Java 實現快速排序：分治法核心邏輯與完整代碼實戰

算法原理速覽

快速排序採用 分治法：選取基準元素，將數組分區為「小於基準」與「大於等於基準」兩個子數組，遞歸排序子數組。與歸併排序不同，快排 原地分區，無需額外合併步驟，空間複雜度僅 O(log n)（遞歸棧）。

• 最佳/平均：O(n log n)
• 最差：O(n²)（有序數組且固定選首/尾元素為基準）
• 優化策略：三數取中、隨機基準、小數組切換插入排序

分區邏輯圖解

基準值 = 陣列[end]
index = start - 1
for i = start to end-1:
    if 陣列[i] < 基準值:
        index++
        swap(陣列[index], 陣列[i])
swap(陣列[index+1], 陣列[end])  // 基準歸位
返回 index+1  // 基準最終位置

工具類 ArrayUtils

public class ArrayUtils {
    public static void printArray(int[] arr) {
        System.out.print("{");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if (i < arr.length - 1) System.out.print(", ");
        }
        System.out.println("}");
    }

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

快速排序核心實現

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

    private static void subQuickSort(int[] arr, int start, int end) {
        if (end - start < 1) return; // 區間長度 < 2

        int pivotIdx = partition(arr, start, end);

        // 遞歸左右子區間
        subQuickSort(arr, start, pivotIdx - 1);
        subQuickSort(arr, pivotIdx + 1, end);
    }

    private static int partition(int[] arr, int start, int end) {
        int pivot = arr[end];          // 選最後一個為基準
        int index = start - 1;         // 小於基準區域的右邊界

        for (int i = start; i < end; i++) {
            if (arr[i] < pivot) {
                index++;
                if (index != i) ArrayUtils.swap(arr, index, i);
            }
        }
        // 基準歸位
        if (index + 1 != end) ArrayUtils.swap(arr, index + 1, end);
        return index + 1;
    }

    public static void main(String[] args) {
        int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3};
        System.out.println("排序前:");
        ArrayUtils.printArray(arr);
        quickSort(arr);
        System.out.println("排序後:");
        ArrayUtils.printArray(arr);
    }
}

執行結果

排序前:
{9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3}
排序後:
{-3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

進階優化方向

1. 三數取中法：取首、中、末三者中位數作基準，極大降低最差情況概率
2. 隨機化基準：swap(arr, end, random.nextInt(end-start+1)+start)
3. 小區間切換插入排序：長度 < 10~20 時改用插入排序，減少遞歸開銷
4. 尾遞歸優化：對較大分區遞歸，較小分區迭代，限制棧深度
5. 三向切分：處理大量重複鍵（Dutch National Flag 問題）

總結

快速排序是面試與工程實踐的高頻考點。本文提供了 標準單向掃描分區 的清晰實現，代碼結構清晰、邊界處理嚴謹。理解 partition 過程中 index 邊界變量的語義，是掌握快排的關鍵。生產環境建議直接使用 Arrays.sort()（雙軸快排）或 Collections.sort()（TimSort），僅在教學、面試或特殊定製場景手寫實現。