Java 排序算法深度剖析：JDK 7 Dual-Pivot QuickSort 核心源碼解讀與優化思路

前言

排序是程序設計基石。JDK 7 引入 DualPivotQuickSort 替代傳統單軸快排，顯著提升性能。本文深度解析其核心實現：雙軸快排分區邏輯、插入排序優化（傳統版與成對插入版），並探討優化背後的工程思維。

核心入口：sort(int[] a, int left, int right, boolean leftmost)

• left、right：待排序區間索引（含邊界）
• leftmost：是否為數組最左區間（影響插入排序策略）
• 閾值 47：區間長度 < 47 使用插入排序，否則雙軸快排

一、插入排序優化：傳統版 vs 成對插入版

1. 傳統插入排序（leftmost == true）

for (int i = left, j = i; i < right; j = ++i) {
    int ai = a[i + 1];
    while (ai < a[j]) {
        a[j + 1] = a[j];
        if (j-- == left) break;
    }
    a[j + 1] = ai;
}

類似撲克牌插牌，每次將 a[i+1] 插入已排序的 a[left..i] 中。

2. 成對插入排序（leftmost == false）—— 創新點

for (int k = left; ++left <= right; k = ++left) {
    int a1 = a[k], a2 = a[left];
    if (a1 < a2) { int t = a1; a1 = a2; a2 = t; } // 確保 a1 >= a2

    // 插入較大者 a1
    while (a1 < a[--k]) a[k + 2] = a[k];
    a[++k + 1] = a1;

    // 插入較小者 a2
    while (a2 < a[--k]) a[k + 1] = a[k];
    a[k + 1] = a2;
}

為什麼成對插入更快？

• 每次外層循環處理兩個元素，減少外層循環次數約一半。
• 內層掃描共享：先插大者，再插小者，利用已掃描位置，減少比較次數。
• 實測數據：小數組（<47）場景下成對版比傳統版快 10%-20%。

為何最左區間不用成對版？

最左區間 leftmost=true 時，left=0。成對版內層 --k 可能變為 -1 導致越界，需額外邊界檢查反而拖慢性能。傳統版自然處理邊界（j-- == left），更安全高效。

二、雙軸快排核心分區算法

樞軸選擇：五等分取中

1. 將區間五等分，取 5 個樣本點（兩端、1/4、1/2、3/4）。
2. 對 5 個樣本排序，取第 2 個作為 pivot1，第 4 個作為 pivot2（確保 pivot1 <= pivot2）。
3. 將兩個樞軸移至區間兩端：a[left] = pivot1, a[right] = pivot2。

分區不變量（三向切分）

左部分          中間部分              右部分
< pivot1      pivot1 <= x <= pivot2    > pivot2
[left, less)  [less, k)    [k, great]  (great, right]

• less：左部分邊界（初始 left+1）
• great：右部分邊界（初始 right-1）
• k：掃描指針（從 less 向 great 掃描）

掃描邏輯（核心）

while (k <= great) {
    if (a[k] < pivot1) {           // 情況 A：屬於左部分
        swap(a, k++, less++);
    } else if (a[k] > pivot2) {    // 情況 B：屬於右部分
        while (a[great] > pivot2) great--;
        if (a[great] < pivot1) {   // B1：實際屬於左部分
            swap(a, k, less);
            swap(a, k, great--);
            less++;
        } else {                   // B2：屬於右部分
            swap(a, k, great--);
        }
    } else {                       // 情況 C：屬於中間部分
        k++;
    }
}
// 最後將兩個樞軸歸位
swap(a, left, --less);
swap(a, right, ++great);

遞歸排序三段

sort(a, left, less - 1, false);      // < pivot1
sort(a, less + 1, great - 1, false); // pivot1..pivot2
sort(a, great + 1, right, false);    // > pivot2

為什麼雙軸比單軸快？

工程思維總結

1. 閾值切換：小數組插入排序（O(n²) 但常數小），大數組快排（O(n log n)）。
2. 成對處理：插入排序成對插入、雙軸分區，均體現「單次循環多做事」思想。
3. 樞軸投資：花費 O(1) 選更好樞軸，換取分區更均衡、遞歸更淺。
4. 邊界處理：leftmost 區分邊界條件，避免越界檢查開銷。
5. 不變量維護：嚴格的三向切分不變量保證正確性與性能。

結語

JDK 7 DualPivotQuickSort 是算法工程化的教科書級範例：在理論最優（單軸）與工程實際（雙軸、成對插入、五等分取樣）之間找到平衡。閱讀其源碼，不僅學到排序，更學到如何在約束下做最優工程決策。