快速排序模版

快速排序思想：递归分治
1. 确定分界值x，值的大小影响算法效率，可用random
2. 调增区间
3. 递归排序

主要问题
1. 为什么后面一定是j：
由于i的左边一定< x，j的右边一定 > x, 因此当j左移或者i右移时，只有两种情况会导致循环结束。
第一：j == i 时停下，q[i] = q[j] = x， l ～ j 是 <= x的
第二：i - j == 1，此时 q[j] < x, 而 q[i] > x，l ～ j 是 < x的 (不排除有x被一起交换了)
因此用j做分界，是正确的
2. x的取值，建议采用random函数，避免极端情况下退化成$O(n)$的时间复杂度

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
int q[N];

int random(int *q, int l, int r) {  
    // 不加随机数有两个样例过不去，因为当每次取点左端点的值太大或者太小时
    int a = q[l], b = q[l + r >> 1], c = q[r];  
    //每次分出的两个区间相差很大，会导致算法实践复杂度退化成$O(n)$
    return (a > b) ? ((b > c) ? (b) : ((a > c) ? c : a)) : ((a > c) ? (a) : ((b > c) ? c : b));  
    // 返回一个中间值
}

void quick_sort(int *q, int l, int r) {
    if (l >= r) return ;
    int x = random(q, l, r), 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() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", q + i);
    quick_sort(q, 0, n - 1);
    //exit(0);
    for (int i = 0; i < n; i++) {
        printf("%d ", q[i]);
    }
    return 0;
}