1.選擇排序

• 首先將第一個(gè)元素依次與后面的元素比較，如果第一個(gè)元素比后面大，交換其位置，一輪下來，最小值會(huì)被移到第一位

• 將第二個(gè)元素依次與后面比較，重復(fù)上述操作，第二輪下來，第二小的值會(huì)被移到第二位

• 持續(xù)重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

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.冒泡排序

• 依次比較相鄰的元素。如果前者大于后者，就交換他們兩個(gè)。一組比較下來，最大值會(huì)被排到最后
• 依次比較相鄰的元素，和第一步一樣，只是不比較最后一位，第二輪下來，第二大的值會(huì)被排到倒數(shù)第二位
• 持續(xù)重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

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.插入排序

• 首先假設(shè)序列已經(jīng)被排序,所以開始位置從第二位開始，默認(rèn)第一位已經(jīng)排序好
• 將需要排序的元素和它前面的每一個(gè)元素比較，如果有待插入元素比前面某一元素小，則將指定元素插入到其前面
• 注意：待排序的元素需要事先保存，再與前方的元素比較
• 一輪下來，待插入元素和它之前的元素都已經(jīng)被排好序

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.快速排序

• 挑選基準(zhǔn)值：從數(shù)列中挑出一個(gè)元素，稱為"基準(zhǔn)"（pivot）;
• 分割：重新排序數(shù)列，所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面（與基準(zhǔn)值相等的數(shù)可以到任何一邊）。在這個(gè)分割結(jié)束之后，對(duì)基準(zhǔn)值的排序就已經(jīng)完成;
• 遞歸排序子序列：遞歸地將小于基準(zhǔn)值元素的子序列和大于基準(zhǔn)值元素的子序列排序。

def partition(arr, low, high):
    i = (low - 1)  # 最小元素索引
    pivot = arr[high]
    for j in range(low, high):
        # 當(dāng)前元素小于或等于 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[] --> 排序數(shù)組
# low  --> 起始索引
# high  --> 結(jié)束索引

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

常見的時(shí)間復(fù)雜度高低排序：O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)
循環(huán)減半的過程，時(shí)間復(fù)雜度為O(logn)或O(log2n)