思路很简单，就是取每次区间的中间值，左边的小于中间的，右边的都大于中间的，最终left和right都停留在中间这个位置，然后分别递归l-mid--1和mid+1--r这两个区间，求大佬指点

#include<iostream>
using namespace std;
int n,a[1000001];
int cnt;
void qsort(int l,int r)
{ 
	if(l>r)	return;
	int mid=l+r>>1;
	int left=l,right=r;
	while(left<right)
	{
		while(a[left]<a[mid]) left++;
		while(a[right]>a[mid]) right--;
		if(left<right)
		{
			swap(a[left],a[right]);
			left++;
			right--;
		}
		if(left!=right&&a[left]==a[mid]&&left<mid)
			left++;
		if(left!=right&&a[right]==a[mid]&&right>mid)
			right--;
	}
	if(left-1>l) qsort(l,left-1);
	if(r>right+1) qsort(right+1,r);	
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    qsort(1,n);
   for(int i=1;i<=n;i++) cout<<a[i]<<" ";
}