代码

// 1001a: sort n=10000 unsigned. 4-pass LSD byte radix sort.
#include <cstring>

void sort(unsigned *a, int n) {
    static unsigned cnt[256];
    static unsigned tmp[1 << 16];
    unsigned *src = a, *dst = tmp;
    for (int pass = 0; pass < 4; pass++) {
        memset(cnt, 0, sizeof(cnt));
        int sh = pass * 8;
        for (int i = 0; i < n; i++) cnt[(src[i] >> sh) & 255]++;
        int s = 0;
        for (int i = 0; i < 256; i++) { int c = cnt[i]; cnt[i] = s; s += c; }
        for (int i = 0; i < n; i++) dst[cnt[(src[i] >> sh) & 255]++] = src[i];
        unsigned *t = src; src = dst; dst = t;
    }
    if (src != a) memcpy(a, src, n * 4);
}

评测结果