線性時間選擇（linear-time selection）

選擇問題要求一個未排序列表中第 k 小的元素——例如中位數（中間那個）、最小值（k=1）或第 90 百分位數。顯而易見的方法是把全部排序再讀出位置 k，花費 O(n log n)。但找出一個元素不該需要把其他所有元素完全排序，而選擇確實能以 O(n)——線性時間——完成，漸進上比任何比較排序都快。

分治引擎是借自快速排序的分割。挑一個樞紐並分割陣列使較小的去左、較大的去右；這把樞紐放到它真正的排序索引（設為位置 p），花 O(n)。現在比較 k 與 p：若 k 等於 p 就找到答案；若 k < p 第 k 小落在左部，於是在那遞迴；若 k > p 在右部以調整後的名次遞迴。關鍵是你只在「一側」遞迴，而非兩側——這點與快速排序不同。若每次分割都把陣列縮小一個固定比例，工作量形成幾何級數 n + (比例)n + (比例)^2 n + ...，總和為 O(n)。保證好樞紐的兩種方式給出兩個變體：中位數的中位數（確定性最壞情況 O(n)）與隨機樞紐（期望 O(n)）。

線性時間選擇是個驚人結果：你能取出中位數或任何順序統計量，而不必付出完整排序的代價，因為你每一步都丟掉一側、而非處理兩側。它被用作挑好樞紐的副程式、在統計中找百分位數，以及許多幾何與最佳化演算法內部。誠實的隱憂還是那個反覆出現的：確定性 O(n)（中位數的中位數）隱藏一個大常數，所以人們實際跑的是隨機期望 O(n) 版本，並接受它在一連串倒楣樞紐的離奇情況下最壞為 O(n^2)。