代码

#include<bits/stdc++.h>
const int N=1<<27,B=9;
unsigned b[N],cnt[1<<B];
// void counting_sort(int p){
// 	memset(cnt,0,sizeof(cnt));
// 	for(int i=1;i<=n;++i)++cnt[a[i].key[p]];
// 	for(int i=1;i<=w[p];++i)cnt[i]+=cnt[i-1];
// 	for(int i=n;i>=1;--i) b[cnt[a[i].key[p]]--]=a[i];
// 	memcpy(a,b,sizeof(a));
// }
// void radix_sort(){
// 	for(int i=k;i>=1;--i){
// 		counting_sort(i);
// 	}
// }
void sort(unsigned *a,int n){
	for(int p=0;p<3;p++){
		// memset(cnt,0,sizeof(cnt));
		for(int i=0;i<(1<<B);i++) cnt[i]=0;
		for(int i=1;i<=n;i++) cnt[(a[i]>>(B*p))&((1<<B)-1)]++;
		for(int i=0;i<(1<<B);i++) cnt[i]+=cnt[i-1];
		// for(int i=0;i<=5;i++) std::cout<<cnt[i]<<' ';
		// std::cout<<std::endl;
		for(int i=n;i>=1;i--) b[cnt[(a[i]>>(B*p))&((1<<B)-1)]--]=a[i];
		// for(int i=0;i<=5;i++) std::cout<<b[i]<<' ';
		// std::cout<<std::endl;
		for(int i=1;i<=n;i++) a[i]=b[i];
		// memcpy(a,b,sizeof(a));
	}
}

评测结果