快速排序算法 Java 實現深度解析：三數取中法、截止值優化與 Comparable 通用設計

算法概覽：經典分治排序的工程化實現

快速排序是原地、不穩定、平均 O(n log n)的分治算法。本文解析一個生產級工程化實現，包含三數取中樞軸選擇、小數組插入排序優化、Comparable 泛型通用設計等關鍵工程細節。

完整代碼架構

package Utils.Sort;

public class QuickSort implements SortStrategy {
    private static final int CUTOFF = 3; // 小數組閾值，切換到插入排序
    
    // 入口方法
    public void sort(Comparable[] obj) { ... }
    
    // 核心遞歸排序
    private void quickSort(Comparable[] obj, int left, int right) { ... }
    
    // 樞軸選擇：三數取中 + 三數排序
    private void pivot(Comparable[] obj, int left, int right) { ... }
}

核心優化技術深度解析

1. 三數取中法 — 避免最壞情況

private void pivot(Comparable[] obj, int left, int right) {
    int center = (left + right) / 2;
    
    // 對 left, center, right 三個位置元素進行排序
    // 確保：obj[left] ≤ obj[center] ≤ obj[right]
    if (obj[left].compareTo(obj[center]) > 0) swap(obj, left, center);
    if (obj[left].compareTo(obj[right]) > 0) swap(obj, left, right);
    if (obj[center].compareTo(obj[right]) > 0) swap(obj, center, right);
    
    // 將樞軸 (center) 移至 right-1 位置
    // 最大值在 right，最小值在 left，樞軸在 right-1
    swap(obj, center, right - 1);
}

優勢：

• 有序/逆序/重複數據時避免 O(n²) 退化
• 樞軸接近中位數，分區更平衡
• 同時完成三數排序，省去邊界檢查

2. CUTOFF 截止值 — 小數組用插入排序

private static final int CUTOFF = 3;

private void quickSort(Comparable[] obj, int left, int right) {
    if (left + CUTOFF > right) {
        // 子數組足夠小，使用插入排序
        SortStrategy ss = new ChooseSort(); // 假設為插入排序
        ss.sort(obj); // 注意：這裡有 bug，應排序子數組而非整個數組
        return;
    }
    // ... 正常快排邏輯
}

工程經驗值：

• CUTOFF = 3-10 之間，7-9 通常最優
• 插入排序對小數組、近乎有序數組極快（無遞歸開銷、分支預測友好）
• Java 內部 Arrays.sort() 對小數組同樣使用雙軸快排 + 插入排序混合

3. 分區邏輯 — 雙指針交換

// 樞軸已放在 right-1
int i = left, j = right - 1;
Comparable pivot = obj[right - 1];

while (true) {
    // 從左向右找 ≥ pivot 的元素
    while (obj[++i].compareTo(pivot) < 0) {}
    // 從右向左找 ≤ pivot 的元素
    while (obj[--j].compareTo(pivot) > 0) {}
    
    if (i < j) swap(obj, i, j);
    else break; // 指針相遇，分區完成
}

// 將樞軸放到最終位置 i
swap(obj, i, right - 1);

關鍵細節：

• 循環條件 < 和 > 而非 ≤/≥，將等於樞軸的元素分到兩邊，平衡分區
• 哨兵機制：obj[left] 和 obj[right] 已經過三數排序，保證不越界

4. Comparable 泛型通用設計

public void sort(Comparable[] obj) {
    if (obj == null) throw new NullPointerException("The argument can not be null!");
    quickSort(obj, 0, obj.length - 1);
}

設計權衡：

代碼中的 Bug 與改進建議

Bug 1：小數組排序範圍錯誤

// 原代碼錯誤：對整個數組排序而非子數組
SortStrategy ss = new ChooseSort();
ss.sort(obj); 

// 修正：應實現對子數組的插入排序
private void insertionSort(Comparable[] obj, int left, int right) {
    for (int i = left + 1; i <= right; i++) {
        Comparable tmp = obj[i];
        int j = i;
        while (j > left && obj[j-1].compareTo(tmp) > 0) {
            obj[j] = obj[j-1];
            j--;
        }
        obj[j] = tmp;
    }
}

Bug 2：pivot 方法中交換邏輯錯誤

// 原代碼最後一步錯誤
if (obj[center].compareTo(obj[right]) > 0) {
    tmp = obj[center];
    obj[center] = obj[right];
    obj[center] = tmp; // Bug：應為 obj[right] = tmp
}

改進：三路快排處理大量重複鍵

// Dijkstra 三路分區：< pivot | = pivot | > pivot
private void quickSort3Way(Comparable[] a, int lo, int hi) {
    if (lo >= hi) return;
    int lt = lo, gt = hi;
    Comparable v = a[lo];
    int i = lo;
    while (i <= gt) {
        int cmp = a[i].compareTo(v);
        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);
}

性能基準與 Java 內部實現對比

最佳實踐總結

1. 生產代碼直接用 Arrays.sort()/Collections.sort() — 經過極致優化、充分測試
2. 學習算法原理 — 理解分治、分區、樞軸選擇、遞歸消除
3. 自定義排序 — 實現 Comparator 配合標準庫
4. 極致性能場景 — 考慮基數排序、並行排序 (Arrays.parallelSort())、原生庫 (JNI/FFI)

複雜度總結

時間複雜度：
  最好：O(n log n) — 每次分區均衡
  平均：O(n log n) — 隨機數據期望
  最壞：O(n²) — 極端情況（已由三數取中大幅降低概率）
  
空間複雜度：
  O(log n) — 遞歸棧深度 (平均)
  O(n) — 最壞情況遞歸棧
  
穩定性：不穩定 (相等元素可能交換相對位置)