快速排序 核心分區邏輯與 Java 手寫實現詳解

算法思想：分治 + 原地分區

• 選取基準值，將數組分為「≤基準」與「≥基準」兩區；
• 遞歸處理兩區，合併即有序；
• 原地操作，空間 O(log n) 遞歸棧，無額外數組開銷。

分區算法：雙指針單向掃描 (Lomuto 改良版)

public class QuickSort {
    /** 返回基準值最終位置 */
    public int partition(int[] a, int lo, int hi) {
        int pivot = a[hi];           // 選最右元素為基準
        int i = lo - 1;              // i 指向「≤基準區」尾部
        for (int j = lo; j < hi; j++) {
            if (a[j] <= pivot) {     // 發現小元素
                i++;
                swap(a, i, j);       // 換到「≤區」末尾
            }
        }
        swap(a, i + 1, hi);          // 基準值歸位
        return i + 1;
    }

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

    private 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[] arr = {4, 1, 5, 3, 7, 12, 65, 7};
        new QuickSort().sort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr)); // [1, 3, 4, 5, 7, 7, 12, 65]
    }
}

關鍵不變量

循環過程中始終保持：

• a[lo..i] ≤ pivot
• a[i+1..j-1] > pivot
• a[j..hi-1] 待檢查
• a[hi] = pivot

複雜度與優化方向

工程級優化

1. 三數取中法：mid = median(lo, (lo+hi)/2, hi) 選基準，極大降低最壞情況概率；
2. 小數組切換插入排序：長度 ≤ 15 直接插入排序，常數因子更小；
3. 尾遞歸消除：對較大分區遞歸，較小分區迭代，限制棧深度；
4. 三向切分：大量重複鍵時，分為 <、=、> 三區 (Dijkstra 荷蘭國旗)。

JDK 實現參考

• Arrays.sort(int[]) → 雙軸快速排序；
• Collections.sort(List) → TimSort (歸併+插入混合)。

手寫快排是理解「原地分區、不變量維護、遞歸邊界」的必修課，面試與造輪子雙通吃。