代码

#include <algorithm>
#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[kLoopNum][kRadix] = {0};

void sort(unsigned* arr, int n) {
  uint32_t radix_bitmask = kRadix - 1;
  uint32_t *buf_p0 = arr, *buf_p1 = buffer;
  memset(cnt, 0, sizeof(cnt));
  for (int shift_bits = 0, i = 0; shift_bits < 32;
       ++i, shift_bits += kRadixBits) {
    // 对于每个数位使用计数排序。基数设为2的整数幂，这样可以用位运算代替乘除和取模
    for (int j = 0; j < n; ++j) ++cnt[i][DIGIT(buf_p0[j])];
    for (uint64_t j = 1; j < kRadix; ++j) cnt[i][j] += cnt[i][j - 1];
    for (int j = n - 1; j >= 0; --j)
      buf_p1[--cnt[i][DIGIT(buf_p0[j])]] = buf_p0[j];
    std::swap(buf_p0, buf_p1);
  }
  if (buf_p0 != arr) memcpy(arr, buf_p0, n * sizeof(uint32_t));
  return;
}

评测结果