代码

#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 *t = b;
  memset(cnt, 0, 1024*4);
  int i = 0;
  for (; i + 4 <= n; i += 4) {
    u32 x0 = a[i], x1 = a[i+1], x2 = a[i+2], x3 = a[i+3];
    c1[x0&255]++; c2[(x0>>8)&255]++; c3[(x0>>16)&255]++; c4[x0>>24]++;
    c1[x1&255]++; c2[(x1>>8)&255]++; c3[(x1>>16)&255]++; c4[x1>>24]++;
    c1[x2&255]++; c2[(x2>>8)&255]++; c3[(x2>>16)&255]++; c4[x2>>24]++;
    c1[x3&255]++; c2[(x3>>8)&255]++; c3[(x3>>16)&255]++; c4[x3>>24]++;
  }
  for (; i < n; i++) { u32 x = a[i]; c1[x&255]++; c2[(x>>8)&255]++; c3[(x>>16)&255]++; c4[x>>24]++; }
  for (int j = 1; j < 256; j++) { c1[j]+=c1[j-1]; c2[j]+=c2[j-1]; c3[j]+=c3[j-1]; c4[j]+=c4[j-1]; }
  i = n;
  for (; i >= 4; i -= 4) {
    u32 x0 = a[i-1], x1 = a[i-2], x2 = a[i-3], x3 = a[i-4];
    t[--c1[x0&255]] = x0; t[--c1[x1&255]] = x1; t[--c1[x2&255]] = x2; t[--c1[x3&255]] = x3;
  }
  for (; i >= 1; i--) { u32 x = a[i-1]; t[--c1[x&255]] = x; }
  i = n;
  for (; i >= 4; i -= 4) {
    u32 x0 = t[i-1], x1 = t[i-2], x2 = t[i-3], x3 = t[i-4];
    a[--c2[(x0>>8)&255]] = x0; a[--c2[(x1>>8)&255]] = x1; a[--c2[(x2>>8)&255]] = x2; a[--c2[(x3>>8)&255]] = x3;
  }
  for (; i >= 1; i--) { u32 x = t[i-1]; a[--c2[(x>>8)&255]] = x; }
  i = n;
  for (; i >= 4; i -= 4) {
    u32 x0 = a[i-1], x1 = a[i-2], x2 = a[i-3], x3 = a[i-4];
    t[--c3[(x0>>16)&255]] = x0; t[--c3[(x1>>16)&255]] = x1; t[--c3[(x2>>16)&255]] = x2; t[--c3[(x3>>16)&255]] = x3;
  }
  for (; i >= 1; i--) { u32 x = a[i-1]; t[--c3[(x>>16)&255]] = x; }
  i = n;
  for (; i >= 4; i -= 4) {
    u32 x0 = t[i-1], x1 = t[i-2], x2 = t[i-3], x3 = t[i-4];
    a[--c4[x0>>24]] = x0; a[--c4[x1>>24]] = x1; a[--c4[x2>>24]] = x2; a[--c4[x3>>24]] = x3;
  }
  for (; i >= 1; i--) { u32 x = t[i-1]; a[--c4[x>>24]] = x; }
}

评测结果