代码

typedef unsigned int u32;
static u32 tmp[1 << 27];
static u32 cnt[1568];
void sort(unsigned *aa, int n) {
    u32 *a = (u32*)aa;
    int i;
    for (i = 0; i < 1568; i++) cnt[i] = 0;
    for (i = 0; i < n; i++) { u32 x = a[i];
        cnt[0 + (x & 511)]++;
        cnt[512 + ((x>>9) & 511)]++;
        cnt[1024 + ((x>>18) & 511)]++;
        cnt[1536 + ((x>>27) & 31)]++;
    }
    for (i = 1; i < 512; i++) cnt[0+i] += cnt[0+i-1];
    for (i = 1; i < 512; i++) cnt[512+i] += cnt[512+i-1];
    for (i = 1; i < 512; i++) cnt[1024+i] += cnt[1024+i-1];
    for (i = 1; i < 32; i++) cnt[1536+i] += cnt[1536+i-1];
    for (i = n-1; i >= 0; i--) { u32 x = a[i]; tmp[--cnt[0 + (x & 511)]] = x; }
    for (i = n-1; i >= 0; i--) { u32 x = tmp[i]; a[--cnt[512 + ((x>>9) & 511)]] = x; }
    for (i = n-1; i >= 0; i--) { u32 x = a[i]; tmp[--cnt[1024 + ((x>>18) & 511)]] = x; }
    for (i = n-1; i >= 0; i--) { u32 x = tmp[i]; a[--cnt[1536 + ((x>>27) & 31)]] = x; }
}

评测结果