Java 快速排序演算法實作與程式碼解析

快速排序簡介

快速排序是一種高效的分治法排序演算法，平均時間複雜度為 O(n log n)，廣泛應用於各類程式語言的標準庫中。本文提供 Java 實作範例並解析核心邏輯。

程式碼實作

public class QuickSort {
    public static int[] data = { 9, 8, 7, 4, 1, 12, 15, 63, 15, 20 };

    public static void quickSort(int left, int right) {
        if (left >= right) return; // 終止條件

        int i = left;
        int j = right;
        int pivot = data[(left + right) / 2]; // 選取中間元素為基準值
        int temp;

        while (i <= j) {
            // 從左向右找第一個大於基準值的元素
            while (data[i] < pivot) i++;
            // 從右向左找第一個小於基準值的元素
            while (data[j] > pivot) j--;

            if (i <= j) {
                // 交換兩元素
                temp = data[i];
                data[i] = data[j];
                data[j] = temp;
                i++;
                j--;
            }
        }

        // 遞迴處理左半部與右半部
        if (left < j) quickSort(left, j);
        if (i < right) quickSort(i, right);
    }

    public static void main(String[] args) {
        System.out.println("排序前：");
        printArray(data);

        quickSort(0, data.length - 1);

        System.out.println("\n排序後：");
        printArray(data);
    }

    private static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

核心邏輯解析

1. 基準值選取：範例採用中間元素 data[(left + right) / 2]，可減少已排序陣列產生最差情況（O(n²)）的機率。實務上也可採用「三數取中」或隨機選取。
2. 分區過程：雙指標 i、j 向中間掃描，將小於基準值的元素移至左側，大於的移至右側，完成一次分區後基準值位置確定。
3. 遞迴終止：當 left >= right 時代表子陣列長度為 0 或 1，無需排序直接返回。

效能與優化建議

• 小陣列優化：當子陣列長度小於閾值（如 10~20）時，改用插入排序可減少遞迴開銷。
• 尾遞迴優化：對較大的分區使用遞迴，較小的用迴圈，降低堆疊深度。
• 三向切分：針對大量重複鍵值的陣列，採用 Dutch National Flag 演算法將陣列分為 <、=、> 三區，顯著提升效能。

總結

快速排序是原地排序、不穩定的高效演算法。理解其分治邏輯與分區過程是掌握進階排序技巧的基礎。實際開發中建議優先使用 Arrays.sort() 或 Collections.sort()，它們採用雙軸快速排序與 TimSort 混合策略，效能更優。