代码

#include <string.h>
typedef unsigned int u32;

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

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

  memset(c0, 0, 256*4);
  for (int i = 0; i < n; i++) c0[a[i] & 255]++;
  u32 s = 0;
  for (int i = 0; i < 256; i++) { u32 v = c0[i]; c0[i] = s; s += v; }

  memset(c1, 0, 256*4);
  int i = 0;
  for (; i + 3 < n; i += 4) {
    u32 x0 = a[i], x1 = a[i+1], x2 = a[i+2], x3 = a[i+3];
    t[c0[x0 & 255]++] = x0; c1[(x0 >> 8) & 255]++;
    t[c0[x1 & 255]++] = x1; c1[(x1 >> 8) & 255]++;
    t[c0[x2 & 255]++] = x2; c1[(x2 >> 8) & 255]++;
    t[c0[x3 & 255]++] = x3; c1[(x3 >> 8) & 255]++;
  }
  for (; i < n; i++) { u32 x = a[i]; t[c0[x & 255]++] = x; c1[(x >> 8) & 255]++; }
  s = 0;
  for (i = 0; i < 256; i++) { u32 v = c1[i]; c1[i] = s; s += v; }

  memset(c2, 0, 256*4);
  i = 0;
  for (; i + 3 < n; i += 4) {
    u32 x0 = t[i], x1 = t[i+1], x2 = t[i+2], x3 = t[i+3];
    a[c1[(x0 >> 8) & 255]++] = x0; c2[(x0 >> 16) & 255]++;
    a[c1[(x1 >> 8) & 255]++] = x1; c2[(x1 >> 16) & 255]++;
    a[c1[(x2 >> 8) & 255]++] = x2; c2[(x2 >> 16) & 255]++;
    a[c1[(x3 >> 8) & 255]++] = x3; c2[(x3 >> 16) & 255]++;
  }
  for (; i < n; i++) { u32 x = t[i]; a[c1[(x >> 8) & 255]++] = x; c2[(x >> 16) & 255]++; }
  s = 0;
  for (i = 0; i < 256; i++) { u32 v = c2[i]; c2[i] = s; s += v; }

  memset(c3, 0, 256*4);
  i = 0;
  for (; i + 3 < n; i += 4) {
    u32 x0 = a[i], x1 = a[i+1], x2 = a[i+2], x3 = a[i+3];
    t[c2[(x0 >> 16) & 255]++] = x0; c3[x0 >> 24]++;
    t[c2[(x1 >> 16) & 255]++] = x1; c3[x1 >> 24]++;
    t[c2[(x2 >> 16) & 255]++] = x2; c3[x2 >> 24]++;
    t[c2[(x3 >> 16) & 255]++] = x3; c3[x3 >> 24]++;
  }
  for (; i < n; i++) { u32 x = a[i]; t[c2[(x >> 16) & 255]++] = x; c3[x >> 24]++; }
  s = 0;
  for (i = 0; i < 256; i++) { u32 v = c3[i]; c3[i] = s; s += v; }

  i = 0;
  for (; i + 3 < n; i += 4) {
    u32 x0 = t[i], x1 = t[i+1], x2 = t[i+2], x3 = t[i+3];
    a[c3[x0 >> 24]++] = x0;
    a[c3[x1 >> 24]++] = x1;
    a[c3[x2 >> 24]++] = x2;
    a[c3[x3 >> 24]++] = x3;
  }
  for (; i < n; i++) { u32 x = t[i]; a[c3[x >> 24]++] = x; }
}

评测结果