概述

提示：本文上萬字，陸陸續續疏理知識點加測試代碼，耗時近一個月。閱讀時長40分鐘左右。

本文將十大經典排序算法進行彙總，從源碼實現、複雜度、穩定性進行分析，並對每種排序的特性進行點評。對典型算法，給出了具體應用場景。

通俗地講：

• 如果說插入排序是步步維艱的烏龜，那麼希爾排序是跳躍的兔子，冒泡排序就是一個基本無用的小烏龜。選擇排序，聊勝於無，比冒泡強一點點。
• 歸併排序，將大問題分解成小問題，各個擊破，分治思想的完整體現。老闆拆解任務，下放給小兵解決，最後老闆彙總上報。從國家到公司治理，這個套路很常見。
• 快速排序，人如其名，就是非常快！
• 堆排序，將一維數據建成高維的二叉樹，有點“三體”維度打擊的意思。

從技術體系上看，共兩大類排序算法：

• 比較類排序：通過比較決定元素的相對順序，理論上可證明：時間複雜度不能突破O(NlogN)的限制, 是非線性排序。
• 非比較類排序，可以突破比較排序的下界O(NlogN), 達到O(N), 故也稱為線性排序。但有一些前提假設，後文會一一說明。

排序體系圖

每種算法複雜度彙總如下：

說明:

• N：輸入序列長度
• k: 桶個數
• d: 最高位數(基數排序)

選擇排序

每次找到最小值，放到目標位置。

<code>def selection_sort(x, start: int, end: int):
    for i in range(start, end + 1):
        imin = i
        for j in range(i + 1, end + 1):
            if x[j] < x[imin]:
                imin = j
        x[i], x[imin] = x[imin], x[i]/<code>

實現：

• 每次遍歷確認x[i]的正確值
• imin: [i, end]中最小元素的index (參見示意圖)

時間複雜度:

• i, j兩層For循環, 最好最壞區間為[O(N^2),O(N^2)]
• 每次必須遍歷完，才能確定最小值, avg/best/worst均為O(N^2)

空間複雜度：通過交換實現原址排序, O(1)

穩定性: 最後一行的 跨越交換 ，會打亂排序，不能保證穩定。比如[5, 5, 2]:

1. [5(1), 5(2), 2]
2. [2, 5(2), 5(1)]

點評：最樸素的思想: 依次選出第一名、第二名、第三名

冒泡排序

逆序遍歷，查看相鄰元素，如果逆序，偏小值上浮。

<code>def bubble_sort(x, start: int, end: int):
    for i in range(start, end):
        swapped = False
        for j in range(end, i, -1):
            if x[j] < x[j - 1]:
                x[j], x[j - 1] = x[j - 1], x[j]
                swapped = True
        if not swapped:
            break

def bubble_sort_raw(x, start: int, end: int):
    for i in range(start, end):
        for j in range(end, i, -1):
            if x[j] < x[j - 1]:
                x[j], x[j - 1] = x[j - 1], x[j]/<code>

實現：

• 正序遍歷，最大值下沉；或逆序遍歷，最小值上浮。
• 通過檢查當前遍歷是否有過交換操作，如果無，表明已經排序好，可提前退出。

時間複雜度：

• 雙層For循環，時間複雜度為O(N^2)
• 最好：數組已經排序好，可達到O(N)
• 平均、最壞：O(N2)

空間複雜度：原址排序，O(1)

穩定性：相鄰的元素才可能交換，非跨越使交換，保證穩定。

點評：

• 頻繁交換 相鄰 元素，而不能跨越式地交換，是一個缺陷，但帶來的好處是能實現穩定排序。和選擇排序類似，遍歷一遍，確定一個最小元素。
• 玩具算法 ，最簡單但基本無用，唯一用法是快速判斷一個數組是否已排序。很多新版教材都不提及。

插入排序

從前到後依次構建有序序列；對於待排序元素，在已排序列中從後向前掃描，找到對應位置插入。

