快速排序

不用額外陣列的分治排序

上一課的合併排序把陣列切成兩半、各自排好，再合併起來。它的時間是 O(n log n)，但合併時需要一個和原陣列一樣大的暫存陣列。

快速排序（quick sort）也是分治法，但把功夫花在「切」而不是「合」：

1. 選基準（pivot）：從範圍裡挑一個元素
2. 分割（partition）：把比基準小的元素移到左邊、其他移到右邊，基準放在兩邊中間
3. 遞迴：左右兩邊各自再做一次快速排序

分割完成時，基準已經在它排好之後應該在的位置，左邊每個元素都比它小、右邊都不比它小。所以兩邊各自排好以後，整個陣列就排好了，不需要合併。 分割只在原陣列裡交換元素，不需要暫存陣列，這叫做原地排序（in-place）。

快速排序是英國電腦科學家 Tony Hoare 在 1959 年左右於莫斯科國立大學做機器翻譯研究時想出來的（當時要把單字排序以便查字典）， 1961 年以「Algorithm 64: Quicksort」發表在 Communications of the ACM。

Lomuto 分割法

分割有好幾種寫法，這一課用最容易讀懂的 Lomuto 分割法（Jon Bentley 在《Programming Pearls》介紹時註明出自 Nico Lomuto）：

• 基準取範圍的最後一個元素 a[hi]
• i 標出「比基準小的區域」的下一格：a[lo]～a[i-1] 都比基準小
• j 從 lo 掃到 hi - 1，每遇到一個比基準小的 a[j]，就和 a[i] 交換，i 往右一格
• 掃完以後，把基準 a[hi] 和 a[i] 交換，基準就落在兩區的中間，回傳它的位置 i

掃描途中，陣列隨時分成四段：

看下面的動畫時，注意青綠色的格子（比基準小的區域）怎麼一格一格長大。

兩邊各自再排一次

分割一次只保證基準就定位。接下來對左邊 a[lo..p-1] 和右邊 a[p+1..hi] 各自遞迴：

def quick_sort(a, lo, hi):
    if lo >= hi:              # 0 或 1 個元素：已經排好，這是終止條件
        return
    p = partition(a, lo, hi)
    quick_sort(a, lo, p - 1)
    quick_sort(a, p + 1, hi)

每次分割都會讓一個基準就定位，而且範圍至少少一個元素，所以遞迴一定會結束。 注意 lo >= hi 包含「範圍是空的」（lo > hi，例如基準剛好是最小的元素時，左邊是空的）。

下面的動畫裡，quick_sort 另外回傳這個範圍總共比較了幾次（這次分割的 hi - lo 次，加上左右兩邊遞迴回傳的次數）， 遞迴樹的每個節點下方會標出這個數字，下一節分析速度時會用到。

比較次數：最好 O(n log n)，最壞 O(n²)

Lomuto 分割一個 lo～hi 的範圍，j 會掃過基準以外的每個元素，所以剛好比較 hi - lo 次。整棵遞迴樹的比較次數，就是每一層加起來。

• 最好的情況：每次基準都落在正中間，範圍每層減半。遞迴樹大約有 log₂n 層，每一層的範圍加起來不超過 n 個元素，總共約 n log₂n 次，O(n log n)。
• 最壞的情況：每次基準都是範圍裡最大（或最小）的元素，一邊是空的、另一邊只少一個。遞迴樹變成一條長鏈，有 n 層， 比較次數是 (n-1) + (n-2) + … + 1 = n(n-1)/2，O(n²)。

最壞情況離我們很近：資料已經排好時，最後一個元素永遠是最大的，正好每次都選到最差的基準。 前面那組打亂的 8 個元素 [7, 2, 9, 4, 1, 8, 3, 6] 總共比較 14 次。下面用同一個程式排序已經排好的 8 個元素，看看比較幾次。

資料變多以後差多少

8 個元素的 28 次和 14 次看起來差不多，資料一多差距就拉開。以下是用本課的程式實際數出來的比較次數：

n log₂n 在 n = 1,000 時約是 10,000，n(n-1)/2 是 499,500。已排序或「幾乎排好」的資料在實務上很常見（例如每天只多幾筆新資料的名單）， 所以「永遠取最後一個」的寫法在真實資料上很危險。

另一種危險的資料是大量重複值：Lomuto 分割只把「比基準小」的放左邊，1,000 個全部相同的數，每次分割後左邊都是空的，同樣是 499,500 次。

