快速排序與分治法演算法深度解析與 Java 實作優化

分治法：快速排序的理論基石

分治法是解決複雜問題的經典策略，核心思想是「分而治之」：將大問題分解為若干規模較小、結構相同的子問題，遞歸求解子問題，再合併結果。快速排序正是分治法在排序領域的典型應用。

分區操作核心邏輯

分區是快速排序的關鍵步驟，目標是選擇一個基準值，將陣列重新排列使得：

• 左側所有元素 ≤ 基準值
• 右側所有元素 ≥ 基準值
• 基準值位於最終正確位置

基礎分區實作

public int partitionBasic(int left, int right) {
    if (left < 0 || left >= n || right < 0 || right >= n) return -1;
    
    int pivot = arr[left]; // 選最左元素為基準
    int i = left, j = right;
    
    while (i < j) {
        while (i < j && arr[j] >= pivot) j--;
        if (i < j) arr[i++] = arr[j];
        
        while (i < j && arr[i] <= pivot) i++;
        if (i < j) arr[j--] = arr[i];
    }
    arr[i] = pivot;
    return i; // 返回基準值最終位置
}

快速排序遞歸框架

public void quickSort(int left, int right) {
    if (right - left < 1) return; // 終止條件：區間長度 < 2
    
    int pivotIndex = partitionBasic(left, right);
    quickSort(left, pivotIndex - 1);  // 排序左子區
    quickSort(pivotIndex + 1, right); // 排序右子區
}

效能陷阱與優化策略

問題：最壞情況 O(n²)

當陣列已有序或逆序，且每次選最左/最右元素為基準時，分區極度不平衡，退化為 O(n²)。

優化一：三數取中法選基準

private int medianOfThree(int left, int right) {
    int mid = (left + right) >>> 1;
    
    // 確保 arr[left] <= arr[mid] <= arr[right]
    if (arr[left] > arr[mid]) swap(left, mid);
    if (arr[left] > arr[right]) swap(left, right);
    if (arr[mid] > arr[right]) swap(mid, right);
    
    // 將中位數移到 left 位置作為基準
    swap(mid, left);
    return arr[left];
}

優化二：小區間切換插入排序

private static final int INSERTION_SORT_THRESHOLD = 16;

public void quickSortOptimized(int left, int right) {
    if (right - left < INSERTION_SORT_THRESHOLD) {
        insertionSort(left, right);
        return;
    }
    // ... 正常快速排序邏輯
}

優化三：尾遞歸消除

public void quickSortTailRecursion(int left, int right) {
    while (right - left >= INSERTION_SORT_THRESHOLD) {
        int pivotIndex = partitionOptimized(left, right);
        
        // 遞歸處理較小區間，迴圈處理較大區間（消除尾遞歸）
        if (pivotIndex - left < right - pivotIndex) {
            quickSortTailRecursion(left, pivotIndex - 1);
            left = pivotIndex + 1;
        } else {
            quickSortTailRecursion(pivotIndex + 1, right);
            right = pivotIndex - 1;
        }
    }
    insertionSort(left, right);
}

完整優化版測試結果

初始陣列: 95 40 64 18 78 23 73 84 40
排序後:   18 23 40 40 64 73 78 84 95

時間複雜度總結

* 極低機率觸發，工程上可視為 O(n log n)

工程實踐建議

• 生產環境優先使用 Arrays.sort()（雙軸快速排序）或 Collections.sort()（TimSort）
• 自行實作時務必加入隨機化或三數取中
• 大數據量考慮並行排序 Arrays.parallelSort()
• 避免在遞歸深度過大時發生 StackOverflowError