選取問題，以及為何不乾脆排序
這裡有個看似平凡的問題：給定一個含 n 個數字的未排序陣列與一個排名 k，找出第 k 小的元素。中位數是著名的特例（k = n/2），但 k 可以是任何值——第 7 小、第 90 百分位。偷懶的答案是把整個陣列排序，再讀出位置 k。這行得通，但排序要花 Theta(n log n)，而且它做的遠超過我們的要求：我們只想要「一個」元素就定位，它卻把「每個」元素都排好了。本指南的目標，是用誠實的線性時間 O(n) 完成這件事——比任何以排序為基礎的做法都還快。
為什麼 O(n) 竟然有可能？因為找出一個有排名的元素，確實比完整排序容易。我們不需要所有小元素彼此之間的相對順序，也不需要所有大元素之間的順序——我們只需要知道「有多少個」比答案小，並把坐在排名 k 那一格的那一個分離出來。那是少得多的資訊，而底下的演算法正是靠拒絕計算我們永遠用不到的順序來換取速度。
快速選取：先分割，再只遞迴進一邊
起點是你在快速排序那篇指南裡已經見過的分割常式。挑一個樞紐，然後重排陣列，使所有比樞紐小的落在它左邊、所有比它大的落在右邊；分割步驟會讓樞紐停在它最終排好序的位置，假設是索引 p。接著就是讓選取比排序便宜的那個轉折。把 p 和目標排名 k 比較：若 p 等於 k，樞紐「就是」答案，我們停手。若 k < p，答案完全落在左塊裡，於是我們只往那邊遞迴；若 k > p，它落在右塊裡，我們只往那邊遞迴。我們每次都丟掉一整邊。
這就是快速選取，它是減治法的漂亮範例：不像合併排序或完整的快速排序會往「兩」半都遞迴，這裡只有一個遞迴呼叫存活下來——正像二分搜尋，只不過是在未排序資料上、由分割來做切分。當樞紐落在中間附近時，存活的那塊大約是原本的一半，所以每層的工作以幾何級數縮小：n，然後 n/2，然後 n/4，依此類推。那個幾何級數加總約為 2n，也就是 O(n)。一次又一次好的切分，選取就是線性的。
馴服樞紐的兩種辦法
要逃離平方的最壞情況，有兩條路。第一條是放棄保證好樞紐，改成每次都「隨機」挑一個。這就是隨機化快速選取，一段簡短的分析顯示它的期望執行時間是 O(n)：平均而言，一個隨機樞紐落得離兩端夠遠，使存活的那邊以一個常數比例縮小。它簡單、實務上快，也幾乎總是真實函式庫採用的做法。但要把宣稱說精確——這裡的 O(n) 是對擲硬幣取的「期望」時間。仍存在一段機率趨近於零的倒楣樞紐序列，把它推到 O(n^2)；隨機性把壞情況從任何「固定」輸入上挪開，卻沒有廢除壞情況本身。
第二條路更有野心：造出一個「可證明」夠好的樞紐，不擲硬幣、也沒有逃生口——一個確定性的 O(n) 演算法，其最壞情況就是線性。麻煩在於這是循環的：完美的樞紐會是中位數，但中位數正是我們想找的那個難題。脫離這個循環的方法，正是本指南的核心構想，而它有個好記的名字。
中位數的中位數：一個你能信任的樞紐
中位數的中位數這個技巧能快速找出一個近似中位數，而一個近似中位數正是樞紐真正需要的全部。這份食譜很具體，第一次看到時還有點出人意料。
- 把這 n 個元素分成每組 5 個的小組（最後一組可以更小）——總共約 n/5 組。
- 找出每個 5 人小組的中位數。每個只花常數時間，因為 5 個元素用固定幾次比較就能排好，所以所有小組中位數加起來花 O(n)。
- 把那約 n/5 個小組中位數收集成一個新清單，再找出「那個」清單的中位數——遞迴地，對一個規模 n/5 的問題呼叫這同一個選取演算法。
- 把那個中位數的中位數當作樞紐，繞著它分割原陣列，再像快速選取那樣，只往存活的那一邊遞迴。
為什麼這個樞紐好？想像那些小組中位數，令 M 為它們之中的中位數——也就是我們選的樞紐。在 n/5 個小組中位數裡，有一半至多為 M。對每個這樣的小組，它的中位數至多為 M，而在它那 5 人小組裡、位於該中位數之下的那兩個元素也至多為 M。所以這樣的每一組都貢獻了 3 個保證至多為 M 的元素。那大約是來自約一半的 n/5 個小組、各 3 個——約 (3/10)n 個不大於樞紐的元素。由鏡像的論證，至少約 (3/10)n 個元素不小於樞紐。因此這個樞紐永不極端：每 10 個元素中，至少有 3 個坐在它的每一側。
那個保證正是全部的重點。既然至少約 3/10 的元素落在每一側，我們遞迴進去的那一邊至多容納約 7/10 的元素。存活的那塊永遠以一個常數比例縮小——絕不會只縮 1，像草率樞紐所容許的那樣。毀掉單純快速選取的壞情況根本不可能發生，因為我們刻意把樞紐工程化到讓它不可能。
為什麼這條遞迴關係式解出線性
現在誠實地算成本。每次呼叫在遞迴之外做 O(n) 工作——分組、找小中位數、分割。然後它做「兩」個遞迴呼叫：一個規模 n/5，用來找小組中位數的中位數；一個規模至多 7n/10，用來遞迴進存活的那邊。把這寫下來就得到底下的遞迴關係式。令人吃驚的是，這個有兩個呼叫的遞迴關係式竟仍解出 O(n)。
T(n) = T(n/5) + T(7n/10) + O(n) key fact: 1/5 + 7/10 = 2/10 + 7/10 = 9/10 < 1 so: T(n) <= c*n * (1 + 9/10 + (9/10)^2 + ...) = c*n * 10 = O(n)
用本階稍早養成的遞迴樹習慣來讀這條遞迴關係式。根做 c*n 的工作。它的兩個子節點處理規模 n/5 與 7n/10，所以「下一」層做 c*(n/5) + c*(7n/10) = c*(9n/10) 的工作——只有上一層的 9/10。每層都是前一層的 9/10，所以總和是個遞縮的幾何級數 c*n*(1 + 9/10 + 81/100 + …)，加總至多 10*c*n。決定性的事實是 1/5 + 7/10 = 9/10 < 1：兩個子問題合起來嚴格地小於原問題，所以工作以幾何方式衰減，而非在各層間維持不變（後者正是讓合併排序的樹每層花 n、落在 n log n 的原因）。
你實際上該用哪一個
這裡是誠實的實務判斷。中位數的中位數是一個里程碑式的「理論」結果：它證明了確定性、最壞情況線性時間的選取根本是可能的，這是個確實令人意外的事實，也是聰明的樞紐設計如何擊敗天真界限的典範。但它的隱藏常數很大——所有那些分組、找子中位數、加上額外的遞迴呼叫，都意味著它的 O(n) 帶著沉重的係數。實務上，隨機化快速選取更簡單也更快，而中位數的中位數那個漸進 O(n) 藏著的常數大到足以讓隨機方法在真實輸入上通常勝出。中位數的中位數的價值在於當「後備」：有些函式庫跑隨機化快速選取，只在遞迴跑得太深時才切換到中位數的中位數，既得到快速的典型行為，又有最壞情況線性的保證。
退一步，看看這整階更大的教訓。橫跨二分搜尋、合併排序、快速排序、卡拉楚巴乘法，以及如今的選取，整場遊戲都是同一套：一個規模 n 的問題、一種把它切開的方法，以及一場讓合併成本低到使遞迴關係式塌縮成微小之物的奮鬥。選取是最純粹的示範——我們不只是聰明地切分，更「製造」出那個使切分安全的樞紐本身，把一場脆弱的 O(n) 或 O(n^2) 賭局變成牢不可破的 O(n)。那個動作——把你的子問題工程化到讓最壞情況咬不到你——是你從分治法帶走最強大的構想之一。