代码

using namespace std;
unsigned*aa;
#define uint unsigned
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
void _sort(int l,int r){
	if(l>r)return;
	uint p=aa[l+gen()%(r-l+1)];
	int i=l-1,j=r+1;
#define isL(x) (x<l?true:(x>r?false:aa[x]<=p))
	while(1){
		while(i<=j&&isL(i))i++;
		while(i<=j&&!isL(j))j--;
		if(i<j){
			swap(aa[i],aa[j]);
		}else{
			assert(i>j);
			break;
		}
	}
	while(j>=l&&aa[j]==p)j--;
	while(i<=r&&aa[i]==p)i++;
	_sort(l,j);
	_sort(i,r);
}
void sort2(unsigned*a,int n){
	aa=a;
	_sort(0,n-1);
}

评测结果