代码

#include<iostream>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<algorithm>
#include<type_traits>
#include<limits>

namespace RadixSort {

int cnt[32][256],n;
template<typename Iter1,typename Iter2> 
void __radix_sort(Iter1 a,Iter2 b,int len) {
    int tim=n>>3,dt=len<<3;
    auto nw=a+n-1;
    while(tim--){
        b[--cnt[len][nw[0]>>dt&255]]=nw[0];
        b[--cnt[len][nw[-1]>>dt&255]]=nw[-1];
        b[--cnt[len][nw[-2]>>dt&255]]=nw[-2];
        b[--cnt[len][nw[-3]>>dt&255]]=nw[-3];
        b[--cnt[len][nw[-4]>>dt&255]]=nw[-4];
        b[--cnt[len][nw[-5]>>dt&255]]=nw[-5];
        b[--cnt[len][nw[-6]>>dt&255]]=nw[-6];
        b[--cnt[len][nw[-7]>>dt&255]]=nw[-7];
        nw-=8;
    }
    switch(n&7){
        case 7:{b[--cnt[len][*nw>>dt&255]]=*nw;--nw;}
        case 6:{b[--cnt[len][*nw>>dt&255]]=*nw;--nw;}
        case 5:{b[--cnt[len][*nw>>dt&255]]=*nw;--nw;}
        case 4:{b[--cnt[len][*nw>>dt&255]]=*nw;--nw;}
        case 3:{b[--cnt[len][*nw>>dt&255]]=*nw;--nw;}
        case 2:{b[--cnt[len][*nw>>dt&255]]=*nw;--nw;}
        case 1:{b[--cnt[len][*nw>>dt&255]]=*nw;--nw;}
    }

}

template<typename IntType,typename Iter,bool chkmx=false> 
void radix_sort(Iter st,Iter ed) {
    typedef IntType T;
    static_assert(std::is_unsigned<T>::value&&std::is_integral<T>::value,
        "Need unsigned integer. Pleas use to_unsigned to access.");
    T rmx=std::numeric_limits<IntType>::max()>>8;
    T mx=0,*b=new T[ed-st](),*nw=nullptr,v=1;
    Iter a=st;
    int tot=1;
    for(T i=1;i<rmx;i<<=8) tot++;
#if !chkmx
    mx=rmx<<8;
#endif
    n=ed-st,v=0;
    for(int len=0;len<tot;len++,v=(len<<3)) 
        for(nw=st;nw!=ed;++nw) ++cnt[len][*nw>>v&255];
    for(int len=0;len<tot;len++) for(int i=1;i<256;++i) {
        cnt[len][i]+=cnt[len][i-1];
    }
    bool p=1;
    v=1;
    for(int len=0;len<tot;len++,p^=1,v<<=3) {
        if(p) __radix_sort(a,b,len);
        else __radix_sort(b,a,len);
        if(v>=mx) break;
    }
    if(!p) for(int i=0;i<n;i++) a[i]=b[i];
    delete []b;
}
}

//todo: to_unsigned

void sort(unsigned *a,int n) {RadixSort::radix_sort<unsigned>(a,a+n);}

评测结果