代码

typedef unsigned int u32;
static u32 tmp[100000000];
static u32 cnt[1024];
static inline void sc4f(u32*dst,u32*c,const u32*src,u32 n,u32 sh){
    u32 i;
    for(i=0;i+4<=n;i+=4){
        u32 x0=src[i],x1=src[i+1],x2=src[i+2],x3=src[i+3];
        dst[c[(x0>>sh)&255]++]=x0; dst[c[(x1>>sh)&255]++]=x1; dst[c[(x2>>sh)&255]++]=x2; dst[c[(x3>>sh)&255]++]=x3;
    }
    for(;i<n;i++){u32 x=src[i];dst[c[(x>>sh)&255]++]=x;}
}
void sort(u32 *a, int n) {
    u32 i; u32*c0=cnt,*c1=cnt+256,*c2=cnt+512,*c3=cnt+768;
    for(i=0;i<1024;i++)cnt[i]=0;
    for(i=0;i<(u32)n;i++){u32 x=a[i];c0[x&255]++;c1[(x>>8)&255]++;c2[(x>>16)&255]++;c3[x>>24]++;}
    for(i=1;i<256;i++){c0[i]+=c0[i-1];c1[i]+=c1[i-1];c2[i]+=c2[i-1];c3[i]+=c3[i-1];}
    // convert ends->starts
    for(i=255;i>0;i--){c0[i]=c0[i-1];c1[i]=c1[i-1];c2[i]=c2[i-1];c3[i]=c3[i-1];}
    c0[0]=c1[0]=c2[0]=c3[0]=0;
    sc4f(tmp,c0,a,(u32)n,0); sc4f(a,c1,tmp,(u32)n,8); sc4f(tmp,c2,a,(u32)n,16); sc4f(a,c3,tmp,(u32)n,24);
}

评测结果