代码

#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+=4){
		cnt[a[i]&T]++;
		cnt[a[i+1]&T]++;
		cnt[a[i+2]&T]++;
		cnt[a[i+3]&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<(1<<B);i++) cnt[i]=0;
	for(int i=0;i<n;i+=4){
		cnt[(b[i]>>B)&T]++;
		cnt[(b[i+1]>>B)&T]++;
		cnt[(b[i+2]>>B)&T]++;
		cnt[(b[i+3]>>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[(b[i]>>B)&T]]=b[i];
}

评测结果