//2023.2.13 取中点且x=q[l+r>>1]时，不能用i
//0 1 2 3 4 5
//0 8 2 3 4 5
// i j * * (8 2不符合条件)
//0 2 8 3 4 5 (第一个while完成，)
// j i * * (2 8不符合条件，且i>j，不会交换)
//恰好进入下一轮
//l j j+1 * * r

include[HTML_REMOVED]

using namespace std;

const int N=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>>1],i=l-1,j=r+1;
while(i<j)
{
    do i++;while(q[i]<x); //i右移
    do j--;while(q[j]>x); //j左移
    if(i<j) //将不符合条件的两边的数交换位置
    {
        int temp=q[i];
        q[i]=q[j];
        q[j]=temp;
    }
}

//递归调用
quick_sort(q,l,j);
quick_sort(q,j+1,r);
//不能用i

}

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]);

return 0;

}