基于分治思想

1. 确定分界点
   直接取左边界q[l]、中间值q[(l+r)/2]、右边界q[r]、随机取
2. 调整区间
   把整个区间分成两半 小于等于分界点的的放在左边
3. 递归
   递归处理左右两段

一般的做法：

1. 开两个数组a[], b[]
2. 扫描q[l~r]，q[i]<=x则放到a[]，反之放到b[]
3. 把a[] b[]里面的数分别放到q[]里面

优雅的做法（不用单独开数组）：

1. 用两个指针i j，同时往中间走
2. i指到的如果小于等于X，就往后移动，大于X则停下来
3. j指到的如果大于等于X，就往前移动，小于X则停下来
4. 这个时候，交换i和j指向的数
5. 然后i j继续往中间走，直到相遇
6. 然后继续递归处理两边的部分

#include <iostream>
using namespace std;
const int N = 1e6 + 10;

int n;
int q[N];

void quick_sort(int q[], int l, int r) {
    if (l >= r) return;
    int x = q[(l+r)/2], i = l - 1, j = r + 1;
    while (i < j) {
        do i ++; while (q[i] < x);
        do j --; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i ++) scanf("%d", &q[i]);
    quick_sort(q, 0, n - 1);
    for (int i = 0; i < n; i ++) printf("%d ", q[i]);
    return 0;
}

注：我的x取q[l]的话会超时，取中点就accept了