快速排序深度解析：為什麼快、Hoare 分區、三數取中、尾遞歸優化與插入排序混合

為什麼叫「快速」排序？

基於比較的排序下界為 Ω(n log n)。快速排序透過主元劃分，一次 O(n) 掃描就能確定 n/2 個元素「小於主元」、n/2 個「大於主元」，排除的排列可能性呈幾何級數下降，故常數極小、實測最快。

Hoare 分區 (原地、常數小)

雙指針從兩端向中間掃描，交換錯位元素，不固定主元最終位置，僅保證 [lo, p) ≤ [p, hi)。優點：等於主元的元素均勻分兩側，避免退化。

int* hoare(int* lo, int* hi, int n) { // [lo, hi)
    int pivot = lo[rand()%n]; // 隨機主元
    --lo;
    while (true) {
        while (*++lo < pivot);
        while (*--hi > pivot);
        if (lo < hi) swap(*lo, *hi);
        else return lo; // 回傳分界指標
    }
}

期望比較次數分析

任意相距 gap 的元素對，被比較機率 2/(gap+1)。總期望 ≈ 2n ln n + n。實測吻合。

三數取中優化主元

隨機取三元素取中位數作主元，機率密度 6x(1-x)，落在 [n/3, 2n/3] 機率 13/27 ≈ 48% (單純隨機僅 33%)，劃分更均衡。

int median3(int* a, int n) {
    int x = a[rand()%n], y = a[rand()%n], z = a[rand()%n];
    return max(min(x,y), min(max(x,y), z));
}

尾遞歸消除

遞歸處理較小分支，較大分支用迴圈繼續，遞歸深度 ≤ log n，省棧框架。

void quickSort(int* lo, int* hi) {
    while (hi - lo > 1) {
        int* p = hoare(lo, hi, hi-lo);
        if (p - lo < hi - p) { quickSort(lo, p); lo = p; }
        else { quickSort(p, hi); hi = p; }
    }
}

「葉子加粗」：小區間改用插入排序

遞歸到 FACTOR (建議 8~30) 以下停止，最後對近乎有序陣列跑一次插入排序 (哨兵優化)，消除大量遞歸開銷。

#define FACTOR 37
void insertionSort(int* a, int n) {
    for (int i=2;i<=n;++i) { int t=a[i]; int j=i-1; while(t

完整優化版性能

隨機主元 + Hoare + 尾遞歸 + 三數取中 + 插入排序混合。
實測 10⁶ 隨機整數 < 0.2s (G++ -O2)，穩定擊敗 std::sort。


總結
快速排序快在「分治獲得大量資訊」。工程上組合 隨機化主元 + Hoare 分區 + 三數取中 + 尾遞歸 + 小區間插入排序，即得高效、穩健、無遞歸爆棧風險的工業級實現。