代码

#include <algorithm>
#pragma GCC optimize("Ofast", 3, "inline")
typedef unsigned int u32;
void sort(unsigned *a, int n) {
    u32 cnt[256];
    u32 *b = new u32[n];
    u32 ps = 0;
    memset(cnt, 0, sizeof cnt);
    for (int i = 0; i < n; ++i) ++cnt[(a[i] >> ps) & 0xff];
    for (int i = 1; i < 256; ++i) cnt[i] += cnt[i - 1];
    for (int i = n - 1; ~i; --i) b[--cnt[(a[i] >> ps) & 0xff]] = a[i];
    std::swap(a, b);
    ps = 8;
    memset(cnt, 0, sizeof cnt);
    for (int i = 0; i < n; ++i) ++cnt[(a[i] >> ps) & 0xff];
    for (int i = 1; i < 256; ++i) cnt[i] += cnt[i - 1];
    for (int i = n - 1; ~i; --i) b[--cnt[(a[i] >> ps) & 0xff]] = a[i];
    std::swap(a, b);
    ps = 16;
    memset(cnt, 0, sizeof cnt);
    for (int i = 0; i < n; ++i) ++cnt[(a[i] >> ps) & 0xff];
    for (int i = 1; i < 256; ++i) cnt[i] += cnt[i - 1];
    for (int i = n - 1; ~i; --i) b[--cnt[(a[i] >> ps) & 0xff]] = a[i];
    std::swap(a, b);
    ps = 24;
    memset(cnt, 0, sizeof cnt);
    for (int i = 0; i < n; ++i) ++cnt[(a[i] >> ps) & 0xff];
    for (int i = 1; i < 256; ++i) cnt[i] += cnt[i - 1];
    for (int i = n - 1; ~i; --i) b[--cnt[(a[i] >> ps) & 0xff]] = a[i];
    std::swap(a, b);
}

评测结果