代码

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

#include <stdio.h>
#include <stdlib.h>
#define BUCKET_MOD (0xFFFFU)
#define BUCKET_SIZE (BUCKET_MOD + 1U)
#define MAX_SIZE (10000000U)

typedef unsigned sort_t;
sort_t arr[MAX_SIZE];
O2 void sort(sort_t *data, int n) {
    unsigned int k1[BUCKET_SIZE] = {0}, k2[BUCKET_SIZE] = {0};
    unsigned int i;
    // sort_t *arr = (sort_t*)malloc(sizeof(data[0]) * n);
    sort_t *p;
    for (p = data + n; p > data; ) {
        register sort_t tmp = *(--p);
        if ((tmp >> 16) > BUCKET_MOD) {
            printf("k1++:%u\n", tmp >> 16);
        }
        ++k2[tmp & BUCKET_MOD];
        ++k1[tmp >> 16];
    }
    for (i = 1; i < BUCKET_SIZE; ++i) {
        k2[i] += k2[i - 1];
        k1[i] += k1[i - 1];
    }
    for (p = data + n; p > data; ) {
        register sort_t tmp = *(--p);
        if (k2[tmp & BUCKET_MOD] == 0) {
            printf("k2:%u\n", tmp & BUCKET_MOD);
        }
        arr[--k2[tmp & BUCKET_MOD]] = tmp;
    }
    for (p = arr + n; p > arr; ) {
        register sort_t tmp = *(--p);
        if (k1[tmp >> 16] == 0) {
            printf("k1:%u\n", tmp >> 16);
        }
        data[--k1[tmp >> 16]] = tmp;
    }
    // free(arr);
}

评测结果