代码

typedef unsigned int u32;
static u32 tmp[1 << 27];
static u32 cnt[8448];
void sort(unsigned *aa, int n) {
    u32 *a = (u32*)aa;
    int i;
    for (i = 0; i < 8448; i++) cnt[i] = 0;
    for (i = 0; i < n; i++) { u32 x = a[i];
        cnt[0 + (x & 4095)]++;
        cnt[4096 + ((x>>12) & 4095)]++;
        cnt[8192 + ((x>>24) & 255)]++;
    }
    for (i = 1; i < 4096; i++) cnt[0+i] += cnt[0+i-1];
    for (i = 1; i < 4096; i++) cnt[4096+i] += cnt[4096+i-1];
    for (i = 1; i < 256; i++) cnt[8192+i] += cnt[8192+i-1];
    for (i = n-1; i >= 0; i--) { u32 x = a[i]; tmp[--cnt[0 + (x & 4095)]] = x; }
    for (i = n-1; i >= 0; i--) { u32 x = tmp[i]; a[--cnt[4096 + ((x>>12) & 4095)]] = x; }
    for (i = n-1; i >= 0; i--) { u32 x = a[i]; tmp[--cnt[8192 + ((x>>24) & 255)]] = x; }
    for (i = 0; i < n; i++) a[i] = tmp[i];
}

评测结果