快速排序原理與 Java 實現完整解析

算法概述

快速排序由 Tony Hoare 1960 年發明，平均時間複雜度 O(n log n)，原地排序、不穩定。因內層迴圈極簡且緊湊，實際表現通常優於同階合併排序、堆排序。

核心思想：分治法

1. 選取一個基準元素。
2. 一趟分區：將小於基準的元素移到左側，大於的移到右側，基準落在最終排序位置。
3. 遞迴對左右兩個子陣列重複上述步驟，直到區間長度 ≤ 1。

分區演示（以首元素為基準）

原始：3 5 2 6 2
基準：3

第1輪：
從右找 <3 → 2，交換 → 2 5 2 6 3
從左找 >3 → 5，交換 → 2 3 2 6 5
從右找 <3 → 2，交換 → 2 2 3 6 5
指標相遇，分區完成，基準 3 歸位

遞迴左半部 [2 2]、右半部 [6 5]
最終：2 2 3 5 6

Java 完整實現（含過程輸出）

public class QuickSort {
    private static int round = 0;

    public static void sort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

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

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[low];
        round++;
        System.out.printf("第 %d 輪分區 [%d-%d] 基準=%d%n", round, low, high, pivot);

        while (low < high) {
            while (low < high && arr[high] >= pivot) {
                System.out.printf("  右→左 找<%d high=%d%n", pivot, high);
                high--;
            }
            swap(arr, low, high);

            while (low < high && arr[low] <= pivot) {
                System.out.printf("  左→右 找>%d low=%d%n", pivot, low);
                low++;
            }
            swap(arr, low, high);
        }
        return low;
    }

    private static void swap(int[] arr, int i, int j) {
        if (i != j) {
            int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
            System.out.print("  交換後: ");
            Arrays.stream(arr).forEach(x -> System.out.print(x + " "));
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[] data = {3, 5, 2, 6, 2};
        System.out.println("原始: " + Arrays.toString(data));
        sort(data);
        System.out.println("結果: " + Arrays.toString(data));
    }
}

效能與優化建議

常見優化策略

1. 三數取中法：取首、中、尾三者中位數作基準，避免有序陣列退化。
2. 隨機基準：隨機選取元素與首位交換，期望時間複雜度穩定。
3. 小區間改用插入排序：長度 < 10~20 時切換，減少遞迴開銷。
4. 尾遞迴消除：對較大分區遞迴，較小分區迴圈處理，限制棧深度 O(log n)。
5. 三向切分：大量重複鍵時，將陣列分為 <、=、> 三段，避免重複元素重複比較。

總結

快速排序以優雅的分治思想、極少的額外空間、優異的快取局部性，成為工業界排序首選（如 JDK Arrays.sort() 基本類型使用雙軸快排）。理解其分區邏輯與優化方向，是演算法面試與高效能工程的必修課。