Java 快速排序演算法完整解析：遞迴實作、分區策略與效能優化

前言

快速排序是實務中最常用的 O(n log n) 內部排序演算法，以分治法將陣列分為「小於基準」與「大於基準」兩部分遞迴排序。本文深入解析單向掃描分區、雙向掃描、三向切分、隨機化基準選擇等核心技術，並提供生產級實作範本。

核心思想：分治法

1. 分割：選一基準值，將陣列重組為左側 ≤ 基準、右側 ≥ 基準
2. 解決：遞迴對左右子陣列排序
3. 合併：原地排序無需額外合併步驟

經典單向掃描分區

public class QuickSort {

    public static void quickSort(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int pivotIdx = partition(arr, left, right);
            quickSort(arr, left, pivotIdx - 1);
            quickSort(arr, pivotIdx + 1, right);
        }
    }

    /**
     * 單向掃描分區：以 left 為基準
     * 返回基準值最終位置
     */
    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        int i = left; // 小於 pivot 的區域右邊界
        
        for (int j = left + 1; j <= right; j++) {
            if (arr[j] < pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, left, i); // 將基準值放到正確位置
        return i;
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
    }
}

雙向掃描分區（Hoare Partition）

原始論文版本，雙指標向中間掃描，交換錯位元素，通常比單向掃描快：

private static int hoarePartition(int[] arr, int left, int right) {
    int pivot = arr[left];
    int i = left - 1, j = right + 1;
    
    while (true) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);
        if (i >= j) return j;
        swap(arr, i, j);
    }
}

// 遞迴呼叫需調整邊界
private static void quickSortHoare(int[] arr, int left, int right) {
    if (left < right) {
        int p = hoarePartition(arr, left, right);
        quickSortHoare(arr, left, p);
        quickSortHoare(arr, p + 1, right);
    }
}

關鍵優化技術

1. 隨機化基準選擇 - 避免最壞情況

private static final Random RANDOM = new Random();

private static int randomizedPartition(int[] arr, int left, int right) {
    int randIdx = left + RANDOM.nextInt(right - left + 1);
    swap(arr, left, randIdx); // 將隨機元素換到 left
    return partition(arr, left, right); // 或 hoarePartition
}

2. 三向切分 - 處理大量重複元素

Dijkstra 荷蘭國旗問題：將陣列分為 < pivot、= pivot、> pivot 三區，重複元素不再遞迴：

private static void quickSort3Way(int[] arr, int left, int right) {
    if (left >= right) return;
    
    int lt = left, gt = right;
    int pivot = arr[left];
    int i = left + 1;
    
    while (i <= gt) {
        int cmp = Integer.compare(arr[i], pivot);
        if (cmp < 0) {
            swap(arr, lt++, i++);
        } else if (cmp > 0) {
            swap(arr, i, gt--);
        } else {
            i++;
        }
    }
    // 現在 [left, lt-1] < pivot, [lt, gt] = pivot, [gt+1, right] > pivot
    quickSort3Way(arr, left, lt - 1);
    quickSort3Way(arr, gt + 1, right);
}

3. 小陣列切換插入排序

private static final int INSERTION_SORT_THRESHOLD = 16;

private static void quickSortOptimized(int[] arr, int left, int right) {
    if (right - left <= INSERTION_SORT_THRESHOLD) {
        insertionSort(arr, left, right);
        return;
    }
    // ... 其餘快排邏輯
}

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

4. 尾遞迴消除 - 減少堆疊深度

private static void quickSortTailRecursion(int[] arr, int left, int right) {
    while (left < right) {
        if (right - left <= INSERTION_SORT_THRESHOLD) {
            insertionSort(arr, left, right);
            return;
        }
        int p = randomizedPartition(arr, left, right);
        // 遞迴處理較小分區，迴圈處理較大分區
        if (p - left < right - p) {
            quickSortTailRecursion(arr, left, p - 1);
            left = p + 1;
        } else {
            quickSortTailRecursion(arr, p + 1, right);
            right = p - 1;
        }
    }
}

完整生產級實作

public final class QuickSort {
    private static final Random RANDOM = new Random();
    private static final int INSERTION_SORT_THRESHOLD = 16;

    private QuickSort() {}

    public static void sort(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        shuffle(arr); // 全域打亂，確保隨機化基準有效
        sort(arr, 0, arr.length - 1);
    }

    private static void sort(int[] arr, int left, int right) {
        while (left < right) {
            if (right - left <= INSERTION_SORT_THRESHOLD) {
                insertionSort(arr, left, right);
                return;
            }
            int p = partition(arr, left, right);
            if (p - left < right - p) {
                sort(arr, left, p - 1);
                left = p + 1;
            } else {
                sort(arr, p + 1, right);
                right = p - 1;
            }
        }
    }

    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        int i = left, j = right + 1;
        while (true) {
            while (arr[++i] < pivot) if (i == right) break;
            while (arr[--j] > pivot) if (j == left) break;
            if (i >= j) break;
            swap(arr, i, j);
        }
        swap(arr, left, j);
        return j;
    }

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

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
    }

    // Fisher-Yates 打亂
    private static void shuffle(int[] arr) {
        for (int i = arr.length - 1; i > 0; i--) {
            int r = RANDOM.nextInt(i + 1);
            swap(arr, i, r);
        }
    }
}

效能特性總結

與 JDK Arrays.sort 比較

• Arrays.sort(int[])：雙軸快速排序，針對基本型別優化，含三向切分、插入排序切換、打亂等所有優化。
• Arrays.sort(Object[])：TimSort (歸併+插入)，穩定、適應性強、部分有序極快。
• 結論：生產環境直接使用 Arrays.sort()；手寫快排僅為面試、教學、特殊定製需求（如外部排序、特定比較器優化）。

總結

快速排序透過隨機化基準、三向切分、小陣列插入排序、尾遞迴消除等工程化優化，可達到極高效能。理解分區邏輯與優化原理，不僅能應付面試，更能在需要自訂比較、外部排序、分散式排序等進階場景中靈活應用。