代码

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

#include <stdio.h>
#include <stdlib.h>
#define BUCKET_MOD (0xFFU)
#define BUCKET_SIZE (BUCKET_MOD + 1U)
#ifndef MAX_SIZE
#define MAX_SIZE (1000000U)
#endif

#define SPLIT_LOOP_1(p, key, mod, value, index)     \
*(--(key[value[index] mod].addr)) = value[index]
#define SPLIT_LOOP_2(p, key, mod, value, index)     \
SPLIT_LOOP_1(p, key, mod, value, index + 1);        \
SPLIT_LOOP_1(p, key, mod, value, index)
#define SPLIT_LOOP_4(p, key, mod, value, index)     \
SPLIT_LOOP_2(p, key, mod, value, index + 2);        \
SPLIT_LOOP_2(p, key, mod, value, index)
#define _SPLIT_LOOP_8_(p, key, mod, value)          \
SPLIT_LOOP_4(p, key, mod, value, 4);                \
SPLIT_LOOP_4(p, key, mod, value, 0)

#define ADD_LOOP_1(key, mod, v1)                    \
++key[v1 mod].offset
#define ADD_LOOP_2(key, mod, v1, v2)                \
ADD_LOOP_1(key, mod, v1);                           \
ADD_LOOP_1(key, mod, v2)
#define ADD_LOOP_4(key, mod, v1, v2, v3, v4)        \
ADD_LOOP_2(key, mod, v1, v2);                       \
ADD_LOOP_2(key, mod, v3, v4)
#define ADD_LOOP_8(key, mod, v1, v2, v3, v4, v5, v6, v7, v8)    \
ADD_LOOP_4(key, mod, v1, v2, v3, v4)                \
ADD_LOOP_4(key, mod, v5, v6, v7, v8)

#ifndef LOOP
#define SPLIT(dst, src, size, key, mod, p)          \
for (p = src + size; p > src; ) {                   \
    p -= 8;                                         \
    _SPLIT_LOOP_8_(dst, key, mod, p);               \
}               
#else
#define SPLIT(dst, src, size, key, mod, p)          \
for (p = src + size; p > src; ) {                   \
    register sort_t tmp = *(--p);                   \
    *(--key[tmp mod].addr) = tmp;                      \
}
#endif

#define CAL_OFFSET_INIT(key, init, begin)           \
key[init].addr = begin + key[init].offset;
#define CAL_OFFSET(key, i)                          \
key[i].addr = key[i - 1].addr + key[i].offset

typedef unsigned sort_t;
typedef unsigned long long sort_d_t;
typedef union int_p_t {
    unsigned int offset;
    sort_t* addr;
} int_p_t;
// sort_t arr[MAX_SIZE];
O2 void sort(sort_t *data, int n) {
    unsigned int i;
    int_p_t k1[BUCKET_SIZE] = {0}, k2[BUCKET_SIZE] = {0}, k3[BUCKET_SIZE] = {0}, k4[BUCKET_SIZE] = {0};
    sort_t *arr = (sort_t*)malloc(sizeof(data[0]) * n);
    sort_t *p = data, *end = data + n;
    for (; p < end; ) {
    // sort_d_t *pt = (sort_d_t*)data, *pend = (sort_d_t*)(data + n);
    // for (; pt < pend; ) {
        // register sort_d_t tmp = ((sort_d_t*)p)[0];
        // ++k4[tmp & BUCKET_MOD].offset;
        // ++k3[(tmp >> 8) & BUCKET_MOD].offset;
        // ++k2[(tmp >> 16) & BUCKET_MOD].offset;
        // ++k1[(tmp >> 24) & BUCKET_MOD].offset;
        // ++k4[(tmp >> 32) & BUCKET_MOD].offset;
        // ++k3[(tmp >> 40) & BUCKET_MOD].offset;
        // ++k2[(tmp >> 48) & BUCKET_MOD].offset;
        // ++k1[tmp >> 56].offset;
        // p += 2;
        register sort_d_t tmp = ((sort_d_t*)p)[0], tmp_ = ((sort_d_t*)p)[1];
        ++k4[tmp & BUCKET_MOD].offset;
        ++k4[tmp_ & BUCKET_MOD].offset;
        ++k3[(tmp >> 8) & BUCKET_MOD].offset;
        ++k3[(tmp_ >> 8) & BUCKET_MOD].offset;
        ++k2[(tmp >> 16) & BUCKET_MOD].offset;
        ++k2[(tmp_ >> 16) & BUCKET_MOD].offset;
        ++k1[(tmp >> 24) & BUCKET_MOD].offset;
        ++k1[(tmp_ >> 24) & BUCKET_MOD].offset;
        ++k4[(tmp >> 32) & BUCKET_MOD].offset;
        ++k4[(tmp_ >> 32) & BUCKET_MOD].offset;
        ++k3[(tmp >> 40) & BUCKET_MOD].offset;
        ++k3[(tmp_ >> 40) & BUCKET_MOD].offset;
        ++k2[(tmp >> 48) & BUCKET_MOD].offset;
        ++k2[(tmp_ >> 48) & BUCKET_MOD].offset;
        ++k1[tmp >> 56].offset;
        ++k1[tmp_ >> 56].offset;
        p += 4;
    }
    CAL_OFFSET_INIT(k4, 0, arr);
    CAL_OFFSET_INIT(k3, 0, data);
    CAL_OFFSET_INIT(k2, 0, arr);
    CAL_OFFSET_INIT(k1, 0, data);
    for (i = 1; i < BUCKET_SIZE; ++i) {
        CAL_OFFSET(k4, i);
        CAL_OFFSET(k3, i);
        CAL_OFFSET(k2, i);
        CAL_OFFSET(k1, i);
    }

    SPLIT(arr, data, n, k4, & BUCKET_MOD, p);
    SPLIT(data, arr, n, k3, >> 8 & BUCKET_MOD, p);
    SPLIT(arr, data, n, k2, >> 16 & BUCKET_MOD, p);
    SPLIT(data, arr, n, k1, >> 24, p);
    free(arr);
}

评测结果