快速排序法教學：原理、程式碼與時間複雜度

用白話說明原理

1. 選一個樞紐元素，例如最後一個元素，或隨機一個。
2. 分割：把每個比樞紐小的元素移到它的左邊，每個比樞紐大的元素移到它的右邊。這時樞紐已在排序後的最終位置。
3. 遞迴地排序樞紐左邊的部分與右邊的部分。之後不需要再合併任何東西。

合併排序是分割容易、合併困難。快速排序恰好相反：由分割負責主要工作，而把兩半接起來是免費的，因為它們已經在同一個陣列的正確位置上。

範例：一次 Lomuto 分割

以最後一個元素 70 為樞紐，分割 [10, 80, 30, 90, 40, 50, 70]。索引 i 標示小於樞紐的元素區域的終點；j 由左到右掃描。

70 現在位於索引 4，也就是它的最終位置。快速排序接著分別排序 [10, 30, 40, 50] 與 [90, 80]。

Python 實作

import random

def partition(a, lo, hi):
    """Lomuto partition of a[lo..hi] around a random pivot."""
    r = random.randint(lo, hi)
    a[r], a[hi] = a[hi], a[r]       # move the pivot to the end
    pivot = a[hi]
    i = lo - 1
    for j in range(lo, hi):
        if a[j] < pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[hi] = a[hi], a[i + 1]
    return i + 1

def quicksort(a, lo=0, hi=None):
    """Sort list a in place."""
    if hi is None:
        hi = len(a) - 1
    while lo < hi:
        p = partition(a, lo, hi)
        if p - lo < hi - p:           # recurse on the smaller side
            quicksort(a, lo, p - 1)
            lo = p + 1
        else:
            quicksort(a, p + 1, hi)
            hi = p - 1
    return a

print(quicksort([10, 80, 30, 90, 40, 50, 70]))   # [10, 30, 40, 50, 70, 80, 90]
print(quicksort([3, 3, 3, 1]))                   # [1, 3, 3, 3]

對較小的一側遞迴、對較大的一側用迴圈，即使在最差情況下，堆疊深度也維持在 O(log n)。為了說明概念，一個簡短但非原地的版本很受歡迎，不過它在每一層都會配置新的串列：

def quicksort_simple(items):
    if len(items) <= 1:
        return items
    pivot = items[len(items) // 2]
    less = [x for x in items if x < pivot]
    equal = [x for x in items if x == pivot]
    greater = [x for x in items if x > pivot]
    return quicksort_simple(less) + equal + quicksort_simple(greater)

print(quicksort_simple([5, 2, 9, 2, 7]))   # [2, 2, 5, 7, 9]

時間與空間複雜度

經典的最差情況，是對已排序或反向排序的輸入，使用固定選第一個或最後一個元素的樞紐：每次分割只去掉樞紐，形成 n 層、每層 O(n) 的工作量。隨機樞紐讓任何輸入都極不可能發生這種情況。

快速排序與其他排序法的比較

快速排序不是穩定的：分割時的交換可能讓元素越過與它相等的元素。它在記憶體中的陣列上通常勝過合併排序與堆積排序，因為內層迴圈很簡單、原地運作，而且大多依序存取記憶體。內省排序（introsort）被許多 C++ 標準函式庫的 std::sort 實作採用，它先用快速排序，遞迴太深時改用堆積排序，因此保證 O(n log n)。

樞紐選擇、變體與常見錯誤

• 樞紐選擇：第一個或最後一個元素（簡單，但對已排序的輸入是 O(n²)）、隨機元素，或三數取中（第一個、中間、最後一個）。
• Hoare 分割：兩個索引相向移動，交換位於錯誤一側的成對元素。平均來說交換次數比 Lomuto 少。
• 三向分割（荷蘭國旗問題）：分成小於、等於、大於三部分。它讓含有大量重複鍵值的陣列也能很快；單純的 Lomuto 在所有鍵值都相等時會退化為 O(n²)。
• 雙樞紐快速排序使用兩個樞紐與三個部分；Java 用它來排序基本型別的陣列。
• 快速選擇（quickselect）只用一次分割，並只遞迴進入其中一側，以平均 O(n) 的時間找出第 k 小的元素。

何時使用快速排序

在不需要穩定性時，快速排序是排序記憶體中陣列的良好預設選擇。在 Python 中請改用 sorted() 或 list.sort()；它們使用的 Timsort 是穩定的，而且對部分已排序的資料很快。實作快速排序是非常常見的面試題，常接著問最差情況、樞紐選擇、穩定性，或用快速選擇找出第 k 大的元素。