快速排序算法深度解析：三種 Partition 實現、三數取中優化、插入排序切換與完整複雜度證明

快速排序算法深度解析

快速排序採用分治思想，核心在於 partition 切分函數。本文對比三種切分實現，引入三數取中與小數組插入排序優化，並給出完整時間/空間複雜度數學推導。

核心思想

1. 選取樞軸
2. 切分：左側 ≤ 樞軸 ≤ 右側
3. 遞歸處理左右子數組，直到長度 ≤ 1

三種 Partition 實現對比

1. 雙向掃描交換法

《Algorithms 4th》經典實現：left 向右找 > 樞軸，right 向左找 < 樞軸，交換，直到指針相交，最後將樞軸交換到 right 位置。

private static int partition(int[] a, int lo, int hi) {
    int left = lo, right = hi + 1, pivot = a[lo];
    while (true) {
        while (a[++left] <= pivot) if (left == hi) break;
        while (a[--right] >= pivot) if (right == lo) break;
        if (left >= right) break;
        swap(a, left, right);
    }
    swap(a, lo, right);
    return right;
}

• 優點：交換次數少，易理解
• 缺點：訪問數組次數較多

2. 單向掃描 + 存儲索引法

storIndex 指向最後一個 < 樞軸的元素，掃描到 < 樞軸則 swap(++storIndex, i)。

private static int partition(int[] a, int lo, int hi) {
    int storIndex = lo;
    for (int i = lo + 1; i <= hi; i++)
        if (a[i] < a[lo]) swap(a, i, ++storIndex);
    swap(a, lo, storIndex);
    return storIndex;
}

• 缺點：平均交換次數是方法一的 2 倍以上，不推薦

3. 填坑法

先保存樞軸，右向左找小填左坑，左向右找大填右坑，最後坑位放回樞軸。

private static int partition(int[] a, int lo, int hi) {
    int pivot = a[lo];
    while (lo < hi) {
        while (lo < hi && a[hi] >= pivot) hi--;
        a[lo] = a[hi];
        while (lo < hi && a[lo] <= pivot) lo++;
        a[hi] = a[lo];
    }
    a[lo] = pivot;
    return lo;
}

• 優點：訪問數組次數最少，代碼緊湊
• 缺點：理解稍難

優化策略

1. 三數取中選樞軸

private static int median3(int[] a, int lo, int mid, int hi) {
    if (a[lo] > a[mid]) swap(a, lo, mid);
    if (a[mid] > a[hi]) swap(a, mid, hi);
    if (a[lo] > a[mid]) swap(a, lo, mid);
    swap(a, mid, hi - 1); // 樞軸藏到 hi-1
    return a[hi - 1];
}

避免有序/逆序數組退化為 O(n²)。可進一步擴展為五數取中（九數取中）。

2. 小數組切換插入排序

private static final int CUTOFF = 10;
if (hi - lo <= CUTOFF) { insertionSort(a, lo, hi); return; }

插入排序對小數組常數因子更小，避免遞歸開銷。

完整優化版代碼

public class QuickSort {
    private static final int CUTOFF = 10;
    public static void sort(int[] a) { sort(a, 0, a.length - 1); }
    private static void sort(int[] a, int lo, int hi) {
        if (lo + CUTOFF >= hi) { insertionSort(a, lo, hi); return; }
        if (lo >= hi) return;
        int m = median3(a, lo, lo + (hi - lo) / 2, hi);
        swap(a, m, lo);
        int p = partition(a, lo, hi);
        sort(a, lo, p - 1);
        sort(a, p + 1, hi);
    }
    // partition 使用填坑法...
    private static void insertionSort(int[] a, int lo, int hi) { ... }
}

複雜度數學證明

遞歸關係

T(N) = T(i) + T(N-i-1) + cN，i 為左子數組大小，cN 為切分掃描開銷。

最壞情況 O(N²)

樞軸恆為極值，i=0：T(N) = T(N-1) + cN = c(N + N-1 + ... + 2) = cN(N+1)/2 = O(N²)

最好情況 O(N log N)

樞軸恆為中位數，i = N/2：T(N) = 2T(N/2) + cN，主定理得 O(N log N)。

平均情況 O(N log N)

假設樞軸位置均勻分佈：
T(N) = (1/N) Σ [T(k) + T(N-k-1)] + cN
經數學歸納法證明 T(N) ~ 2cN ln N = O(N log N)。

空間複雜度

• 最好/平均：遞歸深度 log₂N，棧幀 O(log N)
• 最壞：遞歸深度 N，棧幀 O(N²)（極小概率，打亂數組可避免）

穩定性

不穩定：兩處破壞相對順序
1. 雙向掃描交換時，相等元素可能被交換
2. 最後將樞軸交換到 right，若左側有相等元素，順序顛倒