圖解快速排序：從哨兵劃分到遞歸征服的完整演示與 C 實現

核心思想：分治 + 原地劃分

快速排序平均 O(N log N)，最壞 O(N²)（已有序陣列）。核心步驟：

1. 選基準值（pivot，如首元素）。
2. 雙指針哨兵劃分：左指針找 >pivot，右指針找
3. 基準值歸位，左右子陣列遞歸排序。

圖解演示：陣列 [6,1,2,7,9,3,4,5,10,8]

第 1 輪：pivot=6

初始:  6  1  2  7  9  3  4  5 10  8
       ↑                          ↑
       i                          j
j 向左找 <6 → 停在 5 (索引 7)
i 向右找 >6 → 停在 7 (索引 3)
交換:  6  1  2  5  9  3  4  7 10  8
j 繼續找 <6 → 停在 4 (索引 6)
i 繼續找 >6 → 停在 9 (索引 4)
交換:  6  1  2  5  4  3  9  7 10  8
j 繼續找 <6 → 停在 3 (索引 5)
i 繼續找 >6 → i=j=5 相遇，停止
交換 pivot 與 arr[5]:  3  1  2  5  4  6  9  7 10  8
       ←左子陣列→  6  ←右子陣列→

遞歸處理左子陣列 [3,1,2,5,4] (pivot=3)

劃分後: 2  1  3  5  4
左 [2,1] → pivot=2 → [1,2]
右 [5,4] → pivot=5 → [4,5]

遞歸處理右子陣列 [9,7,10,8] (pivot=9)

劃分後: 8  7  9  10
左 [8,7] → [7,8]
右 [10]  → 基例

最終有序陣列

1  2  3  4  5  6  7  8  9  10

關鍵細節：為何右指針先動？

基準值選最左端時，必須先移動右指針。若左指針先動，可能越過基準值位置導致邏輯錯誤。右指針先找小於 pivot 的元素，確保交換後左側區域始終 ≤ pivot。

C 標準實現（教科書級）

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void quicksort(int a[], int left, int right) {
    if (left >= right) return;
    int i = left, j = right;
    int pivot = a[left];           // 基準值
    while (i < j) {
        while (i < j && a[j] >= pivot) j--; // 右指針先動
        while (i < j && a[i] <= pivot) i++; // 左指針後動
        if (i < j) {
            int t = a[i]; a[i] = a[j]; a[j] = t;
        }
    }
    a[left] = a[i]; a[i] = pivot;  // 基準值歸位
    quicksort(a, left, i - 1);
    quicksort(a, i + 1, right);
}

int main() {
    int n, a[101];
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    quicksort(a, 0, n - 1);
    for (int i = 0; i < n; ++i) printf("%d ", a[i]);
    return 0;
}

優化方向

• 三數取中法 選 pivot：mid = (left+right)/2，取 a[left], a[mid], a[right] 中位數。
• 小陣列切換插入排序：if (right-left < 16) insertion_sort(...)。
• 尾遞歸消除：迭代處理較大分區，遞歸處理較小分區，棧深度 O(log N)。
• 三向切分：處理大量重複鍵 (Dijkstra 荷蘭國旗問題)。

歷史軼事

Tony Hoare 1960 年發明，1962 年發表《Quicksort》。後設計 ALGOL 60 子集、發明 case 語句、1980 年獲圖靈獎。《算法導論》第 7 章專講。