快速排序深度解析：分治邏輯、分區過程圖解與 Java 高性能實現

快速排序是計算機科學中最經典的 原地排序 算法，JDK Arrays.sort()（基本類型）底層即採用雙軸快排。本文從分治思想、分區不變量、代碼實現、性能優化四個維度徹底講透 QuickSort。

一、核心思想：分治法

1. Divide（分）： 選取基準元素，將數組劃分為「≤ 基準」與「≥ 基準」兩個子區間。
2. Conquer（治）： 遞歸對兩個子區間進行快排。
3. Combine（合）： 原地排序無需合併，遞歸返回即有序。

二、分區算法詳解（Lomuto vs Hoare）

1. Lomuto 分區（教科書常見，易理解）

選最後一個元素為基準，維護索引 i 指向「≤ 基準區間」尾部。遍歷 j，發現 arr[j] ≤ pivot 時 swap(++i, j)。最後 swap(i+1, end) 將基準歸位。

// Lomuto 分區：返回基準最終索引
private static int partitionLomuto(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;
}

缺點： 大量重複元素時退化為 O(n²)；交換次數較多。

2. Hoare 分區（原版，性能更強）

雙指針 i=lo-1, j=hi+1 向中間掃描，i 找 >pivot，j 找 i >= j。返回 j 作為分界點。

// Hoare 分區：返回分界索引 j（左區間 ≤ pivot，右區間 ≥ pivot）
private static int partitionHoare(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);
    }
}

優勢： 交換次數少 ~30%，對重複元素友好，遞歸深度更淺。

三、完整可運行實現（Hoare + 三數取中 + 尾遞歸優化）

public final class QuickSort {

    private QuickSort() {}

    /** 公開入口 */
    public static void sort(int[] a) {
        if (a == null || a.length < 2) return;
        quickSort(a, 0, a.length - 1);
    }

    /** 核心遞歸：尾遞歸優化，遞歸深度 O(log n) */
    private static void quickSort(int[] a, int lo, int hi) {
        while (lo < hi) {
            // 小區間改用插入排序（閾值經驗值 16~32）
            if (hi - lo < 16) {
                insertionSort(a, lo, hi);
                return;
            }
            int p = partition(a, lo, hi);
            // 先遞歸較短分支，尾遞歸消除較長分支棧幀
            if (p - lo < hi - p) {
                quickSort(a, lo, p);
                lo = p + 1;
            } else {
                quickSort(a, p + 1, hi);
                hi = p;
            }
        }
    }

    /** Hoare 分區 + 三數取中基準 */
    private static int partition(int[] a, int lo, int hi) {
        int mid = lo + (hi - lo) / 2;
        // 三數取中：a[lo], a[mid], a[hi] 排序，中位數作基準
        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);
        int pivot = a[mid];

        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);
        }
    }

    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;
    }

    // 測試
    public static void main(String[] args) {
        int[] data = {11, 213, 134, 44, 77, 78, 23, 43, 999, 0, -5, 44};
        sort(data);
        System.out.println(Arrays.toString(data));
    }
}

四、複雜度與穩定性分析

五、工程落地避坑指南

• 基準選擇： 三數取中或隨機基準，極大降低惡意構造數據觸發 O(n²) 風險。
• 小區間切換： n < 16 時改用插入排序，減少函數調用開銷。
• 尾遞歸消除： 手動轉為 while 迴圈，保證棧深度 O(log n)，防止 StackOverflowError。
• 大量重複鍵： 極端場景改用 三向切分快排，將數組分為 < pivot | = pivot | > pivot 三段，JDK Arrays.sort() 內部即採用此策略。
• 並行化： JDK 8+ 可用 Arrays.parallelSort()，基於 ForkJoinPool 多核加速。

面試加分點： 能手寫 Hoare 分區、解釋為什麼返回 j 而非 i、說清尾遞歸優化原理、知道 JDK 實際用的是 Dual-Pivot Quicksort（雙軸快排）並簡述其分區邏輯。