Java 快速排序分區邏輯深度解析：賦值 vs 交換

代碼片段

// 版本 A：賦值法（教科書常見）
array[low] = array[high];
...
array[high] = array[low];

// 版本 B：交換法（直觀理解）
swap(array[low], array[high]);

為什麼賦值法正確且高效

快速排序分區核心：將基準值 key 存入變量，騰出 array[low] 位置。之後：

1. high 向左找 < 的元素，直接覆蓋 到 array[low]
2. low 向右找 >key 的元素，直接覆蓋 到 array[high]
3. 循環結束時 low == high，將 key 寫入該位置

關鍵洞察

• 第一次賦值時 array[low] 已被 key 保存，原值無用
• 後續每次賦值都是將「另一側找到的合格元素」移動到「空出的坑位」
• 整個過程只有 2 次賦值/次循環，交換法需 3 次賦值/次循環（臨時變量）

驗證：修改為交換法後的行為

// 修改後
swap(array[low], array[high]);
// 第一次循環：array[low] 始終等於 key，交換無意義
// 第二次循環：array[high] 始終等於 key，交換無意義

因此教科書版本採用賦值法，避免無效交換，性能更優。

完整分區代碼

int partition(int[] arr, int low, int high) {
    int key = arr[low];
    while (low < high) {
        while (low < high && arr[high] >= key) high--;
        arr[low] = arr[high]; // 坑位填補
        while (low < high && arr[low] <= key) low++;
        arr[high] = arr[low]; // 另一側坑位填補
    }
    arr[low] = key; // 基準歸位
    return low;
}