同一個範本，只是把苦工搬了家
到現在，分割、解決、合併的範本應該很熟悉了：把輸入拆開，遞迴地解決每一塊，再把答案黏回去。上一篇指南裡，合併排序的拆分非常隨便——只按位置從中間切成兩半——而把排序的代價付在合併那一步：在那裡，把兩個已排好的半邊合起來，每一層要花 O(n) 的工。快速排序正好是它的鏡像。它把代價預先付在「分割」那一步，於是「合併」這一步就免費了。
一口氣把整個點子說完。從陣列裡挑一個元素，叫它樞紐（pivot）。把陣列重新排一排，讓所有比樞紐小的都坐到它左邊、所有比它大的都坐到它右邊，而樞紐本身則落在它在最終排序中該在的那個位置。這個重排就叫做分割（partitioning）。接著遞迴地對左半段和右半段做快速排序。當兩邊都排好回來，整個陣列其實就已經排好了——沒有東西需要再黏。樞紐放對了位置，左邊排好了，右邊排好了，於是它們直接首尾相接。
親手走一遍分割過程
「分割」聽起來好像得用額外的暫存空間，但經典的小技巧只用一次掃描就能就地完成。拿最後一個元素當樞紐。讓一根手指從左掃到右；再用第二個標記，緊跟在「已知比樞紐小的那一堆」的邊界後面。每當手指停在一個比樞紐小的元素上，就把邊界往前推一格，並把那個小元素換進「較小區」。當手指走到尾端，再把樞紐換進邊界那一格。一趟掃描，O(n) 次比較，不用額外陣列。
pivot = A[hi]; i = lo - 1 // i marks end of the 'smaller' region
for j = lo to hi-1: // j is the scanning finger
if A[j] < pivot:
i = i + 1
swap A[i], A[j]
swap A[i+1], A[hi] // drop pivot into its final slot
return i+1 // the pivot's index拿 [3, 7, 1, 5, 2] 來追蹤，樞紐是 2（最後一個元素）。手指看到 3（不比 2 小，跳過）、7（跳過）、1（比 2 小！邊界前進到索引 0，把 A[0] 和這個 1 交換——原本在最前面的 3 被擠到索引 2，得到 [1, 7, 3, 5, 2]）、5（跳過）。手指走完；我們把樞紐 2 換進邊界那一格 A[1]，這會把 7 送到尾端，得到 [1, 2, 3, 5, 7]。看看我們手上有什麼：1 在 2 的左邊，{3, 5, 7} 在 2 的右邊——這裡它們剛好已成順序，但一般而言不必如此，只要正確地落在右側即可。樞紐 2 從此永遠待在它最終的位置，而我們對 [1] 和 [3, 5, 7] 繼續遞迴。
為什麼這是對的？因為有一條在每一步掃描都成立的迴圈不變量：A[lo..i] 裡的東西全都嚴格小於樞紐，而 A[i+1..j-1] 裡的東西全都不小於樞紐。每一輪迭代都為新進來的元素重新讓這條不變量成立，於是迴圈結束時陣列就被乾淨地切開，而最後那一次交換把樞紐恰好放在接縫上。我們正是在重用前面學習階段裡那套不變量的機制——分割並不神奇，它只是一個帶著「可證明的承諾」的小迴圈。
為什麼合併那一步不花成本
這是讓從合併排序過來的人最意外的地方。當兩個遞迴呼叫都回來之後，快速排序「完全不做」任何合併——沒有 merge、沒有複製、沒有比較。原因是：分割早就把每個元素放到了樞紐正確的那一側，而樞紐本身也已經就定位。所以一旦左子陣列內部排好、右子陣列內部也排好，把它們接起來（這完全免費，因為它們本來就是同一個陣列裡相鄰的切片）就得到一個完全排好的陣列。合併那一步已經塌縮成什麼都沒有。
於是合併排序花在「merge」上的那每層 O(n)，快速排序改花在「partition」上——同樣的預算，不同的步驟。如果樞紐把陣列切成大致相等的兩半，遞迴大約有 log n 層，每一層做 O(n) 的分割工，給出我們已經熟悉的遞迴關係式 T(n) = 2 T(n/2) + O(n)，它解出 O(n log n)。這幅畫面跟合併排序的遞迴樹一模一樣：O(n) 的工，攤在大約 log n 層上。快速排序只是從另一扇門走到了同一個結果。
樞紐決定一切
上面這一切都假設樞紐把陣列大致切成兩半。但沒有任何東西「強迫」出一個好的切分——樞紐不過是我們隨手挑的某個元素，而資料才決定結果會多麼一面倒。假設我們總是拿最後一個元素當樞紐，而陣列本來就已排好：[1, 2, 3, 4, 5]。樞紐 5 是最大的，於是左半段拿走其他四個元素、右半段什麼也沒有。分割照樣花了 O(n)，卻幾乎沒換到任何切分。下一層：樞紐 4 又是剩下元素裡最大的，於是又全都堆到同一側。
現在的遞迴關係式不是 T(n) = 2 T(n/2) + O(n)，而是 T(n) = T(n-1) + O(n)：一個子問題只比上一個小一點點，每次只剝掉一個元素。這個遞迴有 n 層，而不是 log n 層，而第 k 層仍做大約 n-k 的分割工。把 1 + 2 + ... + n 加起來得到 Theta(n^2)。同一個演算法，碰到幸運樞紐時跑 O(n log n)，碰到倒楣樞紐時就跑 O(n^2)——一個平方級的爆炸，而且偏偏發生在「已經排好序」的輸入上，這恰恰是你天真地以為應該「很容易」的情況。
這就是關於快速排序最核心的一句老實話，而它正好對應到基礎階段的最壞／最好／平均這組角度。它的最好與平均情況是 O(n log n)，但它的最壞情況確確實實是 Theta(n^2)。只報平均值——「快速排序是個 n log n 演算法」——會藏起一道真實的懸崖。而且這道懸崖不是靠刁鑽的亂數才碰得到，而是普通的、已排序或近乎排序的資料就會碰到，這種資料在真實世界裡層出不窮。
把樞紐隨機化：用一道保證換取運氣
修法很漂亮，也有點狡猾。不要每次都拿最後一個元素，而是從目前的子陣列裡均勻隨機地挑樞紐。這就是隨機化快速排序。關鍵在於：它並不會讓任何單一輸入變得安全——對任何固定的選樞紐規則，總還是有「某個」輸入會觸發 Theta(n^2)。隨機化改變的是「誰掌控那個壞情況」。切分現在由你擲的硬幣決定，而不是由資料的順序決定，所以沒有哪個特定輸入——不管是已排序、反向排序，還是對手事先遞給你的任何東西——能可靠地逼出最壞情況。
- 在分割一個子陣列之前，在它裡面隨機挑一個索引，把該元素換到最末端，這樣樞紐就是現有元素中均勻隨機的一個。
- 之後完全照原樣分割。因為樞紐是隨機的，它落在相當靠中間的位置（給出一個不太一面倒的切分）的機會很高。
- 對兩側都遞迴。攤開整次執行，用一個仔細的期望值論證（每一對元素配一個指示變數，再用期望值的線性性質相加），可證明期望比較次數大約是 1.39 n log n。
那個期望界倚靠一個值得點名的工具：期望值的線性性質。你為每一對元素定義一個指示變數，當這兩者曾被比較過時它是 1，算出這件事的機率（在排序後的順序裡結果是 2/(距離+1)），再把所有這些微小的期望值加起來——即使這些事件彼此糾纏、互相依賴，期望總和仍然就等於各期望值之和。這個技巧把一張嚇人的、遞迴隨機性交織的網，轉換成一個乾淨、可直接相加的 O(n log n) 總額。
選得好，以及快速排序到底適合做什麼
隨機化並不是唯一的防線。一個常見的確定性啟發法是三數取中（median-of-three）：看第一個、中間、最後一個元素，拿它們的中位數當樞紐。它廉價地避開了「已排序」的災難，實務上也傾向給出平衡的切分，不過一個知道規則的聰明對手，原則上仍能造出一個 Theta(n^2) 的輸入——一條確定性規則總是能被騙倒。最徹底的修法，是用「中位數的中位數」在線性時間內挑出一個可證明良好的樞紐，這是本階段第 5 篇指南的主題；它徹底消除最壞情況，代價是一個更大的常數。
既然合併排序能毫無附註地保證 O(n log n)，那到底何必用快速排序？老實的答案是常數與記憶體。快速排序是就地分割的，只需要 O(log n) 的堆疊空間，而教科書版的合併排序得複製到一個大小為 n 的輔助陣列。而且它的內層迴圈又緊湊又對快取友善，所以它隱藏的常數很小——這次是隱藏常數反過來咬向對快速排序有利的一邊。實務上隨機化快速排序常是最快的比較式排序，這恰恰說明了為什麼光靠漸進分析永遠定不了一個選擇；你得在「最壞情況的保證」和「典型速度」之間權衡。
關於上限還有一句老實話。和合併排序一樣，快速排序是比較式排序，而沒有任何比較式排序能在最壞情況下打破 Omega(n log n) 下界——所以 n log n 並不是這兩個演算法的怪癖，而是整個比較模型都會撞上的一堵牆。最後，同一個分割點子，若拿來「只」遞迴進其中一側而非兩側，就給出線性時間的選取（找第 k 小的元素）；那就是你會在第 5 篇指南遇見的 quickselect 表親，而它又是此刻把分割學透的另一份回報。