代码

#include<bits/stdc++.h>
const int N=1<<27,B=16;
unsigned b[N],cnt[1<<B];
void sort(unsigned *a,int n){
	int T=(1<<B)-1;
	for(int i=0;i<(1<<B);i++) cnt[i]=0;
	for(int i=0;i<n;i++) cnt[a[i]&T]++;
	for(int i=0;i<(1<<B);i++) cnt[i]+=cnt[i-1];
	for(int i=n-1;i>=0;i--) b[--cnt[a[i]&T]]=a[i];
	// for(int i=0;i<n;i++) a[i]=b[i];
	for(int i=0;i<(1<<B);i++) cnt[i]=0;
	for(int i=0;i<n;i++) cnt[(b[i]>>B)&T]++;
	for(int i=0;i<(1<<B);i++) cnt[i]+=cnt[i-1];
	for(int i=n-1;i>=0;i--) a[--cnt[(a[i]>>B)&T]]=b[i];
	// for(int i=0;i<n;i++) a[i]=b[i];
}

评测结果