1960-快速排序#

案件摘要#

1960 年，年輕的英國人 Tony Hoare 在莫斯科州立大學交換，一邊學俄語、一邊為一家機器翻譯計畫打工。他遇到的第一個任務，是把俄英詞典的單詞按字母順序排好，供翻譯程式查找。當時教科書上的合併排序需要額外的磁帶與記憶體，對小機器而言過於奢侈。Hoare 在深夜的構想中發明了一種「先分割、再各個擊破」的原地排序法——快速排序，這樁懸案於 1961 年以《Algorithm 64: Quicksort》結案，成為實務上最快的通用排序。

前因 -- 為什麼會有這個案子#

Hoare 在莫斯科交換學生，兼職替機器翻譯計畫排序俄英詞典的單詞卡。
合併排序需要 \(O(n)\) 的額外記憶體，當時機器記憶體極小，額外緩衝區不可行。
Hoare 想要「原地排序（in-place）」：只用陣列本身，不需輔助空間。
已有的插入排序、氣泡排序雖然原地，但平均複雜度為 \(O(n^2)\) ，對大詞典太慢。
分治（divide and conquer）思想已在合併排序中出現，但無人能讓它「不花額外空間」。

線索與推理 -- 數學式、程式、理論#

線索一：分割（partition）#

選一個樞紐（pivot），一趟掃描把小於 pivot 的元素移到左邊、大於的移到右邊，只需 \(O(n)\) 時間與 \(O(1)\) 空間。分割完成後，pivot 已落在最終位置，左右兩半再各自遞迴。

\[ T(n) = T(k) + T(n-k-1) + O(n) \]

其中 \(k\) 是左半部的大小。案件的關鍵就在 \(k\) 的分布。

線索二：平均 \(O(n \log n)\) ，最壞 \(O(n^2)\)#

若 pivot 每次都把陣列大致對半切，遞迴深度為 \(\log_2 n\) ，每層總工作量 \(O(n)\) ：

\[ T(n) \approx O(n) \cdot \log_2 n = O(n \log n) \]

但若陣列已排序而 pivot 又選首元素，每次分割只切出一個元素：

\[ T(n) = T(n-1) + O(n) \Rightarrow T(n) = O(n^2) \]

線索三：隨機 pivot —— 破案時刻#

Hoare 的修正是：不讓敵人（輸入）預測你的策略。隨機選 pivot 後，對任何輸入，比較次數的期望值為

\[ \mathbb{E}[C(n)] = \sum_{k} \frac{2(n-k-1)}{k+1} + \dots \approx 1.39\, n \log_2 n \]

常數 1.39 來自調和級數 \(\sum 1/i = \ln n + \gamma\) ；合併排序的比較次數約 \(n \log_2 n\) ，快排略多但實務更快（原地、快取友好）。這是隨機化演算法（randomized algorithm）的早期經典示範。

線索四：3-way partition 與重複鍵#

1962 年的完整論文中 Hoare 已處理重複鍵的改進；1976 年 Dijkstra 把它形式化為「荷蘭國旗問題」：一趟掃描把陣列分成小於、等於、大於三段，重複鍵極多時將複雜度壓回 \(O(n)\) 級。

程式碼示範#

import random

comparisons = 0

def partition(a, lo, hi):
    global comparisons
    p = random.randint(lo, hi)
    a[p], a[hi] = a[hi], a[p]
    pivot = a[hi]
    i = lo - 1
    for j in range(lo, hi):
        comparisons += 1
        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):
    if hi is None:
        hi = len(a) - 1
    if lo < hi:
        p = partition(a, lo, hi)
        quicksort(a, lo, p - 1)
        quicksort(a, p + 1, hi)

data = list(range(1000))
random.shuffle(data)
quicksort(data)
assert data == sorted(data)
n = len(data)
print(f"n={n}, comparisons={comparisons}")
print(f"1.39 n log2 n = {1.39 * n * __import__('math').log2(n):.0f}")

隨機 pivot 使比較次數落在 \(1.39\,n\log_2 n\) 附近，即使輸入已排序也不會退化。

結案 -- 後果與影響#

快速排序成為實務上最快的通用排序：原地、快取友好、程式簡潔。
C 語言標準函式庫的 qsort、諸多語言內建排序皆以其為基礎或參考。
隨機化演算法的早期示範：以隨機性對抗最壞輸入，開啟 Las Vegas 演算法傳統。
partition 思想延伸出選擇演算法：quickselect 求 \(O(n)\) 期望的第 \(k\) 小，Blum-Floyd-Pratt-Rivest-Tarjan 的 median of medians 給出最壞 \(O(n)\) 。
Hoare 因包括快速排序在內的貢獻獲 1980 年圖靈獎。

關鍵人物與文獻#

C.A.R. Hoare (1961). Algorithm 64: Quicksort. Communications of the ACM, 4(7), 321.
C.A.R. Hoare (1962). Quicksort. The Computer Journal, 5(1), 10-16.
E.W. Dijkstra (1976). A Discipline of Programming. Prentice-Hall.（荷蘭國旗問題）
J. Blum, R. Floyd, V. Pratt, R. Rivest, R. Tarjan (1973). Time bounds for selection. Journal of Computer and System Sciences, 7(4), 448-461.
C.A.R. Hoare (1981). The Emperor's Old Clothes. Communications of the ACM, 24(2), 75-83.（1980 圖靈獎演講）
D.E. Knuth (1998). The Art of Computer Programming, Vol. 3: Sorting and Searching (2nd ed.). Addison-Wesley.