《算法（第四版）》排序專題：快速排序原理、實現與三大優化

編輯：關於C語言

《算法（第四版）》排序專題：快速排序原理、實現與三大優化

1. 核心概念

快速排序：原地排序（僅需 O(log n) 棧空間），平均時間 O(N log N)，最壞 O(N²)。屬分治法經典實現（歸並排序也是分治，但歸並先遞歸後合併，快排先切分後遞歸）。

2. 基本思想

選一個基準值（pivot），將數組劃分為「≤pivot」和「≥pivot」兩部分，pivot 歸位。對兩部分遞歸排序，整個數組自然有序。

3. 詳細示例

數組：`6 1 2 7 9 3 4 5 10 8`，選首元素 6 為基準。
雙指針 `i`(左) `j`(右) 掃描：
- `j` 左移找 `<6`（停於 5），`i` 右移找 `>6`（停於 7），交換 → `6 1 2 5 9 3 4 7 10 8`
- `j` 找 4，`i` 找 9，交換 → `6 1 2 5 4 3 9 7 10 8`
- `j` 找 3，`i` 與 `j` 相遇於 3。交換基準 6 與 3 → `3 1 2 5 4 6 9 7 10 8`
6 歸位，左側 `<6`，右側 `>6`。遞歸處理左右子數組，最終有序。

雙指針劃分過程

4. 標準實現

public class QuickSort {
    public static void sort(Comparable[] a) {
        // StdRandom.shuffle(a); // 洗牌消除輸入依賴
        sort(a, 0, a.length - 1);
    }
    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) return;
        int j = partition(a, lo, hi);
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }
    private static int partition(Comparable[] a, int lo, int hi) {
        int i = lo, j = hi + 1;
        Comparable v = a[lo];
        while (true) {
            while (less(a[++i], v)) if (i == hi) break;
            while (less(v, a[--j])) if (j == lo) break;
            if (i >= j) break;
            exch(a, i, j);
        }
        exch(a, lo, j);
        return j;
    }
}

5. 關鍵細節（必須處理）

重復元素處理： 左掃描停於 `≥v`，右掃描停於 `≤v`，避免大量重復元素導致劃分極不平衡（退化 O(N²)）。
遞歸終止條件： `hi <= lo` 確保不再劃分單元素/空區間，防止死遞歸。

6. 三大工程優化

6.1 小數組切換插入排序

小數組（≤15 元素）插入排序更快。修改終止條件：

if (hi <= lo + M) { Insertion.sort(a, lo, hi); return; } // M 取 5~15

6.2 三取樣切分

取子數組首、中、末三元素中位數作基準，劃分更均衡。可將取樣元素移至末尾作哨兵，省去邊界檢查。

6.3 三向切分（熵最優排序）

針對大量重復鍵值：將數組劃分為 `v` 三段。
維護指針 `lt`、`i`、`gt`：
- `a[lo..lt-1] < v`
- `a[lt..i-1] = v`
- `a[i..gt]` 待定
- `a[gt+1..hi] > v`
掃描 `i`：
`a[i] < v` → `exch(lt++, i++)`
`a[i] > v` → `exch(i, gt--)`
`a[i] == v` → `i++`
遞歸排序 `v` 部分，`=v` 部分已有序。
荷蘭國旗問題 經典應用。

private static void sort3way(Comparable[] a, int lo, int hi) {
    if (hi <= lo) return;
    int lt = lo, i = lo + 1, gt = hi;
    Comparable v = a[lo];
    while (i <= gt) {
        int cmp = a[i].compareTo(v);
        if (cmp < 0)      exch(a, lt++, i++);
        else if (cmp > 0) exch(a, i, gt--);
        else              i++;
    }
    sort3way(a, lo, lt - 1);
    sort3way(a, gt + 1, hi);
}