代码

typedef unsigned int ui;
const ui maxn=1e8+5,maxm=0x10000,P=0xffff;

ui tmp[maxn],cnt[maxm],cnt2[maxm];

void sort(ui *a, int n) {
	for(int i=0;i<n;i++) cnt[a[i]&P]++;
	for(ui i=1;i<=P;i++) cnt[i]+=cnt[i-1];
	for(int i=n-1;i>=0;i--) tmp[--cnt[a[i]&P]]=a[i];
	for(int i=0;i<n;i++) cnt2[a[i]>>16]++;
	for(ui i=1;i<=P;i++) cnt2[i]+=cnt2[i-1];
	for(int i=n-1;i>=0;i--) a[--cnt2[tmp[i]>>16]]=tmp[i];
}

评测结果