代码

typedef unsigned u32;
void sort(u32 *a,int n){
	u32 *b=new u32[n];//基数排序辅助数组
	int base=12,mask=(1U<<base)-1;//基数排序使用的基和掩码
	u32 *cnt=new u32[mask+1]();//单次计数排序使用的计数数组
	for(int ba=0;ba<32;ba+=base){
		for(int i=0;i<=mask;i++) cnt[i]=0;
		for(int i=0;i<n;i++) ++cnt[a[i]>>ba&mask];
		for(int i=1;i<=mask;i++) cnt[i]+=cnt[i-1];
		for(int i=n-1;~i;i--) b[--cnt[a[i]>>ba&mask]]=a[i];
		for(int i=0;i<n;i++) a[i]=b[i];
	}
	delete[] cnt;
	delete[] b;
}

评测结果