本文将介绍键索引计数法、LSD基数排序、MSD基数排序。
1. 字符串（String）
我们来简单回顾一下字符串。
众所周知，字符串是编程语言中表示文本的数据类型。它是一堆字符的组合，如 String S="String"。
我们可以知道字符串的长度：S.length()=6;
可以知道某个位置的字符是什么：S[0]="S"; S[5]="g";
可以提取S中的一部分;
可以把两个字符串合并起来形成新字符串等等。
2. 字符串排序
如果我们要对一堆字符串像字典一样排序，怎么排？例如：
字典是怎么排序的呢？
按照英文字母表顺序a,b,c,d,...,y,w，我们得到了字母的大小排序：a<b<c<d<...<y<w。
sea和she相比，第一个字母相同，第二个字母e<h，故sea<she;
sea和seashells相比，前三个字母相同，但seashells比sea长，故sea<seashells;
seashells和sells相比，前两个字母相同，第三个字母a<l，故seashells<sells。
图中的CompareTo()就是对象之间比较大小的方法。
要想使用上述4种排序算法，必须提供一种对象之间比较大小的方法。即程序需要知道对象a与对象b谁大谁小（或相等）。
如果对象是数字，那比较方法容易实现。但如果对象是字符串，比较方法就复杂多了。
接下来，我们将介绍拥有比上述方法更高效率的字符串排序算法。
3. 键索引计数法（Key-indexed counting ）
讲算法之前，我们来先了解一下这些算法的基础：键索引计数法。
从例子入手：a[]是拥有一堆只有一个字符的string数组。
a[]中不同的字符分别有6个：a,b,c,d,e,f。我们需要给这些字符配对一些int类型的键索(Key-indexed)：令a=0;b=1;c=2;d=3;e=4;f=5。
创建一个int类型的数组count，拥有7个元素：
然后我们数这六个字符分别重复出现了多少次，并把次数记录在count[x+1]中。x为某个字符对应的键索。
a重复出现了2次，a对应的键索为0，故count[1]=2;
b重复出现了3次，b对应的键索为1，故count[2]=3;
c重复出现了1次，c对应的键索为2，故count[3]=1;
d重复出现了2次，d对应的键索为3，故count[4]=2;
e重复出现了1次，e对应的键索为4，故count[5]=1;
f重复出现了3次，f对应的键索为5，故count[6]=3;
然后我们计算比某个字符小的字符有多少个，计算方法为count[x+1] += count[x]。x为某个字符对应的键索。(x从0开始逐渐递增)
例如：count[1]=count[1]+count[0]=2; count[2]=count[1]+count[2]=2+3=5; count[3]=count[3]+count[2]=1+5=6;
为了方便理解，我们把键索对应的字符显示出来：
然后就是排序了，构建一个辅助数组aux[]。
从a[0]逐一排序：
因为a[0]=d，d对应的键索为3,count[3]=6，故aux[6]=d, count[3]+=1;
因为a[1]=a，a对应的键索为0,count[0]=0，故aux[0]=a, count[0]+=1;
因为a[2]=c，c对应的键索为2,count[2]=5，故aux[5]=c, count[2]+=1;
因为a[3]=f，f对应的键索为5,count[5]=9，故aux[9]=f, count[5]+=1;
如此类推，直到aux[]填满了。
aux[]就是排序完毕后的数组，最后只需把aux[]复制给a[]即可，算法结束。
总结一下通用思路就是：
令a[]是拥有一堆只有一个字符的string数组，且有R个不同的字符。
1. 创建一个int类型的拥有R+1个元素的数组count和一个与a[]同等大小的string数组aux[]；
2. 数这些不同的字符分别重复出现了多少次，并把次数记录在count[x+1]中。x为某个字符对应的键索；
3. 计算比某个字符小的字符有多少个，计算方法为count[x+1] += count[x]。x为某个字符对应的键索。(x从0开始逐渐递增)
4. 通过利用count[]把a[]的元素逐一添加到aux[]中
5. 把aux[]复制给a[]
键索引计数法是稳定的（Stable），如果不了解稳定是什么意思，继续往下看，稍后将介绍。
代码实现：
4. LSD基数排序（LSD radix sort ）
现在开始讲String排序算法。
LSD全称：Least-significant-digit-first 低位有效数字优先。
如果要排序的那堆字符串长度相同，我们可以用LSD基数排序。
从例子入手：a[]是拥有一堆只有三个字符的string数组。
为了方便理解，我把这些字符都特意分开标示出来了。a[0]=dab;a[1]=add;a[2]=cab; ...
首先，我们先对第三个字符那一列通过键索引计数法把这堆字符串排一次序：
