#include<iostream>

using namespace std;

 const int N = 1e6+10;//数组大小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 while的写法要熟悉，while里面的条件是跳出循环条件的对立事件
        do j -- ; while(q[j] > x);
        if(i < j) swap(q[i],q[j]);//交换前加一个判断，避免重复交换，还是考虑打破循环的条件
    }
    //递归处理
    quick_sort(q, l, j);//边界问题，写j的时候，上面不能是r，同理
    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]);
}

时间复杂度 ：对程序大致运行时间的描述
空间复杂度 ：对程序大致占用空间的描述