代码

#include <cstdint>
#include <cstring>

void sort(unsigned *arr, int n) {
  int radix_bits=8;
  uint64_t radix = 1ULL << radix_bits;
  uint32_t* cnt = new uint32_t[radix];
  uint32_t* tmp = new uint32_t[n];
  uint32_t radix_bitmask = radix - 1, digit;
  for (int shift_bits = 0; shift_bits < 32; shift_bits += radix_bits) {
    // 对于每个数位使用计数排序。基数设为2的整数幂，这样可以用位运算代替乘除和取模
    memset(cnt, 0, radix * sizeof(uint32_t));
    for (int j = 0; j < n; ++j) {
      digit = (arr[j] >> shift_bits) & radix_bitmask;
      ++cnt[digit];
    }
    for (uint64_t j = 1; j < radix; ++j) cnt[j] += cnt[j - 1];
    for (int j = n - 1; j >= 0; --j) {
      digit = (arr[j] >> shift_bits) & radix_bitmask;
      tmp[--cnt[digit]] = arr[j];
    }
    memcpy(arr, tmp, n * sizeof(uint32_t));
  }
  delete[] cnt;
  delete[] tmp;
  return;
}

评测结果