隨機快速排序（randomized quicksort）

一般的快速排序透過挑一個「樞紐」、把其餘元素分成比它小與比它大的兩堆、再分別排序來完成。當樞紐落在接近中間時很快，但糟糕的固定選法（比如永遠取第一個元素）在已排序資料上可能是災難，退化成 O(n^2)。隨機快速排序透過每次隨機挑選樞紐來消除這個弱點，於是沒有任何特定輸入會是最壞情況——對手無法預測你的擲幣結果。

精確地說：在每次遞迴呼叫時，從當前子陣列中均勻隨機挑一個樞紐，繞它分割，再對兩側遞迴。這個演算法永遠正確地排序；只有執行時間依賴於隨機選擇。期望比較次數是優雅的部分。令 X_ij 為「第 i 小與第 j 小的元素是否曾被比較」的指示變數。兩個元素恰好在其中之一是整段範圍裡第一個被選為樞紐時被比較，由對稱性這以機率 2/(j - i + 1) 發生。由期望值的線性性質，期望總比較次數為 Σ_{i<j} 2/(j - i + 1)，算出來約為 2 n ln n = O(n log n)。這個期望不需要任何獨立性假設——線性就扛起了它。

隨機快速排序之所以重要，是因為它給出快速排序的實務速度，又附帶一個不依賴輸入順序的保證：它對每個輸入的期望時間都是 O(n log n)，且切爾諾夫式的論證顯示它也以高機率為 O(n log n)。它是把脆弱的平均情況故事轉成穩健隨機故事的教科書範例。誠實的提醒：最壞情況仍是 O(n^2)——一連串倒楣的樞紐選擇可能很慢——而那個 O(n log n) 是對演算法擲幣取的期望，不是硬性界限。精確選中位數能確定性地保證 O(n log n)，但找中位數的代價超過所省，所以隨機性才是務實的勝利。