代码

#include <string.h>

typedef unsigned int u32;

static u32 b[200000000];
static u32 cnt[1024];

void sort(unsigned *a, int n) {
  u32 *c1 = cnt, *c2 = cnt + 256, *c3 = cnt + 512, *c4 = cnt + 768;
  u32 *tmp = b;

  memset(cnt, 0, sizeof(cnt));
  for (int i = 0; i < n; i++) {
    u32 x = a[i];
    c1[x & 255]++;
    c2[(x >> 8) & 255]++;
    c3[(x >> 16) & 255]++;
    c4[x >> 24]++;
  }
  for (int i = 1; i < 256; i++) {
    c1[i] += c1[i-1];
    c2[i] += c2[i-1];
    c3[i] += c3[i-1];
    c4[i] += c4[i-1];
  }
  for (int i = n - 1; i >= 0; i--) tmp[--c1[a[i] & 255]] = a[i];
  for (int i = n - 1; i >= 0; i--) a[--c2[(tmp[i] >> 8) & 255]] = tmp[i];
  for (int i = n - 1; i >= 0; i--) tmp[--c3[(a[i] >> 16) & 255]] = a[i];
  for (int i = n - 1; i >= 0; i--) a[--c4[tmp[i] >> 24]] = tmp[i];
}

评测结果