資料結構：C語言快速排序兩大經典版本（雙向掃描與單向掃描）

版本一：教科書雙向掃描（Hoare 分區）

void QuickSort(int left, int right) {
    if (left >= right) return;
    int pivot = a[left];
    int i = left, j = right;
    while (i != j) {
        while (a[j] >= pivot && i < j) j--;
        while (a[i] <= pivot && i < j) i++;
        if (i < j) { int t=a[i]; a[i]=a[j]; a[j]=t; }
    }
    a[left] = a[i]; a[i] = pivot;
    QuickSort(left, i-1);
    QuickSort(i+1, right);
}

特點：雙指針向中間收斂，基準值最終歸位 i。

版本二：單向掃描（Lomuto 分區）

void quickSort2(int x[], int l, int r) {
    if (l >= r) return;
    int m = l;
    for (int i = l+1; i <= r; i++)
        if (x[i] < x[l]) { m++; int t=x[m]; x[m]=x[i]; x[i]=t; }
    int t = x[l]; x[l] = x[m]; x[m] = t;
    quickSort2(x, l, m-1);
    quickSort2(x, m+1, r);
}

void swap2(int &a, int &b) {   // C++ 參考，C 用指標
    if (&a == &b) return;
    a ^= b; b ^= a; a ^= b;
}

特點：單指針 m 維護「小於基準區」邊界，代碼更簡潔。

比較

進階優化

1. 隨機化基準值 / 三數取中。
2. 小區間改用插入排序。
3. 尾遞迴消除 / 非遞迴棧實現。