Java 快速排序優化全攻略：從基礎實現到三向切分、尾遞歸消除

基礎快排實現 (Lomuto 分區)

public class QuickSortBasic {
    public static void sort(int[] a) { sort(a, 0, a.length - 1); }
    
    private static void sort(int[] a, int lo, int hi) {
        if (lo >= hi) return;
        int p = partition(a, lo, hi);
        sort(a, lo, p - 1);
        sort(a, p + 1, hi);
    }
    
    private static int partition(int[] a, int lo, int hi) {
        int pivot = a[hi]; // 選最後元素
        int i = lo - 1;
        for (int j = lo; j < hi; j++) {
            if (a[j] <= pivot) swap(a, ++i, j);
        }
        swap(a, i + 1, hi);
        return i + 1;
    }
    private static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
}

三大經典優化

1. 小數組切換插入排序 (閾值 7-15)

private static final int INSERTION_SORT_THRESHOLD = 15;

private static void sort(int[] a, int lo, int hi) {
    if (hi - lo <= INSERTION_SORT_THRESHOLD) {
        insertionSort(a, lo, hi);
        return;
    }
    // ... 原快排邏輯
}

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

2. 三數取中法選 Pivot (避免有序數組退化)

private static int medianOfThree(int[] a, int lo, int hi) {
    int mid = lo + (hi - lo) / 2;
    // 排序 lo, mid, hi 三者，中位數放到 hi-1
    if (a[lo] > a[mid]) swap(a, lo, mid);
    if (a[lo] > a[hi]) swap(a, lo, hi);
    if (a[mid] > a[hi]) swap(a, mid, hi);
    swap(a, mid, hi - 1); // 基準值移至 hi-1
    return a[hi - 1];
}

// 分區時調用
int pivot = medianOfThree(a, lo, hi);
// 掃描範圍縮為 [lo+1, hi-2]

3. 三向切分 (Dijkstra 荷蘭國旗問題) — 大量重複鍵神器

private static void sort3Way(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    
    int lt = lo, i = lo + 1, gt = hi;
    int v = a[lo]; // 基準值
    
    while (i <= gt) {
        if (a[i] < v) swap(a, lt++, i++);
        else if (a[i] > v) swap(a, i, gt--);
        else i++;
    }
    
    sort3Way(a, lo, lt - 1);   // 遞歸 < 區
    sort3Way(a, gt + 1, hi);   // 遞歸 > 區
    // = 區已有序，無需遞歸
}

效果：重複鍵多時從 O(n²) 降為 O(n)，接近線性。

進階優化：尾遞歸消除 + 顯式棧

public static void sortIterative(int[] a) {
    // 手動棧模擬遞歸，先處理小分區，限制棧深度 O(log n)
    int[] stack = new int[64]; // 足夠大 (2^64 元素)
    int top = -1;
    stack[++top] = 0;
    stack[++top] = a.length - 1;
    
    while (top >= 0) {
        int hi = stack[top--];
        int lo = stack[top--];
        
        if (lo >= hi) continue;
        if (hi - lo <= INSERTION_SORT_THRESHOLD) {
            insertionSort(a, lo, hi);
            continue;
        }
        
        int p = partition3Way(a, lo, hi); // 返回 lt, gt 需封裝對象或雙值
        
        // 先壓入大分區，再壓入小分區 → 小分區優先處理 → 棧深度 O(log n)
        if (p.gt - p.gt > p.lt - lo) { // 簡化判斷
            push(stack, lo, p.lt - 1);
            push(stack, p.gt + 1, hi);
        } else {
            push(stack, p.gt + 1, hi);
            push(stack, lo, p.lt - 1);
        }
    }
}

private static void push(int[] stack, int lo, int hi) {
    if (lo < hi) { stack[++top] = lo; stack[++top] = hi; }
}

隨機化 Pivot (期望 O(n log n))

private static final Random RAND = new Random();

private static int randomPartition(int[] a, int lo, int hi) {
    int randIdx = lo + RAND.nextInt(hi - lo + 1);
    swap(a, randIdx, hi); // 隨機元素換到末尾
    return partition(a, lo, hi);
}

完整生產級實現綜合版

public class QuickSortPro {
    private static final int INSERTION_THRESHOLD = 15;
    private static final Random RAND = new Random();
    
    public static void sort(int[] a) {
        if (a == null || a.length <= 1) return;
        shuffle(a); // 全局隨機化，消除輸入相關性
        sort(a, 0, a.length - 1);
    }
    
    private static void sort(int[] a, int lo, int hi) {
        while (lo < hi) { // 尾遞歸消除：大分區用循環，小分區遞歸
            if (hi - lo <= INSERTION_THRESHOLD) {
                insertionSort(a, lo, hi);
                return;
            }
            
            int[] bounds = partition3Way(a, lo, hi); // [lt, gt]
            
            // 先處理小分區 (遞歸)，大分區留給 while 循環 (尾遞歸消除)
            if (bounds[0] - lo < hi - bounds[1]) {
                sort(a, lo, bounds[0] - 1);
                lo = bounds[1] + 1; // 尾遞歸消除：更新 lo 繼續循環
            } else {
                sort(a, bounds[1] + 1, hi);
                hi = bounds[0] - 1;
            }
        }
    }
    
    // 三向切分返回 [lt, gt]
    private static int[] partition3Way(int[] a, int lo, int hi) {
        int v = a[lo];
        int lt = lo, i = lo + 1, gt = hi;
        while (i <= gt) {
            if (a[i] < v) swap(a, lt++, i++);
            else if (a[i] > v) swap(a, i, gt--);
            else i++;
        }
        return new int[]{lt, gt};
    }
    
    private static void shuffle(int[] a) {
        for (int i = a.length - 1; i > 0; i--) swap(a, i, RAND.nextInt(i + 1));
    }
    // insertionSort, swap 同前
}

性能對比表 (100萬隨機整數)

避坑指南

• 遞歸棧溢出：極端情況棧深 O(n) → 用尾遞歸消除/顯式棧/隨機化。
• 基本類型數組用 Arrays.sort：雙軸快排比單軸快 10-20%。
• 物件數組用 Arrays.sort：TimSort 穩定、適應性強 (部分有序極快)。
• 並行排序：多核 CPU Arrays.parallelSort() 可獲 2-4x 加速。
• 不要重複造輪子：除非教學/面試/極特殊約束 (嵌入式/實時系統)，生產代碼直接用 JDK。

1. 上一篇文章： 迭代器模式 Java 實現：統一遍歷介面、封裝聚合內部結構
2. 下一篇文章： 外觀模式 詳解：為複雜子系統提供統一高層介面

Java 相關知識

Struts 1 自定義類型轉換器：解決 java.util.Date 綁定失敗的兩種註冊方式

問題現場 表單提交 java.util.Date 字段時，S

從零手寫依賴注入容器：基於 XML 配置與反射機制的實現

前言：模仿 Spring 核心 IoC 容器 本文示範如何從

Servlet 動態生成圖文合一圖片：解決網頁標題頻繁變更痛點

痛點分析 網頁設計常用圖片作為欄位標題（如「熱點聚焦」），但

JVM 調優總結（四）：垃圾回收面臨的三大核心問題

問題一：如何區分垃圾？ 引用計數法（已廢棄） 對象頭記錄引