Java 快速排序完整實戰：雙向掃描分區、隨機基準、三向切分與 Arrays.sort 內核解析

快速排序是面試必考、工程常用的 O(n log n) 平均複雜度排序。本文從經典 Hoare 分區、隨機化基準防退化、三向切分處理重複鍵、尾遞歸消除、到 JDK Arrays.sort 雙軸快排 (Dual-Pivot Quicksort) 內核，層層遞進給出生產級實作與效能調優指南。

經典 Hoare 分區 (雙向掃描)

/** 原地快排，返回基準最終索引 */
private static int partition(int[] a, int lo, int hi) {
    int pivot = a[lo + (hi - lo) / 2]; // 中位數作基準，減少有序陣列退化
    int i = lo - 1, j = hi + 1;
    while (true) {
        do { i++; } while (a[i] < pivot);
        do { j--; } while (a[j] > pivot);
        if (i >= j) return j;
        swap(a, i, j);
    }
}

public static void quickSort(int[] a, int lo, int hi) {
    if (lo < hi) {
        int p = partition(a, lo, hi);
        quickSort(a, lo, p);
        quickSort(a, p + 1, hi);
    }
}

關鍵優化技巧

三向切分快排 (處理重複鍵神器)

/** 將陣列分為 < pivot | = pivot | > pivot 三段 */
private static void quickSort3Way(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    int lt = lo, gt = hi, i = lo + 1;
    int pivot = a[lo]; // 已隨機交換到 lo
    while (i <= gt) {
        int cmp = Integer.compare(a[i], pivot);
        if (cmp < 0) swap(a, lt++, i++);
        else if (cmp > 0) swap(a, i, gt--);
        else i++;
    }
    quickSort3Way(a, lo, lt - 1);
    quickSort3Way(a, gt + 1, hi);
}

適用場景：用戶 ID 去重、日誌等級統計、基因序列分析等重複值極多的數據集。

JDK Arrays.sort 內核：雙軸快排 (Dual-Pivot Quicksort)

• 作者：Vladimir Yaroslavskiy (Java 7 引入)
• 核心思想：選兩個基準 pivot1 < pivot2，將陣列分為四段：< p1 | p1 ~ p2 | > p2
• 優勢：減少交換次數、提升緩存命中、平均比較次數從 2n ln n 降至 1.9n ln n
• 原始類型用雙軸快排，物件類型用 TimSort (歸併+插入，穩定排序)

完整生產級實作 (含所有優化)

public final class QuickSort {
    private static final int INSERTION_SORT_THRESHOLD = 47;
    private static final Random RANDOM = new Random();

    public static void sort(int[] a) {
        if (a == null || a.length < 2) return;
        sort(a, 0, a.length - 1);
    }

    private static void sort(int[] a, int lo, int hi) {
        // 尾遞歸消除循環
        while (hi - lo >= INSERTION_SORT_THRESHOLD) {
            // 隨機化基準
            swap(a, lo, lo + RANDOM.nextInt(hi - lo + 1));
            int[] pivots = partition3Way(a, lo, hi); // 返回 [lt, gt]
            // 先排較小分區，保證棧深度 O(log n)
            if (pivots[0] - lo < hi - pivots[1]) {
                sort(a, lo, pivots[0] - 1);
                lo = pivots[1] + 1;
            } else {
                sort(a, pivots[1] + 1, hi);
                hi = pivots[0] - 1;
            }
        }
        insertionSort(a, lo, hi);
    }

    /** 三向切分，返回 {lt, gt} 使 a[lo..lt-1] < p < a[gt+1..hi] */
    private static int[] partition3Way(int[] a, int lo, int hi) {
        int pivot = a[lo];
        int lt = lo, gt = hi, i = lo + 1;
        while (i <= gt) {
            int cmp = Integer.compare(a[i], pivot);
            if (cmp < 0) swap(a, lt++, i++);
            else if (cmp > 0) swap(a, i, gt--);
            else i++;
        }
        return new int[]{lt, gt};
    }

    private static void insertionSort(int[] a, int lo, int hi) {
        for (int i = lo + 1; i <= hi; i++) {
            int key = a[i], j = i - 1;
            while (j >= lo && a[j] > key) a[j + 1] = a[j--];
            a[j + 1] = key;
        }
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }
}

效能基準參考 (JMH, 10M 隨機整數)

避坑指南

• ❌ 基準固定選 a[lo] → 已排序陣列 O(n²)
• ❌ 遞歸未尾調用優化 → 深遞歸棧溢出
• ❌ 大量重複鍵未用三向切分 → 性能退化
• ✅ 生產代碼**直接用 Arrays.sort/Collections.sort**，JDK 內核經過極致調優
• ✅ 自定義比較器時實作 Comparator 而非繼承 Comparable，避免侵入領域模型

結語

快速排序的藝術在於「分區策略與遞歸控制的平衡」。理解 Hoare 分區、三向切分、雙軸快排的演進脈絡，能讓你在面試白板寫出無 Bug 代碼，也能在效能調優時知道為何 Arrays.sort 總是最快。記住：**除非極特殊場景，生產永遠用 JDK 內建排序。**