笔记：
快速排序基于分治思想。
步骤如下：
1. 确定分界点$x$，$x=(l+r)/2$。
2. 调整区间（重点）：把区间状态修改为：$x$左边的数小于$x$，右边的数大于$x$。
3. 递归处理左右两端，注意处理$l>=r$的边界情况，要$return$。

如何处理第二步重点？
1. 设i在$l-1$位置，j在$r+1$位置。
2. 移动指针$i$，直到碰到一个大于$x$的数。
3. 移动指针$j$，直到碰到一个小于$x$的数。
4. $swap(a_i,a_j)$
5. 重复执行$2$~$4$步，直到$ij$相遇。

代码：

#include <bits/stdc++.h>
using namespace std;
int n, a[100010];
void quick_sort(int l, int r) {
    if (l >= r) return;
    int mid = l + r >> 1;
    int i = l - 1, j = r + 1, x = a[mid];
    while (i < j) {
        do i++; while (a[i] < x);
        do j--; while (a[j] > x);
        if (i < j) swap(a[i], a[j]);
    }
    quick_sort(l, j);
    quick_sort(j + 1, r);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    quick_sort(1, n);
    for (int i = 1; i <= n; i++) cout << a[i] << " ";
    return 0;
}

总结：还是sort快亿点