不同于其他基于比较的排序算法，基数排序是一种基于多关键字排序的思想对单逻辑关键字进行排序的方法。
讲明白点，基数排序是把一个数看成很多的部分，比如123看成1，2和3叠在一起。
最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。 最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。
例子：原数组73, 28, 93, 43, 55, 14, 22, 65, 39, 81
LSD：我们第一次按照个位升序排序，得到81, 22, 73, 93, 43, 14, 55, 65, 28, 39，第二次按照十位排序，得到14, 22, 28, 39, 43, 55, 65, 73, 81, 93。MSD: 首先按第十位分组，得到14, 22, 28, 39, 43, 55,65,73, 81, 93，第二次对于十位相同的数进行个位的分组，得到14, 22, 28, 39, 43, 55, 65, 73, 81, 93。我们这边定义一下数的比较： 看位数：eg：12和9，在个位排好后是，12，9，排十位时9的十位为0，所以往前，成立。 位数相同看最高位：在LSD中的最后一次排序就是最高位的比较，成立。 高位相同看低位：可能这就是基数排序的初衷，因为基数排序一次排一位，故在其他位相同时便可保证两个数是有序的。每一位有先后，数便有先后。
真以为每一位都排序一遍？那还不如直接整个数拿来排。
基数排序建立在桶排序的基础上，对于一个数组，不同的数可能成千上万个，但是他们的个位也就10种可能，而桶排序刚好可以便捷的处理这种有多个重复类型的数据。
按住我10秒就能秒懂桶排序~~
（几乎所有细节都已标出，再不懂我就。。。）
LSD代码如下：
#include<iostream> #include<cstdio> #include<cmath> #include<string> #include<cstring> #include<algorithm> #include<set> #include<map> #include<list> #include<vector> #include<stack> #include<queue> #include<functional> #define D long long #define F double #define MAX 0x7fffffff #define MIN -0x7fffffff #define mmm(a,b) memset(a,b,sizeof(a)) #define pb push_back #define mk make_pair #define fi first #define se second #define pill pair<int, int> #define for1(i,a,b) for(int i=a;i<=b;i++) #define for2(i,a,b) for(int i=a;i>=b;i--) #define ini(n) scanf("%d",&n) #define inll(n) scanf("%lld",&n) #define outisp(n) printf("%d ",n) #define outllsp(n) printf("%lld ",n) #define outiel(n) printf("%d\n",n) #define outllel(n) printf("%lld\n",n) using namespace std; #define N 1001000 #define MOD ((int)1e9+7) const string el="\n"; const string elel="\n\n"; const string sp=" "; const string spsp=" "; const string tab="\t"; int n,x[N]; int maxbit(int data[],int n){//求数组最大位数 int m=1,mb=0; for1(i,1,n){ while(data[i]>=m){ m*=10;mb++; } } return mb; } void IN(){ ini(n); for1(ijk,1,n)ini(x[ijk]);//1~n } void OUT(){ for1(ijk,1,n)outisp(x[ijk]);//1~n cout<<el; } //此方法使用一维数组实现，倍儿棒 ////首先要知道思路，从最后一位开始往前，把最后一位相同的放入一个桶中，按照桶的下标再还原数组 void radix_sort_LSD(int x[],int n){//数据下标1~n int d=maxbit(x,n); //最大位数 int radix=1; //接下来要进行的位 int *ct=new int[10];//计数，ct[2]==22 表示当前位上的数为2的有22个 int *tmp=new int[n+1];//先把桶中的数放入tmp，再把tmp赋值给x数组 for1(i,1,d){ for1(j,0,9)ct[j]=0;//初始化计数器 for1(j,1,n)ct[(x[j]/radix)%10]++;//统计每个桶中数的数量，下标为当前位上的数的计数器++ for1(j,1,9)ct[j]+=ct[j-1];//用ct来确定每个桶中在tmp数组中的区域位置 //eg : ct[3]=20 ，表示当前位上数为3的数中，最后一个应该赋值给tmp[20] //赋值完后，让ct[3]--，变成19，那么这些数中倒数第二个就赋值给了tmp[19] //推一遍，假如有5个当前位上数为3的数，这样下来就正确地赋值给了tmp[16]~tmp[20] for2(j,n,1)tmp[ct[(x[j]/radix)%10]--]=x[j]; for1(j,1,n)x[j]=tmp[j]; radix*=10; } delete[]tmp;delete[]ct; } int main() { IN();// case : 12 73 28 0 93 43 55 14 202 22 65 39 81 radix_sort_LSD(x,n); OUT();// case : 0 14 22 28 39 43 55 65 73 81 93 202 }MSD：
//相对于LSD，会比较耗时，毕竟最坏情况每位的每种可能（0到9）都要递归一次 //LSD做k次操作，MSD做1e(k-1)次操作。。。 //所以基本上用不到 -> 就是懒得敲。。。 //不过可以分享一下思路 //大致流程类似于DFS，对于每一位，先进行一次上述LSD中的操作， //然后对于每种可能（0到9）MSD后一位，直到这种可能的数量<2为止。 //一层MSD函数处理一位，处理后的结果是下一位的升序排列， //然后对下一位所有存在的可能继续MSD十万个数，数的范围1~十万，时间单位（MS） 十万个数，数的范围1~一百，时间单位（MS） 三十万个数，数的范围1~三十万，时间单位（MS） 三十万个数，数的范围1~一百，时间单位（MS）
看得出来，sort果然是国宝级的算法啊，不管是什么情况都稳稳的。
不过LSD这么简单的代码也能这么优秀啊！因为LSD用了桶的思想，所以在有很多重复数据的时候表现良好，而swift刚好相反，在三十万个一百以内的数的轰击下差点爆了，毕竟类似二叉搜索树。。。