<code>def insertion_sort(x, start: int, end: int):
    for i in range(start + 1, end + 1):
        j, key = i - 1, x[i]
        while j >= start and key < x[j]:  # swap only             x[j + 1] = x[j]     #             j -= 1
        x[j + 1] = key          # 

def insertion_sort_vfor(x, start: int, end: int):  # for-loop version
    for i in range(start + 1, end + 1):
        key = x[i]
        for j in range(i - 1, start - 1, -1):
            if key >= x[j]:       # '='保證穩定性
                x[j + 1] = key    #                 break
            x[j + 1] = x[j]   #         else:
            x[j] = key          # 

def insertion_sort_vbubble(x, start: int, end: int):      # bubble version, slow, but understandable
    for i in range(start + 1, end + 1):
        j = i
        while j >= start + 1 and x[j] < x[j - 1]:
            x[j], x[j - 1] = x[j - 1], x[j]
            j -= 1
/<code>

實現

• 將已經觀察過的元素排序好，待觀察元素往裡插
• 每次都將x[j+1]賦值: 要麼右移x[j+1]=x[j]; 要麼x[j+1]=key

時間複雜度

• 最好：雖和選擇排序位於O(N^2)同一梯隊，但最好可達到O(N)，假設原序列已經排序好，只需要O(N)
• 最壞、平均：均為O(N^2)
• 拿當前處理位置i和之前的位置(i-1, i-2, …)比較, 如果大於或等於, 不交換。最好，只比較N次。

空間複雜度: O(1)

穩定性: 插入時的如果和歷史元素值相同，不移動歷史數據，能保證穩定

點評：

• 內層循環用while比for更簡潔
• 對於短序列或近似排序好的序列，複雜度非常低

希爾排序

對子序列進行插入排序，實現最終排序（子序列步長遞減），是對插入排序的優化。

<code>def shell_sort(x, start: int, end: int, version="knuth"):
    n = end - start + 1
    h_list = gaps(n, version=version)

    for h in h_list:
        for i in range(start + h, end + 1):  # h-sort
            j, key = i - h, x[i]
            while j >= start and key < x[j]:
                x[j + h] = x[j]
                j -= h
            x[j + h] = key

def gaps(n: int, version="knuth") -> List[int]:
    """
    get the shell-sort gap list for length=n input sequence
    """
    if version == "shell":
        h_list, h = [], 1           # (3**k-1)//2 for k in [1, 2, 3, ...]
        while h < n // 2:           # 1, 4, 13, 40, 121, 364, 1093
            h_list.append(h)
            h = h * 2
    else:  # "knuth":                     # (3**k-1)//2 for k in [1, 2, 3, ...]
        h_list, h = [], 1
        while h < n // 3:           # 1, 4, 13, 40, 121, 364, 1093
            h_list.append(h)
            h = 3 * h + 1
    return h_list[::-1]
/<code>

代碼：

• 常用的步長序列：reverse(1, 2, 4, 8, 16, 32, …)、reverse(1, 4, 13, 40, 121, 364, 1093, …)
• 理解：對間隔為h的子序列，分別應用插入排序
• 實現：從start+h往後遍歷一遍，交替地實現對間隔為h的多個子序列的插入排序

時間複雜度：

• 基於插入排序，最好最壞區間為：[O(N),O(N^2)/(N^1.5)], 取決於步長序列的設計
• 平均：O(N^1.2)

空間複雜度：O(1)

穩定性：雖基於插入排序，但是子序列導致排序不穩定

點評：

• 插入排序兩個特徵，一個優點是對於近似排好序的序列，複雜度很低；一個缺點是需要頻繁移動相鄰元素。希爾排序，揚長避短，充分利用插入排序的優點，避免插入排序的缺點。
• 通過對間隔為h的子序列排序，可快速交換，逐步讓序列近似排好序過程中本質上還是插入排序，但不是笨笨的順序遍歷
• 如果說插入排序是烏龜，一步一步地移動；那麼希爾排序就時兔子，可以幾步幾步地跳躍

快速排序

隨機選取一個標杆元素，左邊放小元素，右邊放大元素，再遞歸對左邊、右邊的子序列快排。

