1、冒泡排序
冒泡排序（Bubble Sort）也是一种简单直观的排序算法。拿第一个和第二个进行相比，谁大就往后放。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
def bubble_sort(array): for i in range(len(array) - 1): swap = False #为假，没有拍好序 for j in range(len(array) - 1 - i): if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j] swap = True if not swap: break return array array = [100, 59, 20, 122, 10] print(bubble_sort(array))
2 、快速排序
快速排序：不稳定的排序、基准值越小，时间复杂度越高。尽可能取中间值。
先从数列中取出一个数作为基准数。
分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
再对左右区间重复第二步，直到各区间只有一个数。
方式一：相比简单易理解。取最后一个作为基准数。
def quick_sort(lst): if len(lst) <= 1: return lst # 左子数组 left = [] # 右子数组 right = [] # 基准数 -- 取最后一个 base = lst.pop() # 对原数组进行划分，小于基准数的放左边，大于等于基准数的放右边 for i in lst: if i < base: left.append(i) else: right.append(i) # 递归调用 return quick_sort(left) + [base] + quick_sort(right) lst2 = [22, 58, 10, 66, 0, 6, 89, 98, 18, 39, 45, 76] print(quick_sort(lst2)
方式二：以数组的第一个作为基准数，相比之下可能会有点复杂
def QuickSort(num): if len(num) <= 1: #边界条件 return num key = num[0] #取数组的第一个数为基准数 list = [] #定义空列表，分别存储小于/大于/等于基准数的元素 right = [] key1 = [key] for i in range(1,len(num)):#遍历数组，把元素归类到3个列表中 # print(i) if num[i] > key: right.append(num[i]) elif num[i] < key: list.append(num[i]) else: key1.append(num[i]) return QuickSort(list)+key1+QuickSort(right) #对左右子列表快排，拼接3个列表并返回 nums = [5,32,56,42,1,2,83,100] print(QuickSort(nums))
