代码

unsigned tmp[500001];
unsigned cnt1[257], cnt2[257], cnt3[257], cnt4[257];
void sort(unsigned *a, unsigned n) {
    register unsigned *ae = a + n + 1, *tmpe = tmp + n + 1;
    register unsigned *cnte1 = cnt1 + 257, *cnte2 = cnt2 + 257, *cnte3 = cnt3 + 257, *cnte4 = cnt4 + 257;

    for(register unsigned *i = a + 1; i != ae; ++i)
        ++cnt1[*i & 0xff];
    for(register unsigned *i = cnt1 + 1; i != cnte1; ++i)
        *i += *(i - 1);
    for(register unsigned *i = ae - 1; i != a; --i)
        tmp[cnt1[*i & 0xff]--] = *i;

    for(register unsigned *i = tmp + 1; i != tmpe; ++i)
        ++cnt2[(*i >> 8) & 0xff];
    for(register unsigned *i = cnt2 + 1; i != cnte2; ++i)
        *i += *(i - 1);
    for(register unsigned *i = tmpe - 1; i != tmp; --i)
        a[cnt2[(*i >> 8) & 0xff]--] = *i;

    for(register unsigned *i = a + 1; i != ae; ++i)
        ++cnt3[(*i >> 16) & 0xff];
    for(register unsigned *i = cnt3 + 1; i != cnte3; ++i)
        *i += *(i - 1);
    for(register unsigned *i = ae - 1; i != a; --i)
        tmp[cnt3[(*i >> 16) & 0xff]--] = *i;

    for(register unsigned *i = tmp + 1; i != tmpe; ++i)
        ++cnt4[(*i >> 24) & 0xff];
    for(register unsigned *i = cnt4 + 1; i != cnte4; ++i)
        *i += *(i - 1);
    for(register unsigned *i = tmpe - 1; i != tmp; --i)
        a[cnt4[(*i >> 24) & 0xff]--] = *i;
}

评测结果