<code>def quick_sort(x: Sequence, start: int, end: int):
    def partition(x, start, end) -> int:  # Lomuto
        idx = int((start + end) // 2)  # random
        x[idx], x[end] = x[end], x[idx]

        m = start
        for i in range(start, end):  # without x[end]
            if x[i] < x[end]:
                x[i], x[m] = x[m], x[i]  #                 m += 1 

        x[end], x[m] = x[m], x[end]  #         return m

    if start >= end: return
    m = partition(x, start, end)
    quick_sort(x, start, m - 1)
    quick_sort(x, m + 1, end)


def quick_sort_hoare(x: Sequence, start: int, end: int):
    def partition(x, start, end) -> int:
        i, j = start - 1, end + 1
        pivot = x[int((start + end) // 2)]
        while True:
            j -= 1
            while x[j] > pivot:
                j -= 1

            i += 1
            while x[i] < pivot:
                i += 1

            if i < j:
                x[i], x[j] = x[j], x[i]
            else:
                return j

    if start >= end: return
    m = partition(x, start, end)
    quick_sort_hoare(x, start, m)
    quick_sort_hoare(x, m + 1, end)
/<code>

代碼:

• 由上而下編程，上層代碼只有最後4行，加上partition()
• 函數核心是partition()

時間複雜度:

• 理想情況下，每次選取的x[end]都為中位數, 每次將長度N的原問題平均分為兩個子問題, 達到最好的O(NlogN)
• 最壞情況下, 每次選取的x[end]都為最大值或最小值, 最壞為O(N^2)

空間複雜度: 通常實現為原址排序，平均空間複雜(函數調用棧空間，非尾遞歸，棧空間不能避免）為O(logN)

穩定性: 通常都是不穩定的(最後一次跨越交換導致)，也有穩定版本

點評：

• partition有兩個版本，Lomuto版易寫；Hoare版通過雙指針實現，容易出錯，但交換次數會小些，標準庫通常基於Hoare版本。
• 解決三色排序問題時，遍歷一遍同時實現三個分區的劃分標準庫的排序算法，基本都是快速排序，因為快速排序的常數因子非常小

三色排序的問題，請訪問

歸併排序

標準的分治思想：

• 分解：分解成長度相等的左右子序列
• 解決：遞歸調用歸併排序，解決左右子問題
• 合併：合併排序好的左右子序列

<code>def merge_sort(x: Sequence, start: int, end: int):
    def merge(x, start, end):
        m = (start + end) >> 1
        left, right = x[start:m + 1], x[m + 1:end + 1]
        left.append(float('inf'))
        right.append(float('inf'))

        i_left, i_right = 0, 0
        for i in range(start, end + 1):
            if left[i_left] <= right[i_right]: # <=, 保證穩定性
                x[i] = left[i_left]
                i_left += 1
            else:
                x[i] = right[i_right]
                i_right += 1
    if start >= end: return
    m = (start + end) >> 1
    merge_sort(x, start, m)
    merge_sort(x, m + 1, end)
    merge(x, start, end)
/<code>

代碼

• 頂層代碼有5行，比quick_sort多出了合併的一行(分治=分解、解決、合併)
• 難點為merge(): 確保穩定性、用哨兵結點

時間複雜度:

• 利用多核, 高度並行化版本，可做到O(logN)
• 不同於quick_sort(), 沒有初始化的困惑，每次都嚴格2分, 最好最壞區間範圍：[O(NlogN),O(NlogN)]

空間複雜度: 合併時，需要將left, right合併到新空間，複雜為O(N), 無法直接覆蓋原數組

穩定性:

• 當left和right中比較的兩數相等時，優先選擇left
• 因為left本身就比right靠前,這樣可以保證穩定

點評： 快排、歸併排序: 均為分治算法，頂層結構一致（分解，解決，合併）

堆排序

優先隊列和Top k問題中經常用到 堆 這種數據結構。本節介紹堆的基本性質、堆排序、優先隊列、利用堆解決Top k問題。

堆的基本性質

堆，是具有下列性質的近似完全二叉樹：每個節點的值都小於等於其左右孩子節點值是小根堆（大於等於則是大根堆）。

下圖為大小為N=9的堆，高度、深度為log2(9)=3，為從根節點到葉結點的最長路徑長度（邊的個數）。根節點深度為0（相當於海平面），葉子結點深度最深。而高度的計算方式與深度相反，認為葉結點為地平面。

父子關係滿足：

• left(i) = 2i+1
• right(i) = 2i+2
• parent(i) = (i-1)//2

最後一個非葉結點index為parent(N-1) = (N-1-1)//2。故：

• 非葉結點範圍：[0,N//2-1]
• 葉結點範圍：[N//2, N-1]

堆化

建立堆(堆化)的過程：

• 從最後一個非葉結點開始，自底向上構建堆。
• 核心函數為heapify(x, i), 假設i的左孩子、有孩子都滿足堆的性質。以維護最小堆的性質為例：將i結點依次下沉, 所以複雜度為Height(i)。尾遞歸, 空間複雜可優化為O(1)，用循環實現

<code>def build_min_heap(x):
    n = len(x)
    for i in range((n-2)//2, -1, -1): # 必須遞減，滿足heapify中孩子為堆的假設
        min_heapify(x, i, n)

def min_heapify(x, i:int, size:int):
    imin, left, right = i, 2*i+1, 2*i+2
    if left<size>        imin=left
    if right<size>        imin=right
    if i!=imin:
        x[i], x[imin] = x[imin], x[i]
        min_heapify(x, imin, size)
/<size>/<size>/<code>

建立堆複雜度為O(N)：

• 有1/2的元素向下比較了1次; 有1/4的元素向下比較了兩次; …;
• 根據數學推導，可得比較次數<=2n

堆排序

• 構建最小堆，依次彈出堆頂元素
• 構建最大堆，首尾交換，size縮減1，堆頂元素下沉

<code>def max_heapify(x, i: int, size: int):
    imax, left, right = i, 2 * i + 1, 2 * i + 2
    if left < size and x[left] > x[imax]:
        imax = left
    if right < size and x[right] > x[imax]:
        imax = right
    if i != imax:
        x[i], x[imax] = x[imax], x[i]
        heapify(x, imax, size)

def heap_sort(x):
    n = len(x)                  # build max-heap, O(N)
    for i in range((n - 1 - 1) // 2, -1, -1):
        max_heapify(x, i, n)

    for i in range(n - 1, 0, -1):  # swap and siftdown, O(NlogN)
        x[0], x[i] = x[i], x[0]
        max_heapify(x, 0, size=i)
/<code>

原址排序，時間複雜度O(NlogN)

實現：

• 建立最大堆：O(N)
• 首尾元素交換，然後堆大小縮減1，堆頂元素下沉：log(N) + log(N-1) + … = O(NlogN)

時間複雜度: O(N+NlogN) = O(NlogN)

• 構建堆: 倒數第二層的元素每個比較1次，倒數底三層元素每個比較2次, …: 微積分計算可得O(N)
• 首尾元素交換，然後堆大小縮減1，堆頂元素下沉：log(N) + log(N-1) + … = O(NlogN)
• heapify()維持堆的性質不變，即使已經排好序，首尾交換也會打亂，使得最好最壞複雜度[O(NlogN),O(NlogN)]

空間複雜度：O(1)如果heapify()遞歸實現，似乎也需要O(logN)的棧空間，但是是尾遞歸, 可優化為O(1)的迭代實現

穩定性：每次首尾交換, 跨越式交換，必然不穩定 [5,5,5]

點評：優先先隊列、Top k問題，用堆排序非常合適

一種更加容易理解的堆排序(非原址、且建堆複雜度提高)方式如下：

<code>import queue
def heap_sort_using_pq(x, start: int, end: int):
    pq = queue.PriorityQueue()  # 構建堆(優先隊列), O(NlogN)
    for i in range(start, end + 1):
        pq.put(x[i])

    for i in range(start, end + 1):  # 彈出最小值, O(NlogN)
        x[i] = pq.get()

/<code>

實現：

• 構建最小堆（優先隊列）: O(NlogN)
• 依次彈出最小值（堆頂元素，並維護堆性質不變）: O(NlogN)

時間複雜度

• O(2NlogN) = O(NlogN), 常數因子比原址排序大
• 從堆頂端拿出最值, 底部末尾拿一個最補上去, 每次POP的複雜度均為O(logN): O(NlogN)

空間複雜度為O(N)

穩定性：每次pop(), 從頂端拿出一個, 末尾拿一個放上去, 必然不穩定 [5,5,5]

優先級隊列

Python中，queue.PriorityQueue()是對heapq的OOP封裝

• put(item)
• get()

核心源碼如下：

<code>from heapq import heappush, heappop
class PriorityQueue(Queue):
    '''Variant of Queue that retrie Entries are typically tuples of 

    '''

    def _init(self, maxsize):
        self.queue = []

    def _qsize(self):
        return len(self.queue)

    def _put(self, item):
        heappush(self.queue, item)

    def _get(self):
        return heappop(self.queue)

/<code>

heapq源碼解析

• heapq.heapify(x), 即build_heap()假設左右子樹都已經滿足堆的性質, 一層一層下沉
• heapq.heappush(e)堆尾部填入元素，一層一層上浮(該元素的祖已經排好序，進行插入排序 即可)
• heapq.heappop()堆頂元素彈出堆底元素放入堆頂, 一層一層下沉(heapify(x, i))

真正工業界的PQ,實現細節需要考慮清楚:

排序穩定性：你該如何令相同優先級的兩個任務按它們最初被加入時的順序返回？ A: 存儲進入順序

如果任務優先級發生改變，你該如何將其移至堆中的新位置？ A: 哈希表存儲任務->value, 將value標記為REMOVED, 插入新的元素

或者如果一個掛起的任務需要被刪除，你該如何找到它並將其移出隊列？ A: 哈希表存儲任務->value, 將value標記為REMOVED, 插入新的元素

利用堆，解決top k問題

top-k最小值是個常見問題。比如推薦排序中，給用戶推薦用戶最感興趣的k個物品。一種本方法是利用快速排序，然後取前k個元素，複雜度為O(NlogN)。

更好地方法是利用堆。

一種方法是構建一個最小堆O(N)，然後取top-k O(klogN) , 時間複雜度為 O(N + klogN)，空間複雜度為O(N)

另外一種方法，構建大小為k的最大堆, heapq.nsmallest(k)採用的是這種方法，時間複雜度為O(k+Nlogk+klogk), 空間複雜度為O(k)。

想想你是一個功利的班主任，你擁有一間容量為k的教室，你需要從N多個學生中跳出Top k個好學生放進你的教室。

• 構建一個大小為k的最大堆O(k) [ 一個尖子班，人數限制為k ]
• 遍歷元素，維護最大堆的性質：(Nlogk) [
  將其餘同學依次插班到尖子班 ]如果該元素比最後一名好（小），則堆頂元素替換為該元素，並下沉 [ 只要與尖子班的最後一名比較，就能確認是否能進尖子班 ]
• 對最大堆元素進行快速排序(klogk)

點評：尖子班的最後一名很重要，用最大堆的堆頂，可快速獲取最後一名

桶排序

假設輸入服從均勻分佈，將數據劃分到有限數量的桶裡，每個桶內部分別排序。

<code>def bucket_sort(x: List[float], k: int = None):  # x ~ uniform [0, 1)
    n = len(x)
    k = n if k is None else k
    buckets = [[] for _ in range(k)]
    for e in x:
        buckets[int(e * k)].append(e)  # e//(1/k), 1/k is capacity of bucket

    for bucket in buckets:
        quick_sort(bucket, 0, len(bucket) - 1)

    ans = []
    for bucket in buckets:
        for e in bucket:
            ans.append(e)

    return ans
/<code>

時間複雜度：

• 最好：數據服從均勻分佈，均勻散落到每個桶，最好達到O(N)
• 最壞：數據嚴重偏離均勻分佈，都算落到某一個桶中，取決於桶內排序算法的複雜度

空間複雜度：O(N+k)

穩定性：取決於桶內排序算法的穩定性

點評： 數據服從均勻分佈、將其映射到[0, 1) 區間

計數排序

假設輸入為[0, k]區間內的非負整數，將輸入數據計數存儲在新的序列中，然後逆序遍歷輸入序列，將該元素寫入正確位置。

計數排序，是一種特殊的桶排序，每個桶最多有一個元素。

計數排序強制每個桶容積為1, k可以遠大與N, 所以時間、空間複雜度分析均為O(N+k), k必不可少，比如：

• x=[0, 10000]
• N=2
• k=10000

<code>def counting_sort(x: List[int]):
    k, n = max(x), len(x)
    c, ans = [0] * (k + 1), [None] * n

    for e in x:                 # k -> count(k)
        c[e] += 1

    for i in range(1, k + 1):  # k -> count(<=k)
        c[i] += c[i - 1]
 

    for j in range(n - 1, -1, -1):  # stable sort
        ans[c[x[j]] - 1] = x[j]
        c[x[j]] -= 1

    return ans
/<code>

實現：計數計數累積逆序輸出

時間複雜度：計數序列累積O(k), 兩次遍歷輸入序列O(N), 所以時間複雜度區間為[O(N+k), O(N+k)]

空間複雜度：計數數組、輸出序列佔用空間為O(N+k)

穩定性：最後一個For循環的逆序遍歷輸入，保證了穩定性

點評：輸入的數據如果有確定範圍的整數，通過偏移映射成[0, k]區間內的整數，可用計數排序

基數排序

先低位穩定排序，然後再高位穩定排序，直到最高位。

<code>def counting_sort_for_radix(x: List[int], data: List):
    k, n = max(x), len(x)
    c, ans = [0] * (k + 1), [None] * n

    for e in x:                 # k -> count(k)
        c[e] += 1

    for i in range(1, k + 1):  # k -> count(<=k)
        c[i] += c[i - 1]

    for j in range(n - 1, -1, -1):  # stable sort
        ans[c[x[j]] - 1] = data[j]  #         c[x[j]] -= 1

    return ans 


def radix_sort(x):
    d = len(str(max(x)))
    for i in range(d):
        tmp = [e // (10**i) % 10 for e in x]
        x = counting_sort_for_radix(tmp, x)
    return x

/<code>

實現：

• 從低位到高位，依次調用穩定排序算法
• 計數排序只有一行和標準代碼不通，賦值時用原始數據

空間複雜度:

• O(內部排序)
• 如果為計數排序，O(N+k)=O(N)

時間複雜度:

• d*O(內部排序)
• 如果為計數排序，d*O(N+k) = O(dN+dk) = O(dN)，因為基數排序中k很小（比如十進制中，k=10）

穩定性：是

點評：計數排序+基數排序，k會很小

總結

穩定性分析：有跨越交換的，都不穩定。

• 冒泡排序，相鄰元素交換，可保證穩定。
• 歸併排序，左右子塊中左為先，右為後，保證穩定。
• 插入排序，元素一個一個逐步右移，保證穩定。
• 計數排序，逆序按count值寫入，保證穩定。

本地運行的時間比較, 10240個隨機整數，10次排序取均值，運行時間如下：

最後來一個動圖，將七種比較排序放在一起，看下效果。通過監測對原數組的讀寫來大致模擬複雜度。注意：

• 歸併排序中，新建的數組的操作未統計，會使得歸併排序性能偏好
• 堆排序中，為遞歸實現，可通過循環優化，堆排序性能偏差
• 選取的N=16很小, 時間僅供參考

九宮格中，排序算法分佈：

對於隨機數據:

對於逆序數據：

對於已排序數據：

更新日誌

• 2020-02-24 模板、複雜度、穩定性
• 2020-03-09 增加非比較排序
• 2020-03-11 shell sort

閱讀更多 平凡科技 的文章

關鍵字: 算法 本文 排序