快速排序算法模板

#include <bits/stdc++.h>
using namespace std;

void quickSort(int a[], int lo, int hi) {
    if (lo >= hi) return;
    int pivot = a[lo + (hi - lo) / 2];  // 选中间元素作基准
    int i = lo, j = hi;
    while (i <= j) {
        while (a[i] < pivot) i++;
        while (a[j] > pivot) j--;
        if (i <= j) { swap(a[i], a[j]); i++; j--; }
    }
    if (lo < j) quickSort(a, lo, j);
    if (i < hi) quickSort(a, i, hi);
}

int main() {
    int a[] = {5, 3, 8, 1, 2, 7, 4, 6};
    quickSort(a, 0, 7);
    for (int x : a) cout << x << " ";  // 1 2 3 4 5 6 7 8
    return 0;
}

📖 要点说明

• 平均 O(n log n)，最坏 O(n²)（已排序时）
• 选中间元素作基准可避免最坏情况
• 不稳定排序

⚠️ 常见错误

• 基准选第一个元素，已排序数据退化到 O(n²)
• 分区后递归边界搞错
• i<=j 写成 i<j 导致死循环