事实就是，快排太难了2333（笑

快排就是分治嘛，以一个数为边界，分两边，一直分，一直排，排到最后一层有效的两个数，顺序也就出来了。
边界确实有点恶心，好吧，一年前的我也没有把题解吃透吧hh
我们要做的就是使得分治得两个区间内部不一定有序，但总体满足一个性质，左边的数<= x,右边的数>=x,这个x理论上取序列中哪个值都是可以的。但是取的不好也会影响递归的层数,往下看吧（笑
理论上如果我们每次以区间中间的数为边界进行递归，那最多就logn次，分成的同一层的区间,第一层是[0, n - 1], 第二层是[0, n / 2 - 1], [n / 2, n - 1], 第三层就是四份嘛，每一份在扫面过程中至多扫描n/(2 ^ t - 1) 次, t为层数，所以每一层还是O(n)的时间复杂度，总的时间复杂度是O(nlogn)
至于O(n^2)，还是得模拟啊2333，恰好找到的数是最大的话，就会嘎嘎递归了
那就来模拟一下吧（笑
10个数
49 59 88 37 98 97 68 54 31 3
按照模板int x = a[l + r >> 1];取中间的数，会取到98
这是最大的数，所有的数都是小于等于它的
do ll++; while(a[ll] < x);
do rr--; while(a[rr] > x);
ll指针会一直走到98所在的位置，数组下标为4，而rr指针因为do while循环动一次指到3，数组下标为9，这一轮循环结束后
49 59 88 37 3 97 68 54 31 98
quick_sort(a, l, rr), quick_sort(a, rr + 1, r);
可以发现rr和r相等，都是9，所以没有实现分治的目标。
进入下一次递归，rr指针至少左移一个位置，因为上一次循环已经把最大的移到最右边了，如果找的的数又是剩余的数（除去98最大的），那rr指针只会左移一个单位。这样又等价于没实现分治，这样就会有n次“递归”，时间复杂度就是O(n^2)

#include<iostream>
using namespace std;
const int N = 100010;
int a[N], b[N], c[N];
int n, cnt;
void quick_sort(int a[], int l, int r){
    if(l >= r) return;
    int ll = l - 1, rr = r + 1;
    int x = a[l + r >> 1];
    int cnt1 = 0, cnt2 = 0, cnt3 = 0;
    for(int i = l; i <= r; i++){
        if(a[i] > x) c[cnt2++] = a[i]; // b, c为辅助数组嘛
        else if(a[i] < x) b[cnt1++] = a[i];
        else cnt3++;
    }
    int k = l;
    for(int i = 0; i < cnt1; i++)
        a[k++] = b[i];
    for(int i = 0; i < cnt3; i++)
        a[k++] = x;
    for(int i = 0; i < cnt2; i++)
        a[k++] = c[i]; 
    if(cnt3 > 1) cnt3 /= 2; //保证分的区间至少有一个数，否则陷入死循环，边界问题出不来了
                            //如果分的一段区间是相同的数，我们要保证能继续分治下去
                            //为什么取中间的数呢，分治嘛，这样分的少，hack数据，都是同一个数
                            //可以用下面注释的代码打打表看看
    quick_sort(a, l, l + cnt1 - 1 + cnt3), quick_sort(a, l + cnt1 + cnt3 , r);
    //cnt++;  
    //cout<<l<<" "<<l+ cnt1 + cnt3 - 1<<" "<<r<<" "<<x<<endl;
    // for(int i = l; i <= r; i++)
    //     cout<<a[i]<<" ";
    // cout<<endl;
    // if(cnt < 10)
    // quick_sort(a, l, l + cnt1 - 1 + cnt3), quick_sort(a, l + cnt1 + cnt3, r);
}
int main(){
    cin>>n;
    for(int i = 0; i < n; i++)
        cin>>a[i];
    quick_sort(a, 0, n - 1);
    for(int i = 0; i < n; i++)
        cout<<a[i]<<" ";
    return 0;
}