基数排序模板（基数排序，C++模板）

算法的理论学习可右转Creeper_LKF大佬的洛谷日报

时间复杂度\(O(n)\)，算常数的话要乘位长。

蒟蒻参考了Creeper_LKF大佬的模板，并在通用性上面稍微提升了一点。可以兼容所有存储整数的基本类型，以及在此基础上构建的结构体类型（多关键字排序时，优先级高的关键字默认需要在结构体中靠后）。

函数原型

template<typename T>
void Radixsort(T*fst,T*lst,T*buf,int*op)

T即为待排序的类型名，fst lst为首尾指针（和sort一样），buf为缓冲区指针，op为操作列表。

\(op[i]\)提供类型的第\(i\)个字节的比较方式，具体来说有\(5\)种取值。
\(-1\)：该字节不是排序的关键字。
\(0\)：以该字节为基准从小到大排序。
\(1\)：以该字节为基准从大到小排序。
\(2\)：以该字节为基准从小到大排序，且该字节的最高位是有符号整形的符号位。
\(3\)：以该字节为基准从大到小排序，且该字节的最高位是有符号整形的符号位。

例如，对int从小到大排序，则应将\(\{0,0,0,2\}\)传入\(op\)。

对结构体unsigned int,int以前一个为关键字从大到小排序，则应将\(\{1,1,1,1,-1,-1,-1,-1\}\)传入\(op\)。

对长度为\(n\)的int数组排序效率对比如下：（STL不吸氧是真的布星）
\[\begin{matrix} 方式&n=10^6,不开\text{O2}&n=5*10^6,不开\text{O2}&n=5*10^6,开\text{O2}\\text{Radixsort}&\text{30+ms}&\text{80+ms}&\text{60+ms}\\text{std::sort}&\text{190+ms}&\text{1100+ms}&\text{360+ms} \end{matrix}\]

然而，Radixsort的运行时间与待排序类型的关键字位长总和几乎成正比，而std::sort受此的影响小多了。当总位长在\(10\)位以上时，开O2以后两者的差距很小了。所以综合实现难度方面，int多关键字和long long等用开O2的std::sort就够了。

至于实数类型，Radixsort不能直接资磁。double是\(8\)位的用std::sort就好了。至于如果是在想从小到大排float的话，必须膜改一下数组，将所有的负实数强行除了符号位都按位取反以后，传入\(\{0,0,0,2\}\)，最后还要还原回来，实在是太麻烦了。

#include<bits/stdc++.h>
using namespace std;
namespace FlashHu{
#define RG register
#define US unsigned
    template<typename T>
    inline void Radixsort(RG T*fst,RG T*lst,RG T*buf,RG int*op){
        static int b[0x100];
        RG US Len=lst-fst,Sz=sizeof(T),at=0,i,j;
        RG US char*bgn,*end,*it,tmp;
        for(i=0;i<Sz;++i){
            if(op[i]==-1)continue;
            bgn=(US char*)fst+i;end=(US char*)lst+i;
            tmp=((op[i]&1)?0xff:0)^((op[i]&2)?0x80:0);
            if(tmp)for(it=bgn;it!=end;it+=Sz)*it^=tmp;
            memset(b,0,sizeof(b));
            for(it=bgn;it!=end;it+=Sz)++b[*it];
            for(j=1;j<=0xff;++j)b[j]+=b[j-1];
            for(it=end;it!=bgn;)buf[--b[*(it-=Sz)]]=*--lst;
            lst=buf+Len;swap(fst,buf);at^=1;
            bgn=(US char*)fst+i;end=(US char*)lst+i;
            if(tmp)for(it=bgn;it!=end;it+=Sz)*it^=tmp;
        }
        if(at)memcpy(buf,fst,Sz*Len);
    }
#undef RG
#undef US
}

基数排序模板（基数排序，C++模板）

原文：https://www.cnblogs.com/flashhu/p/9751909.html