代码

typedef unsigned int UI;
typedef unsigned char UC;
void sort(UI *a,int n){
	UI c0[(1<<8)+1]={0};
	UI c1[(1<<8)+1]={0};
	UI c2[(1<<8)+1]={0};
	UI c3[(1<<8)+1]={0};
	// cerr<<"OK"<<endl;
	UC *p0=((UC*)a)-4;
	UC *p1=((UC*)a)-3;
	UC *p2=((UC*)a)-2;
	UC *p3=((UC*)a)-1;
	// cerr<<"OK"<<endl;
	for(int _=0;_<n;_++){
		// cerr<<"a["<<_<<"]="<<a[_]<<endl;
		c0[*(p0+=4)]++;
		c1[*(p1+=4)]++;
		c2[*(p2+=4)]++;
		c3[*(p3+=4)]++;
		// cerr<<"count "<<_<<" "<<(int)*p0<<" "<<(int)*p1<<" "<<(int)*p2<<" "<<(int)*p3<<endl;
	}
	// cerr<<"OK"<<endl;
	for(int i=1;i<(1<<8);i++){
		c0[i]+=c0[i-1];
		c1[i]+=c1[i-1];
		c2[i]+=c2[i-1];
		c3[i]+=c3[i-1];
	}
	static UI b[100000001];
	UI x;
	for(int i=n-1;i>=0;i--){
        x=a[i];
		b[--c0[x&0xff]]=x;
	}
	for(int i=n-1;i>=0;i--){
        x=b[i];
		a[--c1[(x>>8)&0xff]]=x;
	}
	for(int i=n-1;i>=0;i--){
        x=a[i];
		b[--c2[(x>>16)&0xff]]=x;
	}
	for(int i=n-1;i>=0;i--){
        x=b[i];
        a[--c3[x>>24]]=x;
	}
}

评测结果