隨機快速選擇（randomized quickselect）

隨機快速選擇是找第 k 小元素的實用方法：它就是只往含答案那一半遞迴的快速排序，且樞紐隨機選取。用擲硬幣而非固定規則挑樞紐，正是讓它的良好表現取決於運氣、而非輸入的關鍵——沒有任何特定的資料排列能成為它的剋星。

程序如下：從目前陣列中均勻隨機選一個樞紐，並以 O(n) 分割。樞紐落在它真正的名次 p。若 k 等於 p 就回傳它；若 k < p 往左遞迴，否則往右遞迴（只一側）。用隨機樞紐，存活那側的期望大小是目前大小的一個固定比例，所以期望總工作量是幾何級數 n + (3/4)n + (3/4)^2 n + ... = O(n)。一個乾淨的看法：由期望值的線性性質，把各輪的期望分割成本相加，其上界是常數乘以 n。所以對每個固定輸入，期望執行時間是 O(n)，這個期望是針對演算法自己的隨機擲幣而言。

這是人們實際用來找中位數、百分位數與選好樞紐的演算法，因為它的常數因子極小、且其期望 O(n) 不論輸入分布為何都成立——隨機性是內部的，所以沒有壞輸入，至多只有一次壞的執行。關鍵的誠實：這裡的 O(n) 是期望時間，不是最壞情況保證。若擲幣串通起來每次都挑到最小或最大元素，你每輪只剝掉一個元素，執行時間就是 O(n^2)。那個最壞情況天文數字般罕見（且對手在看不到你的硬幣時無法強迫它發生），但並非不可能——這正是中位數的中位數以較大常數為代價所消除的取捨。