【题目来源】
https://www.acwing.com/problem/content/787/

【题目描述】
给定你一个长度为 n 的整数数列。
请你使用快速排序对这个数列按照从小到大进行排序。
并将排好序的数列按顺序输出。

【输入格式】
输入共两行，第一行包含整数 n。
第二行包含 n 个整数（所有整数均在 1∼10^9 范围内），表示整个数列。

【输出格式】
输出共一行，包含 n 个整数，表示排好序的数列。

【数据范围】
1≤n≤100000

【输入样例】
5
3 1 2 4 5

【输出样例】
1 2 3 4 5

【算法分析】
历史上，发过两篇关于快速排序的博文，链接如下：
https://blog.csdn.net/hnjzsyjyj/article/details/127825125
https://blog.csdn.net/hnjzsyjyj/article/details/119768770

但是，在提交至本题时，一直提示 Time Limit Exceeded。估计是本题数据加强的原因。同学们可自行分析原因。

【算法代码】

#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;

void quicksort(vector<int> &v, int le, int ri) {
    if(le>=ri) return;
    int mid=v[le+ri>>1];
    
    //交换时i的初始值为le-1，以保证选择到第一个大于mid的数v[i]
    //交换时j的初始值为ri+1，以保证选择到第一个小于mid的数v[j]
    int i=le-1;
    int j=ri+1;
    while(i<j) {
        while(v[++i]<mid){};
        while(v[--j]>mid){};
        if(i<j) swap(v[i],v[j]);
    }

    quicksort(v,le,j);
    quicksort(v,j+1,ri);
}

int main() {
    int n;
    scanf("%d", &n);
    
    vector<int> v;
    for(int i=0; i<n; i++) {
        int x;
        scanf("%d", &x);
        v.push_back(x);
    }

    quicksort(v,0,n-1);

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

    return 0;
}



/*
in:
30
128 294 133 295 175 8 232 248 241 164 11 60 238 133 291 116 6 67 98 67 196 260 181 160 83 160 90 153 233 216

out:
6 8 11 60 67 67 83 90 98 116 128 133 133 153 160 160 164 175 181 196 216 232 233 238 241 248 260 291 294 295
*/

【参考文献】
https://blog.csdn.net/a695484357/article/details/126242857
https://www.acwing.com/problem/content/solution/787/1/