Java 快速排序演算法完整實作與步驟圖解

快速排序：分治法的經典實作

快速排序是效能優異的原地排序演算法，平均時間複雜度 O(n log n)。本文提供完整 Java 實作、分區邏輯解析與執行過程追蹤。

核心步驟

1. 選取基準值（pivot），通常取陣列第一個元素。
2. 分區：將小於 pivot 的元素移至左側，大於者移至右側。
3. 遞迴對左右子陣列重複上述步驟，直到子陣列長度 ≤ 1。

Java 完整程式碼

package com.itheima;

public class QuickSortDemo {
    static int count = 0;

    public static void main(String[] args) {
        int[] values = {5, 4, 8, 3, 7, 2, 1, 9, 0, 6};
        System.out.println("原始陣列：" + java.util.Arrays.toString(values));
        quickSort(values, 0, values.length - 1);
        System.out.println("排序結果：" + java.util.Arrays.toString(values));
    }

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

    public static int partition(int[] arr, int left, int right) {
        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;
        printStep(arr, ++count);
        return i;
    }

    private static void printStep(int[] arr, int step) {
        System.out.printf("第 %2d 次分區後：%s%n", step, java.util.Arrays.toString(arr));
    }
}

執行過程追蹤（節錄）

原始陣列：[5, 4, 8, 3, 7, 2, 1, 9, 0, 6]
第  1 次分區後：[0, 4, 1, 3, 2, 5, 7, 9, 8, 6]
第  2 次分區後：[0, 2, 1, 3, 4, 5, 7, 9, 8, 6]
...
第 13 次分區後：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
排序結果：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

效能與優化重點

• 基準值選取策略影響效能（三數取中、隨機 pivot 可避免最壞 O(n²)）。
• 小陣列（< 10）可改用插入排序提升常數因子。
• 尾端遞迴優化可減少堆疊深度。