快速排序核心原理與 C 語言實現：從哨兵機制到遞歸分治全圖解

算法核心思想

快速排序採用分治策略：選基準數，將數組分為「小於基準」與「大於基準」兩部分，遞歸處理子數組。關鍵在於一次分區過程。

雙向哨兵分區圖解

以序列 6 1 2 7 9 3 4 5 10 8 為例，基準取首元素 6：

1. 哨兵 j 從右向左找 小於 6 的數（停在 5）
2. 哨兵 i 從左向右找 大於 6 的數（停在 7）
3. 交換兩者 → 6 1 2 5 9 3 4 7 10 8
4. 重複上述過程直到 i、j 相遇（位置 3）
5. 將基準 6 與相遇位置交換 → 3 1 2 5 4 6 9 7 10 8

此時 6 左側全 ≤6，右側全 ≥6，完成一次分區。

為什麼哨兵 j 必須先動？

因為基準位於最左端，若 i 先動會越過基準位置導致邏輯錯誤。j 先動保證相遇點左側元素均 ≤ 基準，可直接與基準交換。

C 標準實現

void quicksort(int left, int right) {
    if (left >= right) return;
    int i = left, j = right, temp = a[left];
    while (i != j) {
        while (a[j] >= temp && i < j) j--;
        while (a[i] <= temp && i < j) i++;
        if (i < j) swap(a[i], a[j]);
    }
    a[left] = a[i]; a[i] = temp;  // 基準歸位
    quicksort(left, i-1);
    quicksort(i+1, right);
}

性能特徵

• 平均時間 O(N log N)，最壞 O(N²)（有序數組）
• 空間 O(log N) 遞歸棧
• 不穩定排序
• 優化方向：隨機基準、三數取中、小區間插入排序

歷史軼事

由 C.A.R. Hoare 1960 年發明，後獲 1980 年圖靈獎。他還發明了 case 語句，影響 Pascal、C、Java 等語言。