代码

typedef unsigned int u32;
static u32 tmp[1 << 27];
static u32 cnt[5120];
void sort(unsigned *aa, int n) {
    u32 *a = (u32*)aa;
    int i;
    for (i = 0; i < 5120; i++) cnt[i] = 0;
    for (i = 0; i < n; i++) { u32 x = a[i];
        cnt[0 + (x & 2047)]++;
        cnt[2048 + ((x>>11) & 2047)]++;
        cnt[4096 + ((x>>22) & 1023)]++;
    }
    for (i = 1; i < 2048; i++) cnt[0+i] += cnt[0+i-1];
    for (i = 1; i < 2048; i++) cnt[2048+i] += cnt[2048+i-1];
    for (i = 1; i < 1024; i++) cnt[4096+i] += cnt[4096+i-1];
    for (i = n-1; i >= 0; i--) { u32 x = a[i]; tmp[--cnt[0 + (x & 2047)]] = x; }
    for (i = n-1; i >= 0; i--) { u32 x = tmp[i]; a[--cnt[2048 + ((x>>11) & 2047)]] = x; }
    for (i = n-1; i >= 0; i--) { u32 x = a[i]; tmp[--cnt[4096 + ((x>>22) & 1023)]] = x; }
    for (i = 0; i < n; i++) a[i] = tmp[i];
}

评测结果