快速排序由 C.A.R. Hoare 1962 年提出，屬於分治法典型應用。核心三步走：
分區過程中邊界處理最易出錯，本文深度剖析兩種經典分區寫法。
核心邏輯：將基準值「挖出」形成坑位，右指針找小於基準值的填左坑，左指針找大於基準值的填右坑，交替進行直到指針相遇，最後將基準值填入最終坑位。
public class QuickSortPit {
/** 單次分區，返回基準值最終位置 */
static int partition(int[] arr, int left, int right) {
int pivot = arr[left]; // 選最左為基準
int l = left, r = right;
while (l < r) {
// 1. 從右向左找 < pivot
while (l < r && arr[r] >= pivot) r--;
if (l < r) arr[l++] = arr[r]; // 填左坑，左指針右移
// 2. 從左向右找 > pivot
while (l < r && arr[l] <= pivot) l++;
if (l < r) arr[r--] = arr[l]; // 填右坑，右指針左移
}
arr[l] = pivot; // 基準值歸位
return l;
}
static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int pivotIdx = partition(arr, left, right);
quickSort(arr, left, pivotIdx - 1);
quickSort(arr, pivotIdx + 1, right);
}
}
public static void main(String[] args) {
int[] data = {72, 6, 57, 88, 60, 42, 83, 73, 48, 85};
System.out.println("原始：" + Arrays.toString(data));
quickSort(data, 0, data.length - 1);
System.out.println("排序：" + Arrays.toString(data));
}
}
初始: [72, 6, 57, 88, 60, 42, 83, 73, 48, 85] 坑位=0(72) 右找48<72 → 填坑0: [48, 6, 57, 88, 60, 42, 83, 73, 48, 85] 新坑位=8 左找88>72 → 填坑8: [48, 6, 57, 88, 60, 42, 83, 73, 88, 85] 新坑位=3 右找60<72 → 填坑3: [48, 6, 57, 60, 60, 42, 83, 73, 88, 85] 新坑位=4 左找83>72 → 填坑4: [48, 6, 57, 60, 83, 42, 83, 73, 88, 85] 新坑位=5 右找42<72 → 填坑5: [48, 6, 57, 60, 83, 42, 83, 73, 88, 85] 新坑位=5 指針相遇於5 → 填入基準值72: [48, 6, 57, 60, 83, 72, 83, 73, 88, 85] 左側全<72，右側全>72，分區完成
核心邏輯：左指針 low 從左向右找 > pivot，右指針 high 從右向左找 < pivot，兩指針未交錯時交換元素，最後將基準值與 high 位置交換。
public class QuickSortTwoPointer {
static void quickSort(int[] arr, int left, int right) {
if (left >= right) return;
int pivot = arr[left];
int low = left + 1, high = right;
while (true) {
while (low <= high && arr[low] <= pivot) low++;
while (low <= high && arr[high] >= pivot) high--;
if (low > high) break;
swap(arr, low, high);
}
swap(arr, left, high); // 基準值歸位
quickSort(arr, left, high - 1);
quickSort(arr, high + 1, right);
}
static void swap(int[] arr, int i, int j) {
int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
}
}
| 維度 | 挖坑填數法 | 雙指針交換法 |
|---|---|---|
| 賦值次數 | 每次移動 1 次賦值 | 每次交換 3 次賦值 |
| 程式碼直觀度 | 邏輯連貫，易理解 | 經典教科書寫法，通用性強 |
| 邊界條件處理 | 需注意 l | 需注意 low<=high 循環條件 |
| 適用場景 | 元素移動成本高（大對象） | 通用場景，標準庫多採用 |
mid = (left+right)/2，取 arr[left]、arr[mid]、arr[right] 中位數，避免有序陣列退化 O(n²)swap(arr, left, random(left, right))，期望時間複雜度穩定 O(n log n)「挖坑填數」邏輯更貼近分區本質，賦值次數少，適合大對象排序；「雙指針交換」是教科書標準寫法，通用性強。掌握兩者邊界細節，並結合三數取中、小區間插入排序等優化，即可寫出生產級快速排序。建議動手在紙上模擬 5-6 個元素的分區過程，深度內化指針移動邏輯。
