• 比较相邻的元素。如果第一个比第二个大，就交换他们两个。

• 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

• 针对所有的元素重复以上的步骤，除了最后一个。

• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

'''冒泡排序'''
def Bubble_Sort(arr):
    for i in range(1, len(arr)):
        for j in range(0, len(arr)-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

arr = [29, 63, 41, 5, 62, 66, 57, 34, 94, 22]
result = Bubble_Sort(arr)
print('result list: ', result)
# result list: [5, 22, 29, 34, 41, 57, 62, 63, 66, 94]

• 首先设定一个分界值，通过该分界值将数组分成左右两部分。

• 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。

• 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

• 重复上述过程，直到左、右两个部分各数据排序完成。

'''快速排序'''
def Quick_Sort(arr):
    # 递归入口及出口
    if len(arr) >= 2:
        # 选取基准值，也可以选取第一个或最后一个元素
        mid = arr[len(arr) // 2]
        # 定义基准值左右两侧的列表
        left, right = [], []
        # 从原始数组中移除基准值
        arr.remove(mid)
        for num in arr:
            if num >= mid:
                right.append(num)
            else:
                left.append(num)
        return Quick_Sort(left) + [mid] + Quick_Sort(right)
    else:
        return arr

arr = [27, 70, 34, 65, 9, 22, 47, 68, 21, 18]
result = Quick_Sort(arr)
print('result list: ', result)
# result list: [9, 18, 21, 22, 27, 34, 47, 65, 68, 70]

'''选择排序'''
def Selection_Sort(arr):
    for i in range(len(arr) - 1):
        # 记录最小数的索引
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # i 不是最小数时，将 i 和最小数进行交换
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr

arr = [5, 10, 76, 55, 13, 79, 49, 51, 65, 30]
result = Quick_Sort(arr)
print('result list: ', result)
# result list: [5, 10, 13, 30, 49, 51, 55, 65, 76, 79]

• 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
  

• 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。

'''插入排序'''
def Insertion_Sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

arr = [31, 80, 42, 47, 35, 26, 10, 5, 51, 53]
result = Insertion_Sort(arr)
print('result list: ', result)
# result list: [5, 10, 26, 31, 35, 42, 47, 51, 53, 80]

• 创建一个堆 H[0……n-1]；
  

• 把堆首（最大值）和堆尾互换；

• 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；

• 重复步骤 2，直到堆的尺寸为 1。

'''堆排序'''
def Heapify(arr, n, i):
    largest = i
    # 左右节点分块
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[i] < arr[left]:
        largest = left
    if right < n and arr[largest] < arr[right]:
        largest = right
    if largest != i:
        # 大小值交换
        arr[i], arr[largest] = arr[largest], arr[i]
        # 递归
        Heapify(arr, n, largest)

def Heap_Sort(arr):
    nlen = len(arr)
    for i in range(nlen, -1, -1):
        # 调整节点
        Heapify(arr, nlen, i)
    for i in range(nlen - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        # 调整节点
        Heapify(arr, i, 0)
    return arr

arr = [26, 53, 83, 86, 5, 46, 72, 21, 4, 75]
result = Heap_Sort(arr)
print('result list: ', result)
# result list: [4, 5, 21, 26, 46, 53, 72, 75, 83, 86]