代码

typedef unsigned int u32;
static u32 tmp[1 << 27];
static u32 cnt[3076];
void sort(unsigned *aa, int n) {
    u32 *a = (u32*)aa;
    int i;
    for (i = 0; i < 3076; i++) cnt[i] = 0;
    for (i = 0; i < n; i++) { u32 x = a[i];
        cnt[0 + (x & 1023)]++;
        cnt[1024 + ((x>>10) & 1023)]++;
        cnt[2048 + ((x>>20) & 1023)]++;
        cnt[3072 + ((x>>30) & 3)]++;
    }
    for (i = 1; i < 1024; i++) cnt[0+i] += cnt[0+i-1];
    for (i = 1; i < 1024; i++) cnt[1024+i] += cnt[1024+i-1];
    for (i = 1; i < 1024; i++) cnt[2048+i] += cnt[2048+i-1];
    for (i = 1; i < 4; i++) cnt[3072+i] += cnt[3072+i-1];
    for (i = n-1; i >= 0; i--) { u32 x = a[i]; tmp[--cnt[0 + (x & 1023)]] = x; }
    for (i = n-1; i >= 0; i--) { u32 x = tmp[i]; a[--cnt[1024 + ((x>>10) & 1023)]] = x; }
    for (i = n-1; i >= 0; i--) { u32 x = a[i]; tmp[--cnt[2048 + ((x>>20) & 1023)]] = x; }
    for (i = n-1; i >= 0; i--) { u32 x = tmp[i]; a[--cnt[3072 + ((x>>30) & 3)]] = x; }
}

评测结果