代码

#include<bits/stdc++.h>
void sort(unsigned *a,int n)
{
	int pow2=13,siz=1<<pow2;
	unsigned *b=new unsigned[n],*cnt=new unsigned[siz];
	memset(cnt,0,siz*4);
	for(int j=0; j<=n-1; ++j) ++cnt[a[j]&siz-1];
	for(int j=1; j<=siz-1; ++j) cnt[j]+=cnt[j-1];
	for(int j=n-1; j>=0; --j) b[--cnt[a[j]&siz-1]]=a[j];
	memset(cnt,0,siz*4);
	for(int j=0; j<=n-1; ++j) ++cnt[b[j]>>pow2&siz-1];
	for(int j=1; j<=siz-1; ++j) cnt[j]+=cnt[j-1];
	for(int j=n-1; j>=0; --j) a[--cnt[b[j]>>pow2&siz-1]]=b[j];
	memset(cnt,0,siz*4);
	for(int j=0; j<=n-1; ++j) ++cnt[a[j]>>pow2*2&siz-1];
	for(int j=1; j<=siz-1; ++j) cnt[j]+=cnt[j-1];
	for(int j=n-1; j>=0; --j) b[--cnt[a[j]>>pow2*2&siz-1]]=a[j];
	memset(cnt,0,siz*4);
	for(int j=0; j<=n-1; ++j) ++cnt[b[j]>>pow2*3&siz-1];
	for(int j=1; j<=siz-1; ++j) cnt[j]+=cnt[j-1];
	for(int j=n-1; j>=0; --j) a[--cnt[b[j]>>pow2*3&siz-1]]=b[j];
}

评测结果