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

背景介紹

快速排序由 Tony Hoare 於 1960 年代提出，屬於分治法經典演算法，平均時間複雜度 O(n log n)，且同階複雜度下實際運行速度最快，被譽為「二十世紀十大演算法」之一。

核心思想

1. 選取基準值（通常取首或尾元素）。
2. 將陣列分區：小於基準值放左側，大於放右側。
3. 對左右子陣列遞迴執行上述步驟，直到子陣列長度為 1。
4. 合併有序子陣列，整體有序。

兩大核心優勢

• 比較複用：元素一旦分區，後續比較僅在該分區內進行，避免重複比較（類似 KMP 演算法的前綴複用）。
• 分治法：將大規模問題分解為同構的小規模子問題（類似背包問題的動態規劃思想）。

動態演示

Java 實現程式碼

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] arrays = {1, 12, 2, 13, 3, 14, 4, 15, 5, 16, 17, 17, 177, 18, 8, 8, 19};
        new QuickSort().quickSort(arrays);
        System.out.println(Arrays.toString(arrays));
    }

    public void quickSort(int[] arrays) {
        subQuickSort(arrays, 0, arrays.length - 1);
    }

    private void subQuickSort(int[] arrays, int start, int end) {
        if (start >= end) return;
        int middleIndex = partition(arrays, start, end);
        subQuickSort(arrays, start, middleIndex - 1);
        subQuickSort(arrays, middleIndex + 1, end);
    }

    private int partition(int[] arrays, int start, int end) {
        int pivot = arrays[start];
        while (start < end) {
            while (arrays[end] >= pivot && start < end) end--;
            arrays[start] = arrays[end];
            while (arrays[start] <= pivot && start < end) start++;
            arrays[end] = arrays[start];
        }
        arrays[start] = pivot;
        return start;
    }
}

關鍵點解析

• partition 使用雙指針法，原地交換，空間複雜度 O(log n)（遞迴棧）。
• 基準值選取首元素，若資料近乎有序會退化為 O(n²)，生產環境建議採用「三數取中」或隨機基準值優化。
• 穩定性：快速排序為不穩定排序。