代码

#if defined(__GNUC__) && !defined(__clang__)
#define O2 __attribute__((optimize("-O2")))
#else
#define O2
#endif

#include <stdio.h>
#include <stdlib.h>
#define BUCKET_SIZE (0xFFU)

typedef unsigned sort_t;

O2 void sort(sort_t *data, int n) {
    unsigned int i;
    unsigned int k1[BUCKET_SIZE] = {0}, k2[BUCKET_SIZE] = {0}, k3[BUCKET_SIZE] = {0}, k4[BUCKET_SIZE] = {0};
    sort_t *arr = malloc(sizeof(data[0]) * n), *p;
    for (p = data + n; p > data; ) {
        register sort_t tmp = *(--p);
        ++k4[tmp & BUCKET_SIZE];
        ++k3[(tmp >> 8) & BUCKET_SIZE];
        ++k2[(tmp >> 16) & BUCKET_SIZE];
        ++k1[(tmp >> 24) & BUCKET_SIZE];
    }
    for (i = 1; i < BUCKET_SIZE; ++i) {
        k4[i] += k4[i - 1];
        k3[i] += k3[i - 1];
        k2[i] += k2[i - 1];
        k1[i] += k1[i - 1];
    }
    for (p = data + n; p > data; ) {
        register sort_t tmp = *(--p);
        arr[--k4[tmp & BUCKET_SIZE]] = tmp;
    }
    for (p = arr + n; p > arr; ) {
        register sort_t tmp = *(--p);
        data[--k3[(tmp >> 8) & BUCKET_SIZE]] = tmp;
    }
    for (p = data + n; p > data; ) {
        register sort_t tmp = *(--p);
        arr[--k2[(tmp >> 16) & BUCKET_SIZE]] = tmp;
    }
    for (p = arr + n; p > arr; ) {
        register sort_t tmp = *(--p);
        data[--k1[(tmp >> 24) & BUCKET_SIZE]] = tmp;
    }
    free(arr);
}

评测结果