快速排序思想是基于分治策略（分而治之）把一个序列分两个子序列，然后递归地处理两个子序列。

具体步骤为：

1. 挑选出一个基准值 pivot （一般取当前序列中间值）。

2. 将所有小于 pivot 的元素放在左边，所有大于等于 pivot 的元素放在右边。此时 pivot 所在位置确定为最终位置。

3. 递归处理左右两个子序列（重复 1， 2 操作）。

#include<iostream>

using namespace std;

const int N = 200010;
int q[N];

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;//递归边界
    int i = l - 1, j = r + 1, x = q[(l + r) >> 1];//基准值 x
    while (i < j)//步骤 2
    {
        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);
    //只能取 [l, j], [j + 1, r]
    //或 [l, i - 1], [i, r],此时需要改动基准值 x = q[(l + r + 1) >> 1];
}
int main()
{
    int n;
    cin >> n;

    for (int i = 0; i < n; ++i) cin >> q[i];

    quick_sort(q, 0, n - 1);

    for (int i = 0; i < n; ++i) printf("%d ", q[i]);

    return 0;
}