代码

#include <cstdint>
#include <cstring>

#define DIGIT(X) (((X) >> shift_bits) & radix_bitmask)

constexpr int kRadixBits = 8;
constexpr size_t kMaxN = 1e8, kRadix = 1 << kRadixBits;
constexpr size_t kLoopNum = 32 / kRadixBits + (32 % kRadixBits != 0);
uint32_t buffer[kMaxN], cnt[kRadix] = {0};

void sort(unsigned* arr, int n) {
  uint32_t radix_bitmask = kRadix - 1;
  uint32_t *buf_p0 = arr, *buf_p1 = buffer, *buf_pt;
  for (int shift_bits = 0, i = 0; shift_bits < 32;
       ++i, shift_bits += kRadixBits) {
    memset(cnt, 0, sizeof(cnt));
    for (int j = 0; j < n; ++j) ++cnt[DIGIT(buf_p0[j])];
    for (uint64_t j = 1; j < kRadix; ++j) cnt[j] += cnt[j - 1];
    for (int j = n - 1; j >= 0; --j)
      buf_p1[--cnt[DIGIT(buf_p0[j])]] = buf_p0[j];
    buf_pt = buf_p0, buf_p0 = buf_p1, buf_p1 = buf_pt;
  }
  if (buf_p0 != arr) memcpy(arr, buf_p0, n * sizeof(uint32_t));
  return;
}

评测结果