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))