1960 - Hoare 快速排序（Quicksort 的誕生）#

案件摘要#

1960 年前後，25 歲的 Tony Hoare（1934–2025） 在莫斯科國立大學做交換研究， 為了機器翻譯專案中的一個小需求——「先把單字排序，再查字典」—— 發明了快速排序（Quicksort）：

它的核心是一行不變量：

平均複雜度 \(O(n \log n)\) ，且是原地排序（in-place，不需額外記憶體）—— 這個「順手解決的小問題」，後來成為 C 語言標準函式庫的 qsort， 並隨 UNIX 散布到全世界。1980 年，Hoare 獲圖靈獎—— 而獲獎理由的開頭，正是這個在莫斯科冬夜裡想出來的演算法。

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

• 1959 Dijkstra 最短路徑： Hoare 抵達莫斯科的前一年，Dijkstra 剛發表最短路徑演算法 （見 1959-迪傑斯特拉最短路徑.md）—— 歐洲的「演算法黃金年代」正在展開，分治法（divide and conquer） 的思想已經成熟：

• 1957 FORTRAN： Backus 的 FORTRAN 編譯器（見 1957-巴克斯FORTRAN.md） 證明了高階語言可以自動編譯成高效的機器碼—— 程式設計師開始關心：編譯器內部的排序、查表，要怎麼做才快？
• 當時的排序主流是 merge sort（合併排序）：
• von Neumann（1945） 早已寫下 merge sort——恆定 \(O(n \log n)\) 、穩定；
• 但 merge sort 需要 \(O(n)\) 的額外記憶體——在 1960 年， 記憶體以 KB 計價，每一個位元組都是錢！

• 莫斯科的翻譯難題（1959–1960）： Hoare 在莫斯科國立大學研究機器翻譯：把俄文句子翻成英文，需要查片語字典—— 但字典要先排序，才能用二分搜尋快速查詢。 他先實作了 merge sort，發現太慢也太佔記憶體；接著他嘗試一個瘋狂的想法：

這一「切」，就是快速排序的誕生。

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

第一條線索：分治法（divide and conquer）#

快速排序的三步驟： 1. 分割（partition）：選一個樞紐（pivot），把陣列分成兩半—— 小於樞紐的放左邊，大於的放右邊； 2. 遞迴（recurse）：對左半、右半各自再做同樣的事； 3. 組合：什麼都不用做！分割完，兩半就地接起來就是有序的。

與 merge sort 的最大差別：merge sort 是「先遞迴、後合併（費工）」， quicksort 是「先分割（省工）、後遞迴、零合併」。

第二條線索：分割的不變量（partition invariant）#

不變量：掃描過程中，永遠維持

掃描到 \(j\) 時：若 \(a[j] \le pivot\) ，則 \(i{+}{=}1\) 並交換 \(a[i], a[j]\) ——不變量恢復。 掃描結束後，把樞紐換到 \(i{+}1\) 的位置：

樞紐一旦就位，就再也不動——每一層遞迴，至少一個元素（樞紐）到達最終位置。 這個不變量，就是快速排序正確性的全部證明。

第三條線索：平均 \(O(n \log n)\) ，最壞 \(O(n^2)\) ，與隨機化#

遞迴式：若每次分割都接近對半，則

（與 merge sort 相同——但 quicksort 的分割只需一趟掃描，常數更小、記憶體 \(O(\log n)\) 只存遞迴棧。） 最壞情況：若樞紐永遠選到最大或最小（例如已排序陣列 + 固定取最後一個），分割變成 \(1 : n{-}1\) ：

Hoare 的解法：隨機化樞紐——每次隨機挑一個元素當樞紐， 沒有人（包括輸入資料）能預測樞紐是誰，期望複雜度回到

這是「隨機化演算法」的經典示範——用骰子對抗最壞情況。

Python：快速排序（原地分割 + 隨機樞紐），對照 merge sort#

# 1) in-place partition + 隨機樞紐的快速排序
import random

def quicksort(a, lo=0, hi=None):
    """Hoare 式快速排序：原地排序（in-place），隨機選樞紐"""
    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)
    return a

def partition(a, lo, hi):
    """分割：選樞紐，使左邊 <= 樞紐 <= 右邊（不變量）"""
    r = random.randint(lo, hi)      # 隨機樞紐：對付已排序的「最壞情況」
    a[r], a[hi] = a[hi], a[r]
    pivot = a[hi]
    i = lo - 1                      # i：小於樞紐區的右邊界
    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

# 2) 對照組：merge sort（穩定 O(n log n)，但需要額外記憶體）
def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    L, R = merge_sort(a[:mid]), merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            out.append(L[i]); i += 1
        else:
            out.append(R[j]); j += 1
    return out + L[i:] + R[j:]

# 3) 測試：隨機資料、已排序資料（最壞情況）、與 merge sort 比對
random.seed(1960)
rand_data = [random.randint(0, 99) for _ in range(15)]
sorted_data = list(range(1, 16))          # 已排序：固定樞紐會退化成 O(n²)

