代码

// 1001a: sort 10000 unsigned ints (4 passes of 8 bits, LSD).
typedef unsigned u32;

#define N 10000

void sort(u32 *a, int n) {
    (void)n;
    static u32 b[N];
    u32 *rs[256];
    u32 t0[256] = {0}, t1[256] = {0}, t2[256] = {0}, t3[256] = {0};
    u32 *p;
    int i;

    for (i = 0; i < N; i += 4) {
        u32 x0 = a[i], x1 = a[i + 1], x2 = a[i + 2], x3 = a[i + 3];
        t0[x0 & 255]++; t1[(x0 >> 8) & 255]++; t2[(x0 >> 16) & 255]++; t3[x0 >> 24]++;
        t0[x1 & 255]++; t1[(x1 >> 8) & 255]++; t2[(x1 >> 16) & 255]++; t3[x1 >> 24]++;
        t0[x2 & 255]++; t1[(x2 >> 8) & 255]++; t2[(x2 >> 16) & 255]++; t3[x2 >> 24]++;
        t0[x3 & 255]++; t1[(x3 >> 8) & 255]++; t2[(x3 >> 16) & 255]++; t3[x3 >> 24]++;
    }

    p = b;
    for (i = 0; i < 256; i++) { rs[i] = p; p += t0[i]; }
    for (i = 0; i < N; i += 4) {
        u32 x0 = a[i], x1 = a[i + 1], x2 = a[i + 2], x3 = a[i + 3];
        *rs[x0 & 255]++ = x0;
        *rs[x1 & 255]++ = x1;
        *rs[x2 & 255]++ = x2;
        *rs[x3 & 255]++ = x3;
    }

    p = a;
    for (i = 0; i < 256; i++) { rs[i] = p; p += t1[i]; }
    for (i = 0; i < N; i += 4) {
        u32 x0 = b[i], x1 = b[i + 1], x2 = b[i + 2], x3 = b[i + 3];
        *rs[(x0 >> 8) & 255]++ = x0;
        *rs[(x1 >> 8) & 255]++ = x1;
        *rs[(x2 >> 8) & 255]++ = x2;
        *rs[(x3 >> 8) & 255]++ = x3;
    }

    p = b;
    for (i = 0; i < 256; i++) { rs[i] = p; p += t2[i]; }
    for (i = 0; i < N; i += 4) {
        u32 x0 = a[i], x1 = a[i + 1], x2 = a[i + 2], x3 = a[i + 3];
        *rs[(x0 >> 16) & 255]++ = x0;
        *rs[(x1 >> 16) & 255]++ = x1;
        *rs[(x2 >> 16) & 255]++ = x2;
        *rs[(x3 >> 16) & 255]++ = x3;
    }

    p = a;
    for (i = 0; i < 256; i++) { rs[i] = p; p += t3[i]; }
    for (i = 0; i < N; i += 4) {
        u32 x0 = b[i], x1 = b[i + 1], x2 = b[i + 2], x3 = b[i + 3];
        *rs[x0 >> 24]++ = x0;
        *rs[x1 >> 24]++ = x1;
        *rs[x2 >> 24]++ = x2;
        *rs[x3 >> 24]++ = x3;
    }
}

评测结果