代码

/* Sort n 32-bit unsigned ints in place.  LSD radix sort, 4 passes of 8 bits
 * (small digit table keeps the scatter write streams cache resident). */
#include <stdlib.h>
#include <string.h>

void sort(unsigned *a, int n) {
    if (n <= 1) return;
    /* already sorted? */
    {
        int ok = 1;
        for (int i = 1; i < n; i++) if (a[i - 1] > a[i]) { ok = 0; break; }
        if (ok) return;
    }
    unsigned *tmp = (unsigned *)malloc((size_t)n * sizeof(unsigned));
    if (!tmp) return;
    unsigned cnt[256];
    unsigned *src = a, *dst = tmp;
    for (int pass = 0; pass < 4; pass++) {
        int sh = pass << 3;
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < n; i++) cnt[(src[i] >> sh) & 255u]++;
        if (cnt[(src[0] >> sh) & 255u] == (unsigned)n) continue;  /* no-op pass */
        unsigned s = 0;
        for (int i = 0; i < 256; i++) { unsigned c = cnt[i]; cnt[i] = s; s += c; }
        for (int i = 0; i < n; i++) { unsigned v = src[i]; dst[cnt[(v >> sh) & 255u]++] = v; }
        unsigned *t = src; src = dst; dst = t;
    }
    if (src != a) memcpy(a, src, (size_t)n * sizeof(unsigned));
}

评测结果