1.选择排序

• 首先将第一个元素依次与后面的元素比较，如果第一个元素比后面大，交换其位置，一轮下来，最小值会被移到第一位

• 将第二个元素依次与后面比较，重复上述操作，第二轮下来，第二小的值会被移到第二位

• 持续重复上面的步骤，直到没有任何一对数字需要比较。

def select_sort(array):
    length = len(array)
    for i in range(length):
        for j in range(i+1,length):
            if array[i] > array[j]:
                array[i],array[j] = array[j],array[i]
    return array

2.冒泡排序

• 依次比较相邻的元素。如果前者大于后者，就交换他们两个。一组比较下来，最大值会被排到最后
• 依次比较相邻的元素，和第一步一样，只是不比较最后一位，第二轮下来，第二大的值会被排到倒数第二位
• 持续重复上面的步骤，直到没有任何一对数字需要比较。

def bubble_sort(array):
    length = len(array)
    for i in range(length):
        for j in range(0,length-i-1):
            if array[j] > array[j+1]:
                array[j],array[j+1] = array[j+1],array[j]
    return array

3.插入排序

• 首先假设序列已经被排序,所以开始位置从第二位开始，默认第一位已经排序好
• 将需要排序的元素和它前面的每一个元素比较，如果有待插入元素比前面某一元素小，则将指定元素插入到其前面
• 注意：待排序的元素需要事先保存，再与前方的元素比较
• 一轮下来，待插入元素和它之前的元素都已经被排好序

def insert_sort(array):
    for i in range(1, len(array)):
        key = array[i]
        j = i - 1
        while j >= 0 and key < array[j]:
            array[j + 1] = array[j]
            j -= 1
        array[j + 1] = key

4.快速排序

• 挑选基准值：从数列中挑出一个元素，称为"基准"（pivot）;
• 分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成;
• 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

def partition(arr, low, high):
    i = (low - 1)  # 最小元素索引
    pivot = arr[high]
    for j in range(low, high):
        # 当前元素小于或等于 pivot
        if arr[j] <= pivot:
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return (i + 1)
# arr[] --> 排序数组
# low  --> 起始索引
# high  --> 结束索引

# 快速排序函数
def quickSort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)

常见的时间复杂度高低排序：O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)
循环减半的过程，时间复杂度为O(logn)或O(log2n)