快速排序：激進的領袖

演算法背後的故事：排隊的邏輯

想像妳正試圖在一家嘈雜的派對上，按身高為 100 個人排隊。 妳可以一個一個比對，但那會耗費一整晚的時間。

1959 年，Tony Hoare 在莫斯科研究機器翻譯，需要對俄語單詞進行排序。他意識到，如果他隨便選一個人——基準點 (Pivot)——並問其他人：「妳比這個人矮還是高？」，他就能迅速將人群分為兩組。

接著，他告訴「矮個子」組在她們內部進行同樣的操作，同時也讓「高個子」組這樣做。當每一個小小組都排好序時，整個派對就變成了一條完美的直線。

他將其命名為 快速排序 (QuickSort)，因為與當時那些緩慢、謹慎的演算法相比，她的移動速度快得驚人，具有爆發力。

為什麼需要它？

快速排序是幾乎所有程式語言（如 C++ 的 sort() 或 Java 對原始類型的排序）的預設選擇。

• 速度： 在實作中，由於她與電腦硬體（快取友好性）的交互方式，她通常比其他 $O(N \log N)$ 演算法更快。
• 原地排序： 她不需要巨大的臨時倉庫；她直接在原有的陣地上完成排序。

演算法是如何「思考」的

這個演算法像是一個果斷的領袖，透過遞迴來委派權力。

1. 選拔 (Pivot)： 它挑選一個元素作為「標準」。 專家提示： 選到一個極端的基準點（比如最小的那個）會讓她變慢。一個好的領袖應該是「平庸/平均」的。

2. 大分裂 (分區)： 它橫掃整個列表，將所有比基準點小的元素移到左邊，大的移到右邊。一輪橫掃後，基準點就回到了她的終身歸宿，永遠不需要再移動了。

3. 遞迴委派： 領袖隨後指向左邊和右邊說：「現在，妳們兩邊按同樣的方法處理自己。」

這個過程不斷重複，直到每個元素都成了自己的基準點，秩序就此達成。

工程決策：阿基里斯之踵

快速排序很快，但她不穩定。

• 穩定性： 如果妳有兩個價格相同的「蘋果」，快速排序可能會交換她們的相對順序。如果妳需要保持相等元素的原始順序，請使用 歸併排序。
• 最壞情況： 如果妳總是選到最差的基準點，速度會退化到 $O(N^2)$。現代工程師使用「三數取中」或隨機基準點來防止這種情況。

實作參考 (Python)

def quicksort(arr):
    # 基礎情況：單個元素已經是排序好的
    if len(arr) <= 1:
        return arr
    
    # 1. 選拔：挑選中間的元素作為領袖 (Pivot)
    pivot = arr[len(arr) // 2]
    
    # 2. 大分裂
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    # 3. 遞迴委派
    return quicksort(left) + middle + quicksort(right)

# 注意：以上是「美學版」代碼。
# 生產環境通常使用「原地交換」版本以節省記憶體。

小結

快速排序教會我們：領導力在於劃分。透過做出一個堅定的決策（基準點）並委派剩餘任務，我們能在記錄時間內解決宏大問題。它提醒我們，有時候，為了讓世界團結在一起，妳必須先知道如何將她分開。