代码

typedef unsigned int u32;
void sort(u32 *a, int n) {
    u32 cnt[1024];
    u32 *c1 = cnt, *c2 = cnt + 256, *c3 = cnt + 512, *c4 = cnt + 768;
    for (int i = 0; i < 1024; i++) cnt[i] = 0;
    for (int i = 0; i < n; i++) {
        u32 x = a[i];
        c1[x & 255]++;
        c2[(x >> 8) & 255]++;
        c3[(x >> 16) & 255]++;
        c4[x >> 24]++;
    }
    for (int i = 1; i < 256; i++) {
        c1[i] += c1[i-1];
        c2[i] += c2[i-1];
        c3[i] += c3[i-1];
        c4[i] += c4[i-1];
    }
    static u32 tmp[10000];
    int i;
    for (i = n - 1; i >= 1; i -= 2) {
        u32 x0 = a[i], x1 = a[i-1];
        tmp[--c1[x0 & 255]] = x0;
        tmp[--c1[x1 & 255]] = x1;
    }
    if (i == 0) tmp[--c1[a[0] & 255]] = a[0];
    for (i = n - 1; i >= 1; i -= 2) {
        u32 x0 = tmp[i], x1 = tmp[i-1];
        a[--c2[(x0 >> 8) & 255]] = x0;
        a[--c2[(x1 >> 8) & 255]] = x1;
    }
    if (i == 0) a[--c2[(tmp[0] >> 8) & 255]] = tmp[0];
    for (i = n - 1; i >= 1; i -= 2) {
        u32 x0 = a[i], x1 = a[i-1];
        tmp[--c3[(x0 >> 16) & 255]] = x0;
        tmp[--c3[(x1 >> 16) & 255]] = x1;
    }
    if (i == 0) tmp[--c3[(a[0] >> 16) & 255]] = a[0];
    for (i = n - 1; i >= 1; i -= 2) {
        u32 x0 = tmp[i], x1 = tmp[i-1];
        a[--c4[x0 >> 24]] = x0;
        a[--c4[x1 >> 24]] = x1;
    }
    if (i == 0) a[--c4[tmp[0] >> 24]] = tmp[0];
}

评测结果