Java 快速排序演算法原理圖解與標準實作 (QuickSort)

快速排序 為原地、不穩定、平均 O(n log n) 的分治演算法。本文以「挖坑填數法」圖解分區過程，並提供標準遞迴實作與關鍵細節說明。

核心思想：分區

1. 選取 **基準值** 通常取 arr[low]。
2. 雙指標 left、right 從兩端向中間掃描：
   • right 左移尋找 < pivot 的元素，填入 left 坑位。
   • left 右移尋找 > pivot 的元素，填入 right 坑位。
   • 重複直到 left == right，將 pivot 填入最終坑位。
3. 分區完成：左側 ≤ pivot ≤ 右側。
4. 遞迴處理左右子陣列，直到區間長度 ≤ 1。

分區過程圖解 (陣列: 37 40 38 42 461 5 7 9 12)

初始: [37] 40 38 42 461 5 7 9 12  (pivot=37, left=0, right=8)
right→ 找到 12<37:  [12] 40 38 42 461 5 7 9 [12]  left=1
left→  找到 40>37:  [12] [40] 38 42 461 5 7 9 40  right=7
right→ 找到 9<37:   [12] 9  38 42 461 5 7 [9]  40  left=2
left→  找到 38>37:  [12] 9  [38] 42 461 5 7 38 40  right=6
right→ 找到 7<37:   [12] 9  7  42 461 5 [7]  38 40  left=3
left→  找到 42>37:  [12] 9  7  [42] 461 5 42  38 40  right=5
right→ 找到 5<37:   [12] 9  7  5  461 [5] 42  38 40  left=4
left→  找到 461>37: [12] 9  7  5  [461] 461 42  38 40  right=4
left==right=4:     [12] 9  7  5  [37] 461 42  38 40  ← 分區完成

標準 Java 實作

public class QuickSort {
    /** 公開入口 */
    public static void sort(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        quickSort(arr, 0, arr.length - 1);
    }

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

    /** 單向掃描分區 (Lomuto 方案，較易理解) */
    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[right]; // 選最右為基準
        int i = left - 1;       // 小於區域邊界
        for (int j = left; j < right; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, right);
        return i + 1;
    }

    /** 雙向掃描分區 (Hoare 方案，交換次數較少) */
    private static int partitionHoare(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;
        return i;
    }

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

    // 測試
    public static void main(String[] args) {
        int[] a = {37, 40, 38, 42, 461, 5, 7, 9, 12};
        sort(a);
        System.out.println(Arrays.toString(a)); // [5, 7, 9, 12, 37, 38, 40, 42, 461]
    }
}

關鍵優化策略

複雜度總結

• 時間：平均 O(n log n)、最壞 O(n²) (已排序+固定基準)、最佳 O(n log n)。
• 空間：遞迴棧 O(log n) (平均)、O(n) (最壞)。
• 穩定性：不穩定 (相等元素可能交換順序)。
• 原地：是，僅需常數額外空間。

1. 上一篇文章： Java List 去重複元素的三種高效寫法 (ArrayList 實戰)
2. 下一篇文章： Java Callable 與 Future 非同步任務完整實戰指南

Java 相關知識

Spring 事務管理進階：打破迷思，掌握核心真相（上）

DAO 與事務管理：非綁定關係 常見迷思：「用 Spring

Java 理論與實踐：善用 JMX 監控與管理應用程式

有多少次您凝視著運行中的應用程式，自問：「它到底在做什麼？為

Java 加密技術（六）：DSA 數字簽名算法——非對稱加密的高級驗證實現

DSA（Digital Signature Algorith

使用 Java Service Wrapper 將 Java 程式註冊為系統服務

工具簡介 Java Service Wrapper 提供跨平