選一個好一點的基準

最壞情況的根源是「基準選到範圍裡的極端值」。常見的改善方法：

1. 取中間的元素：先把 a[mid] 和 a[hi] 交換，再照原本的方法分割。已排序的資料，中間的元素剛好是中位數。
2. 三數取中（median of three）：看 a[lo]、a[mid]、a[hi] 三個，取大小在中間的那一個當基準，換到 a[hi]：

def median_of_three(a, lo, hi):
    mid = (lo + hi) // 2
    if a[mid] < a[lo]:
        a[lo], a[mid] = a[mid], a[lo]
    if a[hi] < a[lo]:
        a[lo], a[hi] = a[hi], a[lo]
    if a[hi] < a[mid]:
        a[mid], a[hi] = a[hi], a[mid]
    # 現在 a[lo] <= a[mid] <= a[hi]，中位數在 a[mid]
    a[mid], a[hi] = a[hi], a[mid]     # 把中位數換到最後，當作基準

3. 隨機選基準：每次從範圍裡隨機挑一個。不論輸入長什麼樣子，期望的比較次數都是 O(n log n)，很難被特定的資料打敗。 本課的範例不用亂數，因為三種語言的亂數產生器不同，輸出會不一樣。

這些方法讓最壞情況很難發生，但沒有讓它消失：仍然可能有特別安排的資料讓基準一直選到極端值。 所以實際的函式庫會再加保護，例如很多 C++ 標準函式庫的 std::sort 在遞迴太深時改用堆積排序（第 15 課），保證 O(n log n)。

空間與穩定性

• 額外空間：分割是原地交換，不需要暫存陣列；但遞迴需要呼叫堆疊。基準選得好時遞迴深度約 log₂n，最壞情況（一條鏈）深度是 n。 Python 的遞迴深度上限預設約 1,000，用「取最後一個」排序一萬筆已排序的資料，會先遇到 RecursionError。
• 不穩定：分割時的長距離交換可能把兩個相等元素的前後順序對調，所以快速排序不是穩定排序（穩定性見第 06 課）。 例如分割 [3a, 3b, 1]（基準 1），1 和 3a 交換後變成 [1, 3b, 3a]，兩個 3 的順序反了。
• 實務上很快：平均比較次數和合併排序同級，而且只在原陣列裡移動資料、存取的記憶體位置集中，所以常常比合併排序快。 Java 的 Arrays.sort 排序 int[] 這類基本型別時，用的就是快速排序的變形（雙基準快速排序）；Python 的 sort 則是合併排序的變形（Timsort），下一課會再談。

只想知道第 k 小：快速選擇

有時候不需要整個排好，只想知道「第 k 小的數」，例如中位數。先排序再取 a[k] 要 O(n log n)，但分割其實已經提供了足夠的資訊：

分割回傳基準的位置 p，基準左邊有 p 個比它小的元素，所以基準就是第 p 小（從 0 算起）。

• p == k：基準就是答案
• p < k：答案在右邊，左邊整段不用再管
• p > k：答案在左邊，右邊整段不用再管

和快速排序不同，每次只往一邊繼續，所以不需要遞迴，用迴圈就好。這叫快速選擇（quickselect），Hoare 在 1961 年發表快速排序時也一起發表了它（Algorithm 65: Find）。 平均每次範圍減半，比較次數約 n + n/2 + n/4 + … ≈ 2n，平均 O(n)；最壞情況和快速排序一樣是 O(n²)。

重點整理

• 快速排序：選基準、分割、遞迴排序兩邊；分割後基準就在最終位置，不需要合併
• Lomuto 分割：基準取 a[hi]，i 標出比基準小的區域的下一格，j 掃過每個元素，最後基準和 a[i] 交換；分割一個範圍比較 hi - lo 次
• 基準每次落在中間時是 O(n log n)；每次選到極端值時遞迴樹變成一條鏈，是 O(n²)，已排序的資料加上「取最後一個」正好是這種情況
• 改善：取中間元素、三數取中、隨機選基準；函式庫還會在遞迴太深時換方法
• 快速排序是原地排序，但不穩定
• 快速選擇每次只往答案所在的一邊繼續，平均 O(n) 找到第 k 小

下一課：計數排序與排序的極限。到目前為止的排序都靠「比較兩個元素」，下一課會看到比較排序為什麼不可能比 O(n log n) 更快，以及不用比較的排序法。