字符串算法—字符串排序（上篇）
本⽂将介绍键索引计数法、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。
说到排序，我们⾃然想起了插⼊排序、、、，我们来回顾⼀下它们对N个对象进⾏排序的效率：
图中的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; ...
⾸先，我们先对第三个字符那⼀列通过键索引计数法把这堆字符串排⼀次序：
理所当然的，因为这些字符串每个都是⼀个个体，排序的时候，要整个字符串⼀起移动⽽不是只移动第三个字符。
标红的那⼀列已经排好序了。
接下来对第⼆个字符那⼀列通过键索引计数法把这堆字符串排⼀次序：
接下来对第⼀个字符那⼀列通过键索引计数法把这堆字符串排⼀次序：
排序完成，算法结束。
稳定性问题：
在这⾥，我们可以讨论⼀下稳定性的问题了（stable）。我们经常说这个算法是稳定的（stable），那个算法是不稳定的（not stable）。
这⾥的稳定不是指可不可靠，⽽是指这个算法会不会破坏原有的顺序。
例如，我们看⼀下这个例⼦，经历了对第⼆个字符那⼀列通过键索引计数法把这堆字符串排⼀次序后，a[1]=cab; a[2]=fad。
它们在对第三个字符那⼀列通过键索引计数法把这堆字符串排⼀次序的那时，对应的位置在哪？a[1]=cab; a[4]=fad。
第⼀次排序时，cab在fad前⾯，因为它们的第三个字符b<d; 但第⼆次排序时，这两个字符串的第⼆个字符都是a，不稳定的算法有可能会把fad排到cab前⾯，但稳定的算法肯定不会！
总结⼀下LSD基数排序通⽤思路就是：
如果需要排序的那堆字符串拥有⼀样多的字符，那么我们可以从它们的最后⼀个字符进⾏键索引计数法排序，然后对它们的倒数第⼆个字符进⾏键索引计数法排序，如此类推，直到对它们的第⼀个字符进⾏键索引计数法排序后，排序结束。
键索问题：
但是，键索引计数法是需要知道要排序的字符串有多少个不同的字符的，从⽽给那些字符匹配键索，难道我们每次都要去数⼀下有多少个不同的字符？
其实并不需要，这样做太耗费时间了。看下表：
根据每个不同类型的字符串，我们可以选择不同的R值（键索引计数法构建count数组需要⽤到的R值）。
如果我们知道要排序的字符串都是由⼩写字母组成，则R=26(毕竟只有26个字母)；
如果要排序的字符串还有⼀些符号，那就⽤R=256吧。
总之，按照需求选择R值。
LSD基数排序的代码实现:
5. MSD基数排序（MSD radix sort ）
那么如果要排序的那堆字符串长度不同，怎么办？那就⽤MSD基数排序吧！
MSD全称：Most-significant-digit-first ⾼位有效数字优先。
LSD是从最后⼀位字符开始往前排序的，⽽MSD是从第⼀位字符开始往后排序的。
从例⼦⼊⼿：a[]是拥有⼀堆字符串的字符串数组。
为了⽅便理解，我把这些字符都特意分开标⽰出来了。a[0]=she;a[1]=sells;a[2]=seashells; ...
我们设定每个字符串的最后⼀位字符的下⼀个位置的空字符的键索为-1，即：（为了⽅便观察，这⾥将暂时标红它们）
每次进⾏键索引计数法排序时，我们都按照排序结果，把所有字符串分成数个区。如下：
⾸先，我们先对第⼀个字符那⼀列通过键索引计数法把这堆字符串排⼀次序：
第⼀个字符那⼀列只有4个不同的字母，故把所有字符串分为4个区：
第⼀个区有a[0]；第⼆个区有a[1]；第三个区有a[2]~a[11]；第四个区有a[12]、a[13]。
然后从上往下看：
第⼀个区只有⼀个字符串，此区排序完毕；
第⼆个区只有⼀个字符串，此区排序完毕；
第三个区有很多个字符串，对此区的第⼆个字符那⼀列通过键索引计数法把这堆字符串排⼀次序：（为了⽅便观察，已排序完毕的字符串⽤绿⾊表⽰）
继续分区：
第⼀个区有a[2]~a[6]；第⼆个区有a[7]~a[10]；第三个区有a[11]。
然后从上往下看：
第⼀个区有很多个字符串，对此区的第三个字符那⼀列通过键索引计数法把这堆字符串排⼀次序：（为了⽅便观察，待排序的字符串⽤⿊⾊表⽰）
继续分区：
第⼀个区有a[2]~a[4]；第⼆个区有a[5]、a[6]。
然后从上往下看：
第⼀个区有很多个字符串，对此区的第四个字符那⼀列通过键索引计数法把这堆字符串排⼀次序：
在这次排序中，-1的效果就能表现出来了：因为分配键索时，字符分到的键索都是正数，这⾥的-1是最⼩的，故这样可以保证最短的字符在最前⾯。
继续分区：只有⼀个区，此区有a[3]、a[4]。（-1不是字符，不参与分区）
此区有很多个字符串，对此区的第五个字符那⼀列通过键索引计数法把这堆字符串排⼀次序：
继续分区：只有⼀个区，此区有a[3]、a[4]。
此区有很多个字符串，对此区的第六个字符那⼀列通过键索引计数法把这堆字符串排⼀次序：
（由于这两个字符串是相同的，故每次排序后的结果都⼀样，这⾥省略第7、8个字符的排序）
继续分区：只有⼀个区，此区有a[3]、a[4]。
此区有很多个字符串，对此区的第九个字符那⼀列通过键索引计数法把这堆字符串排⼀次序：
继续分区：只有⼀个区，此区有a[3]、a[4]。
此区有很多个字符串，对此区的第⼗个字符那⼀列通过键索引计数法把这堆字符串排⼀次序：
继续分区：没有区（因为都是-1，-1不是字符，不参与分区）
此区排序完毕，开始下⼀个区的排序：
此区有很多个字符串，对此区的第四个字符那⼀列通过键索引计数法把这堆字符串排⼀次序：
继续分区：只有⼀个区，此区有a[5]、a[6]。
此区有很多个字符串，对此区的第五个字符那⼀列通过键索引计数法把这堆字符串排⼀次序：
继续分区：只有⼀个区，此区有a[5]、a[6]。
此区有很多个字符串，对此区的第六个字符那⼀列通过键索引计数法把这堆字符串排⼀次序：
继续分区：没有区（因为都是-1，-1不是字符，不参与分区）
此区排序完毕，开始下⼀个区的排序：
字符串转数组编码方式 此区有很多个字符串，对此区的第三个字符那⼀列通过键索引计数法把这堆字符串排⼀次序：
继续分区：
第⼀个区有a[7]~a[9]；第⼆个区有a[10]。
然后从上往下看：
第⼀个区有很多个字符串，对此区的第四个字符那⼀列通过键索引计数法把这堆字符串排⼀次序：
继续分区：只有⼀个区，此区有a[8]。（-1不是字符，不参与分区）
此区只有⼀个字符串，此区排序完毕。
开始下⼀个区的排序：
此区只有⼀个字符串，此区排序完毕。
开始下⼀个区的排序：
此区只有⼀个字符串，此区排序完毕。
开始下⼀个区的排序：
此区有两个字符串，但由于它们是⼀样的，故这⾥省略对此区的第⼆、第三、第四个字符那⼀列分别通过键索引计数法排序：
没有下⼀个区了，全部排序完毕，算法结束。
这个算法演⽰过程本⾝就是⼀个递归的过程。
总结⼀下：
1. 对所有字符串的第⼀个字符那⼀列通过键索引计数法把这堆字符串排⼀次序，根据排序结果进⾏分区；
2. 从上往下处理各个分区：如果分区只有⼀个字符串，则此区处理完毕；如果有多个字符串，则对此区的字符串的下⼀个字符进⾏排序、分区、处理分区。
3. 所有分区处理完后，排序完毕，算法结束。
实现代码：
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论