圖解快速排序：Java 實現 Partition 過程逐步演示

快排核心：雙指針分區 (Hoare 方案)

以 8 位運動員身高排序為例：[181, 169, 187, 172, 163, 191, 189, 182] (A-H)。

第一輪分區圖解

基準 pivot = 181 (A)
初始: i=0(L), j=7(R), pivot=181, empty=0

步驟 1: j 從右向左找 < 181
  j=7: 182 ≥ 181 → j=6
  j=6: 189 ≥ 181 → j=5
  j=5: 191 ≥ 181 → j=4
  j=4: 163 < 181 找到！a[empty]=a[4] → a[0]=163, empty=4
  陣列: [163, 169, 187, 172, 163, 191, 189, 182] (empty=4)

步驟 2: i 從左向右找 > 181
  i=1: 169 ≤ 181 → i=2
  i=2: 187 > 181 找到！a[empty]=a[2] → a[4]=187, empty=2
  陣列: [163, 169, 187, 172, 187, 191, 189, 182] (empty=2)

步驟 3: j 繼續找 < 181
  j=3: 172 < 181 找到！a[empty]=a[3] → a[2]=172, empty=3
  陣列: [163, 169, 172, 172, 187, 191, 189, 182] (empty=3)

步驟 4: i 繼續找 > 181
  i=3: i==j 相遇，停止

步驟 5: 基準歸位
  a[empty]=pivot → a[3]=181
  陣列: [163, 169, 172, 181, 187, 191, 189, 182]

分區完成: 左側 [163,169,172] 都 < 181，右側 [187,191,189,182] 都 > 181

遞歸排序子陣列

左半部 [163,169,172]: 已有序 (或繼續遞歸)
右半部 [187,191,189,182]:
  pivot=187 → 分區後 [182] [187] [191,189]
  [191,189] → pivot=191 → [189] [191]
最終有序: [163, 169, 172, 181, 182, 187, 189, 191]

Java 完整實現 (Hoare 分區 + 空位法)

public class QuickSortVisual {
    
    public static void quickSort(int[] a) { quickSort(a, 0, a.length - 1); }
    
    private static void quickSort(int[] a, int lo, int hi) {
        if (lo >= hi) return;
        
        int i = lo, j = hi;
        int pivot = a[lo];
        int empty = lo; // 空位索引
        
        while (i < j) {
            // 右指針找小於 pivot
            while (i < j && pivot <= a[j]) j--;
            if (i < j) a[empty] = a[empty = j]; // 填空位、更新空位
            
            // 左指針找大於 pivot
            while (i < j && a[i] <= pivot) i++;
            if (i < j) a[empty] = a[empty = i]; // 填空位、更新空位
        }
        
        a[empty] = pivot; // 基準歸位
        
        // 遞歸排序左右
        quickSort(a, lo, empty - 1);
        quickSort(a, empty + 1, hi);
    }
    
    public static void main(String[] args) {
        int[] heights = {181, 169, 187, 172, 163, 191, 189, 182};
        System.out.println("排序前: " + Arrays.toString(heights));
        quickSort(heights);
        System.out.println("排序後: " + Arrays.toString(heights));
    }
}

另一種分區：單向掃描 (Lomuto 方案)

// 選最後元素為 pivot，單指針 i 維護小於區域邊界
private static int partitionLomuto(int[] a, int lo, int hi) {
    int pivot = a[hi];
    int i = lo - 1;
    for (int j = lo; j < hi; j++) {
        if (a[j] <= pivot) swap(a, ++i, j);
    }
    swap(a, i + 1, hi);
    return i + 1;
}

特點：代碼更簡潔、易理解，但交換次數較多、不穩定、退化性能略差。

關鍵圖解總結

常見錯誤與修正

教學建議

1. 先在紙上手動跑 5-8 個元素的完整過程。
2. 用 IDE Debug 斷點觀察 i、j、empty、陣列內容變化。
3. 對比 Hoare vs Lomuto：交換次數、代碼複雜度、穩定性、極端情況表現。
4. 理解為什麼「三數取中」能改善有序數組性能。

1. 上一篇文章： 外觀模式 詳解：為複雜子系統提供統一高層介面
2. 下一篇文章： Java synchronized 關鍵字深度解析：用法、鎖機制與常見陷阱

Java 相關知識

Hibernate 從入門到精通（十）：多對多單向關聯映射詳解

前言 繼一對多雙向關聯後，進入多對多映射。本文解析多對多單向

5 月 23 日 Java 生日快樂：從 Oak 到全球開發語言的 28 年演進史

Java 誕生緣起 Java 是一種跨平台、面向物件的程

J2EE 1.3 中移除 Service Locator 模式的資源快取機制

緒論 Service Locator 是 J2EE 應用中常

Java 1.4 焦點子系統重構：FocusTraversalPolicy 深度解析與自定義實戰

焦點管理演進史 早期 Java 依賴本地窗口管理器處理焦點，