隨機選擇（randomized selection）
有時你不需要把整個清單排序——你只想要第 k 小的項目，例如中位數。為了讀出一個位置而排序所有東西很浪費。隨機選擇直接找出第 k 小，用的是與快速排序相同的隨機樞紐想法，但只遞迴進入一側，這使它平均以線性時間執行，而非 n log n。
精確地說：均勻隨機挑一個樞紐並分割陣列；設樞紐落在位置 p。若 p 等於 k 就完成了；若 k < p 答案在左部，若 k > p 答案在右部——所以你只遞迴進入那一側，丟棄其餘。因為每次分割平均丟掉一個固定比例的元素，期望總工作量是一個幾何級數，n + (3/4)n + (9/16)n + ... = O(n)，線性時間。看清這個固定比例的乾淨方式：一個隨機樞紐以機率二分之一落在順序的中間一半（第 25 與第 75 百分位之間），而這樣的樞紐至少丟掉四分之一的元素；平均而言你只需要幾次分割就能把問題縮小一個固定倍率。
隨機選擇之所以重要，是因為它是取得期望線性時間選擇的最簡單方式，也是其他演算法內部快速找中位數的核心。它是確定性的「中位數的中位數」方法的隨機表親，後者保證 O(n) 最壞情況，但常數較大、程式碼較多。誠實的提醒：和隨機快速排序一樣，若樞紐一再倒楣，最壞情況是 O(n^2)，而那個 O(n) 是對擲幣取的期望。實務上它快又簡單；當你需要硬性的最壞情況保證時，改用中位數的中位數。
要在 [7, 2, 9, 4, 1, 6] 中找第 3 小：隨機樞紐 4 分割成 [2,1]（較小）| 4 | [7,9,6]（較大），於是 4 位於第 3 位——正是答案，不需遞迴。若我們想要第 5 小，就只遞迴進入右部 [7,9,6]。
只遞迴進入一側：期望 O(n)，但最壞情況 O(n^2)。
選擇之所以勝過排序，只因為它遞迴進入一側而非兩側——這一個改變把 n log n 變成期望的 n。但保證是期望線性，不是最壞情況線性；要硬性的 O(n) 界限請用中位數的中位數。