算法的理论学习可右转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以前一个为关键字从大到小排序，则代码大致写成
Radixsort(a,a+n,buf,new int[8]{1,1,1,1,-1,-1,-1,-1});
对长度为(n)的int数组排序效率对比如下：（STL不吸氧是真的布星）
然而，Radixsort的运行时间与待排序类型的关键字位长总和成正比（upd:蒟蒻目测和总位长也有关，猜测是因为访问步长增加导致缓存刷新次数增加。例如，对long long排序大约是对int排序的三倍时间）。
而std::sort受此的影响小多了。当总位长在(10)位以上时，开O2以后两者的差距很小了。所以综合实现难度方面，int多关键字和long long等用开O2的std::sort就够了。
至于实数类型，Radixsort不能直接资磁。double是(8)位的用std::sort就好了。至于如果是在想从小到大排float的话，必须膜改一下数组，将所有的负实数强行除了符号位都按位取反以后，传入({0,0,0,2})，最后还要还原回来，实在是太麻烦了。
#include<bits/stdc++.h>
#define UC unsigned char
using namespace std;
template<typename T>
void Radixsort(T*fst,T*lst,T*buf,int*op){
static int b[0x100];
int Len=lst-fst,Sz=sizeof(T),at=0,i,j;
UC*bgn,*end,tmp;
for(i=0;i<Sz;++i){
if(op[i]==-1)continue;
bgn=(UC*)fst+i;end=(UC*)lst+i;
tmp=((op[i]&1)?0xff:0)^((op[i]&2)?0x80:0);
memset(b,0,sizeof(b));
for(UC*it=bgn;it!=end;it+=Sz)++b[tmp^*it];
for(j=1;j<0x100;++j)b[j]+=b[j-1];
for(UC*it=end;it!=bgn;buf[--b[tmp^*(it-=Sz)]]=*--lst);
lst=buf+Len;swap(fst,buf);at^=1;
}
if(at)memcpy(buf,fst,Sz*Len);
}
有没有觉得很好实现呢？比什么后缀排序不知道好写到哪里去了
这样实现很简短，但常数没有卡到极限，b桶数组的初始化部分可以强行展开出来并行计算。