快速排序完整實現指南：分治邏輯、基準選擇、遞歸優化與工程級測試策略

前言

快速排序是原地、分治、不穩定、平均 O(n log n) 的排序王者。本文從核心分區邏輯、基準選擇策略、遞歸尾調用優化、隨機化防退化、三向切分處理重複鍵、工程級測試用例設計**六個維度，提供可直接用於生產/面試的 C 語言完整實現。

一、核心分區算法：Hoare vs Lomuto

推薦：工程採用 Hoare 分區 + 隨機化基準 + 三向切分 綜合方案。

二、標準 Hoare 分區實現 (含隨機基準)

#include 
#include 

// 隨機交換基準到首位，防止有序/逆序數組退化
static void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

static int partition_hoare(int arr[], int low, int high) {
    // 隨機選取基準並交換到 low
    swap(&arr[low], &arr[low + rand() % (high - low + 1)]);
    int pivot = arr[low];
    int i = low - 1, j = high + 1;
    while (1) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);
        if (i >= j) return j; // 分界點 j
        swap(&arr[i], &arr[j]);
    }
}

void quick_sort(int arr[], int n) {
    if (!arr || n <= 1) return;
    srand((unsigned)time(NULL)); // 僅主調用處種子一次
    _quick_sort(arr, 0, n - 1);
}

static void _quick_sort(int arr[], int low, int high) {
    if (low >= high) return;
    int p = partition_hoare(arr, low, high);
    _quick_sort(arr, low, p);
    _quick_sort(arr, p + 1, high);
}

三、三大工程優化：尾遞歸消除 + 小數組插入排序 + 三向切分

1. 尾遞歸消除 (手動展開大分區)

遞歸深度最壞 O(n)，平均 O(log n)。總是遞歸處理較小分區，大分區用循環迭代，保證棧深度 ≤ O(log n)。

static void _quick_sort_opt(int arr[], int low, int high) {
    while (low < high) {
        // 小數組閾值切換插入排序 (通常 10~20)
        if (high - low < 16) { insertion_sort(arr, low, high); return; }
        
        int p = partition_hoare(arr, low, high);
        // 遞歸處理較小側，迭代處理較大側
        if (p - low < high - p) {
            _quick_sort_opt(arr, low, p);
            low = p + 1; // 尾遞歸 → 循環
        } else {
            _quick_sort_opt(arr, p + 1, high);
            high = p;
        }
    }
}

2. 三向切分 — 解決大量重複鍵退化

將數組分為 < pivot、= pivot、> pivot 三段，等於區不再遞歸。荷蘭國旗算法 (Dijkstra)。

static void partition_3way(int arr[], int low, int high, int *lt, int *gt) {
    swap(&arr[low], &arr[low + rand() % (high - low + 1)]);
    int pivot = arr[low];
    int i = low, lt_idx = low, gt_idx = high;
    while (i <= gt_idx) {
        if (arr[i] < pivot) swap(&arr[lt_idx++], &arr[i++]);
        else if (arr[i] > pivot) swap(&arr[i], &arr[gt_idx--]);
        else i++;
    }
    *lt = lt_idx; *gt = gt_idx; // 返回等於區邊界 [lt, gt]
}

3. 小數組插入排序閾值

元素 ≤ 16 時插入排序比快排更快 (無函數調用開銷、緩存局部性好)。

四、完整工程級代碼骨架

void quick_sort_production(int arr[], int n) {
    if (!arr || n <= 1) return;
    srand((unsigned)time(NULL));
    _quick_sort_3way(arr, 0, n - 1);
}

static void _quick_sort_3way(int arr[], int low, int high) {
    while (high - low >= 16) {
        int lt, gt;
        partition_3way(arr, low, high, <, >);
        // 遞歸較小側
        if (lt - low < high - gt) {
            _quick_sort_3way(arr, low, lt - 1);
            low = gt + 1;
        } else {
            _quick_sort_3way(arr, gt + 1, high);
            high = lt - 1;
        }
    }
    insertion_sort(arr, low, high); // 收尾
}

五、測試用例設計矩陣 (白盒覆蓋)

六、常見面試追問與回答要點

1. 為什麼不穩定？ 分區交換可能改變相等元素相對順序 (如 Hoare 分區 swap(arr[i], arr[j]) 跨越中間相等元素)。
2. 最壞 O(n²) 怎麼避免？ 隨機化基準 (期望 O(n log n))、中位數三數取中、IntroSort (超深度切換堆排序)。
3. 外部排序怎麼用快排？ 內存分塊快排生成有序段，歸併階段用 K 路歸併 (敗者樹/優先隊列)。
4. 並行快排？ 分區後左右獨立，投入線程池；任務粒度控制 (如 < 1000 元素不再分發)。

結語

快速排序的工程化核心在於「隨機化消除最壞案、三向切分征服重複鍵、尾遞歸限制棧深、小數組插入排序減常數」。掌握 Hoare 分區雙指針邏輯與三向切分荷蘭國旗算法，配合完整測試矩陣，即可在面試白板編程與系統級組件開發中游刃有餘。標準庫 std::sort (Introsort) 正是此思想的集大成者。