代码

// 1001a: sort n=10000 unsigned ints in place (baseline radix sort, 8-bit LSD)
void sort(unsigned *a, int n) {
    static unsigned b[10000];
    unsigned cnt[1024];
    unsigned *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++) {
        unsigned 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];
    }

    for (int i = n - 1; i >= 0; i--) b[--c1[a[i] & 255]] = a[i];
    for (int i = n - 1; i >= 0; i--) a[--c2[(b[i] >> 8) & 255]] = b[i];
    for (int i = n - 1; i >= 0; i--) b[--c3[(a[i] >> 16) & 255]] = a[i];
    for (int i = n - 1; i >= 0; i--) a[--c4[b[i] >> 24]] = b[i];
}

评测结果