print("隨機樞紐快速排序 vs merge sort")
print(f"  原始（隨機）：{rand_data}")
print(f"  quicksort  ：{quicksort(rand_data[:])}")
print(f"  merge sort ：{merge_sort(rand_data)}")

print("\n已排序資料（最壞情況的誘餌，隨機樞紐化解套）：")
print(f"  原始：{sorted_data}")
print(f"  quicksort：{quicksort(sorted_data[:])}")

ok = all(quicksort(rand_data[:]) == sorted(rand_data)
         for _ in range(1000))
print(f"\n隨機資料驗證 1000 次，全部正確？{ok}")

print("\n複雜度對照：")
print("  遞迴式：T(n) = 2T(n/2) + O(n)  →  T(n) = O(n log n)（平均）")
print("  最壞（已排序 + 固定樞紐）：O(n²)；隨機化後期望 O(n log n)")
print("  merge sort：恆 O(n log n)，但需 O(n) 額外記憶體")

隨機樞紐快速排序 vs merge sort
  原始（隨機）：[34, 91, 48, 80, 42, 43, 58, 51, 62, 76, 66, 52, 52, 45, 95]
  quicksort  ：[34, 42, 43, 45, 48, 51, 52, 52, 58, 62, 66, 76, 80, 91, 95]
  merge sort ：[34, 42, 43, 45, 48, 51, 52, 52, 58, 62, 66, 76, 80, 91, 95]

已排序資料（最壞情況的誘餌，隨機樞紐化解套）：
  原始：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
  quicksort：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

隨機資料驗證 1000 次，全部正確？True

複雜度對照：
  遞迴式：T(n) = 2T(n/2) + O(n)  →  T(n) = O(n log n)（平均）
  最壞（已排序 + 固定樞紐）：O(n²)；隨機化後期望 O(n log n)
  merge sort：恆 O(n log n)，但需 O(n) 額外記憶體

結案 -- 後果與影響#

• C 語言標準函式庫的 qsort： 1970 年代末，quicksort 成為 C 標準函式庫的排序函式 qsort—— 至今仍是最通用的排序介面（ANSI C, 1989 標準化）。

• UNIX 的散布（1973）： UNIX（見 1973-UNIX作業系統.md） 以 C 語言重寫後廣為流傳，qsort 隨之進入每一台電腦—— Kernighan 與 Ritchie 的《C 程式設計語言》（1978） 也用 quicksort 作為遞迴的教科書範例。
• Knuth 的定位（1968）： Knuth 在《The Art of Computer Programming》第三卷 （見 1968-克努特演算法藝術.md） 給 quicksort 完整的數學分析——稱它為二十世紀最優雅的演算法之一。

• Hoare 的其他貢獻——「十億美元的錯誤」： 1965 年，Hoare 在 ALGOL W 語言中引入空引用（null reference），並於 2009 年公開懺悔：

今日所有語言的安全設計（如 Rust 的 Option、Swift 的 Optional） 都是在為這個錯誤還債。 - Hoare 邏輯（1969）： Hoare 在論文 An Axiomatic Basis for Computer Programming 提出 Hoare 邏輯（公理語義學）：

這是程式正確性證明與形式化驗證的基石。 - CSP 通訊順序程序（1978）： Hoare 發表《Communicating Sequential Processes》—— 並行程式的訊息傳遞模型，直接影響 Go 語言（goroutines/channels）。 - 圖靈獎（1980）與逝世（2025）： 1980 年，Hoare 因「程式語言的定義與設計」獲圖靈獎—— 得獎演講《The Emperor's Old Clothes》 批評複雜系統，主張簡單性。 他晚年關注形式化驗證，2025 年 3 月逝世，享年 91 歲。

• 歷史定位：Hoare 是「簡潔的力量」的化身—— 他證明了一個好的演算法，可以只用幾行、 不用額外記憶體、快過一切同類； 而它誕生於一個最平凡的場景：查字典前，先把單字排好。

關鍵人物與文獻#

• C. A. R. Hoare：Quicksort（1960–1961，發表於 Computer Journal）；null reference（1965，自稱「十億美元的錯誤」）；An Axiomatic Basis for Computer Programming（1969，Hoare 邏輯）；Communicating Sequential Processes（1978，CSP）；圖靈獎（1980，演講 The Emperor's Old Clothes）；2025 年逝世。
• E. W. Dijkstra：最短路徑（1959）——分治思想的同代人；後續的「結構化程式設計」與 Hoare 呼應。
• J. Backus：FORTRAN（1957）——高階語言時代的開端，編譯器內的排序需求浮現。
• J. von Neumann：merge sort（1945）——quicksort 的對照組（穩定但耗記憶體）。
• D. Knuth：The Art of Computer Programming Vol. 3（1972）——quicksort 的完整數學分析。
• B. Kernighan & D. Ritchie：The C Programming Language（1978）——以 quicksort 為遞迴範例，qsort 進入 C 標準。
• 相關案件：1959-迪傑斯特拉最短路徑.md、1968-克努特演算法藝術.md、1973-UNIX作業系統.md、1957-巴克斯FORTRAN.md。