C語言快速排序算法深度剖析：單樞軸分區、遞歸邏輯與優化變體

快速排序是「分治法」教科書級範例，平均 O(n log n)、原地排序、緩存友好。本文通過逐行註釋核心分區邏輯、可視化執行流程、複雜度分析、常見優化變體，建立完整的 QuickSort 內功心法。

核心代碼：Hoare 分區方案 (教學版)

void quick_sort(int a[], int n) {
    if (n <= 1) return;                    // 基線條件
    
    int i = 0, j = n - 1;
    int pivot = a[0];                      // 選首元素為樞軸
    
    while (i < j) {
        // 從右向左找 < pivot
        while (i < j && a[j] >= pivot) --j;
        if (i < j) a[i++] = a[j];          // 填左坑，i 右移
        
        // 從左向右找 > pivot
        while (i < j && a[i] <= pivot) ++i;
        if (i < j) a[j--] = a[i];          // 填右坑，j 左移
    }
    
    a[i] = pivot;                          // 樞軸歸位
    
    quick_sort(a, i);                      // 排左半部 [0, i-1]
    quick_sort(a + i + 1, n - i - 1);      // 排右半部 [i+1, n-1]
}

分區過程可視化：初始 [6, 9, 7, 3, 4], pivot=6

輪次  j指針動作          i指針動作          數組狀態           說明
--------------------------------------------------------------------
開始                                        [6, 9, 7, 3, 4]   pivot=6 存入變量
1     j=4: 4<6 ✓  → a[0]=4                  [4, 9, 7, 3, 4]   4 填左坑(索引0), i=1
      i=1: 9>6 ✓  → a[4]=9                  [4, 9, 7, 3, 9]   9 填右坑(索引4), j=3
2     j=3: 3<6 ✓  → a[1]=3                  [4, 3, 7, 3, 9]   3 填左坑(索引1), i=2
      i=2: 7>6 ✓  → a[3]=7                  [4, 3, 7, 7, 9]   7 填右坑(索引3), j=2
結束  i==j==2                               [4, 3, 6, 7, 9]   pivot 歸位索引2

關鍵洞察：坑位遞移

1. 首元素保存為 pivot，索引 0 成為第一個「坑」。
2. 右側找到較小值 → 填左坑 → 原位置成新坑。
3. 左側找到較大值 → 填右坑 → 原位置成新坑。
4. 坑位在左右交替遞移，最終 i==j 即為唯一坑位，放入 pivot。

複雜度與缺陷分析

五大工程優化變體

1. 三數取中選樞軸：mid = median(a[0], a[n/2], a[n-1])，大幅降低最壞情況概率。
2. 隨機化樞軸：swap(a[0], a[rand()%n])，期望 O(n log n)。
3. 小數組切換插入排序：if (n < 16) insertion_sort(a, n);，減少遞歸開銷。
4. 尾遞歸消除：遞歸排較大分區，迴圈處理較小分區，棧深度限制在 O(log n)。
5. 三向切分 (Dutch National Flag)：大量重複鍵值時 O(n)，將數組分為 < <pivot, =pivot, >pivot 三段。

標準庫 qsort 實戰

#include <stdlib.h>

int cmp_int(const void *a, const void *b) {
    int ia = *(const int*)a, ib = *(const int*)b;
    return (ia > ib) - (ia < ib);  // 避免溢出
}

int main() {
    int a[] = {6, 9, 7, 3, 4};
    size_t n = sizeof(a)/sizeof(a[0]);
    qsort(a, n, sizeof(int), cmp_int);
    // a 變為 [3, 4, 6, 7, 9]
}

手寫 vs 庫函數選擇指南

• 教學/面試/特殊約束：手寫，可控制分區細節、統計比較次數、插桩。
• 生產代碼：qsort / C++ std::sort / pdqsort (模式避免最壞情況)，經過工業級調優、處理邊界情況、編譯器內聯優化。

快速排序的精髓在於「以空間換時間的坑位遞移藝術」。理解分區不變量（左側 ≤ pivot ≤ 右側），掌握樞軸選擇策略，即可駕馭所有基於比較的分治排序變體。