字符串之————基数排序（LSD、MSD）
本篇⽂章围绕字符串排序的核⼼思想，通过图⽰例⼦和代码分析的⽅式讲解了两个经典的字符串排序⽅法，内容很详细，完整代码放在⽂章的最后。
⼀、键索引计数法
在⼀般排序中，都要⽤⾥⾯的元素不断⽐较，⽽字符串这玩意⼉⼤可不必⽐较，有另外⼀种思想。在键索引计数法中，可以突破NlongN的排序算法运⾏时间下限，它的时间级别是线性的！
引⼊字母表概念：
想要不对字符串⾥⾯的字符进⾏对⽐，我们需要引⼊字母表的概念，⽐如将‘a’看作1，‘b’看作2，‘c’看作3，这样下去，26个字母只需要⼀个长度为27的数组就能够表⽰（下标为0不⽤），⽽且按数字来看他们是有序的（从a到z对应1到26）。
所以“abcdefg..”这些字符转换为整型时（使⽤charAt（）函数），⾃然有⼀个对应的顺序，所以我们只需要到⼀个合适⼤⼩的数组来保存每个将会⽤到的字符的信息即可。现在我们创建count[]数组，⼤⼩为256，⽤来保存对应字符出现的频率和排序时的索引。
索引计数法共分为四步，下⾯进⾏说明并举例。(⽤R来表⽰字符的种类，r表⽰字符在R中的顺序）
1、计算频率:
for(int i=0;i<N;i++){//计算频率
count[a[i].charAt(d)+1]++;
}
遍历所有字符串，d为字符串的第d个字符（下⾯例⼦中字符串都为单个数字）。
出现什么字符，我们就将对应的count[r+1]加⼀（⾥⾯为什么是r+1，看到下⼀步你⾃然会明⽩）。
2、计算索引:
for(int r=0;r<R;r++){//将频率转换为索引
count[r+1]+=count[r];
}
需要在我们计算出频率的基础上进⾏:count[r+1]+=count[r]
将count数组中后⼀位总是加上前⼀位。
例⼦：
⽼师组织了⼀次游玩，把同学们分为四组，需要做的是将同学按组号排序（这⾥R为4，count数组⼤⼩为R+2，下标为0不⽤）
图1 计算出现频率
图2 将频率转换为起始索引
可以从图⼆最后⼀⾏看到，r为1对应索引为0，即⼀组从0开始排序。
r为2对应索引1，即⼆组从1开始排序。
⽽第三组索引为5，说明从⼀到四全是第⼆组的位置。
3、数据分类
for(int i=0;i<N;i++){//数据分类
aux[count[a[i].charAt(d)]++]=a[i];字符串转数组用什么方法
}
进⾏数据分类我们需要⼀个辅助数组aux，⽤来暂时储存排序的数据。
把数据放⼊辅助字符串数组，全部放⼊时已经形成有序。
4、回写
for(int i=0;i<N;i++){//回写
a[i]=aux[i];
}
把辅助字符串数组的内容搬回去就⾏了。
到此为⽌键索引计数法就完成了，接下来利⽤它来实现LSD/MSD。
⼆、低位优先排序（LSD）
第位优先排序与⾼位优先排序的主要区别在于排序的⽅向，核⼼思想算法都是通过键索引计数法。低位优先算法是从字符串的右到左来排序（这可能会出现⼀些问题，在⾼位优先排序的介绍中将会提到）。
下图为⼀个地位优先排序的完整过程：
利⽤索引计数法，从左到右对每⼀位进⾏索引计数，这就形成了第位优先排序。
for (int d=W-1;d>=0;d--){//从右到左对所有字符串的每位判断
int count[]=new int[R+1];
for(int i=0;i<N;i++){//计算频率
count[a[i].charAt(d)+1]++;
}
for(int r=0;r<R;r++){//将频率转换为索引
count[r+1]+=count[r];
}
for(int i=0;i<N;i++){//排序
aux[count[a[i].charAt(d)]++]=a[i];
}
for(int i=0;i<N;i++){//回写
a[i]=aux[i];
}
}
三、⾼位优先排序（MSD）
在低位优先排序中，可能会出现⼀点问题。⽐如字符串“ab”与“ba”，长度为2需要进⾏两次排序，第⼀次排序结果为“ba”、“ab”，第⼆次排序结果为“ab”、“ba”，第⼀次排序的结果对第⼆次毫⽆意义，这就造成了时间上的浪费。
⽽在⾼位优先排序中，只会进⾏⼀次排序。结果为“ab”、“ba”。
不同之处：
在⾼位排序中⼜引⼊了分组的概念，即⽤⾸字母来切分下⼀个排序组。
在代码中我们使⽤递归的⽅式来不断切分排序组。
1public static void sort(String[] a,int lo,int hi,int d){
2if(lo>=hi){
3return;
4 }
5int[] count=new int[R+2];
6for(int i=lo;i<=hi;i++){
7 count[charAt(a[i],d)+2]++;
8 }
9for(int r=0;r<R+1;r++){
10 count[r+1]+=count[r];
11 }
12for(int i=0;i<=hi;i++){
13 aux[count[charAt(a[i],d)+1]++]=a[i];
14 }
15for(int i=0;i<=hi;i++){
16 a[i]=aux[i];
17 }
18for(int r=0;r<R;r++){
19 sort(a,lo+count[r],lo+count[r+1]-1,d+1);
20 }
21 }
上⾯这段代码⾮常简洁，但其中有⼀些地⽅是复杂的，请研究下⾯例⼦的调⽤过程确保你理解了算法。
图3 sort（a,0,9,0）的顶层调⽤
在下⼀期带来另⼀种字符串排序⽅法，三向字符串快速排序，相⽐于这两种⽅法，将会有更⼴的受⽤⾯！
四、完整代码
1public class LSD {
2public static void sort(String[] a,int W){//W表⽰字符串的长度
3int N=a.length;
4int R=256;//依字符的种类数⽬⽽定
5 String aux[]=new String[N];
6for (int d=W-1;d>=0;d--){//从右到左对所有字符串的每位判断
7int count[]=new int[R+1];
8for(int i=0;i<N;i++){//计算频率
9 count[a[i].charAt(d)+1]++;
10 }
11for(int r=0;r<R;r++){//将频率转换为索引
12 count[r+1]+=count[r];
13 }
14for(int i=0;i<N;i++){//排序
15 aux[count[a[i].charAt(d)]++]=a[i];
16 }
17for(int i=0;i<N;i++){//回写
18 a[i]=aux[i];
19 }
20 }
21 }
22 }
1public class MSD {
2private static int R=256;
3private static String[] aux;
4
5public static int charAt(String s,int d){
6if(d<s.length()){
7return s.charAt(d);
8 }else{
9return -1;
10 }
11 }
12
13public static void sort(String[] a){
14int N=a.length;
15 aux=new String[N];
16 sort(a,0,N-1,0);
17 }
18
19public static void sort(String[] a,int lo,int hi,int d){ 20if(lo>=hi){
21return;
22 }
23int[] count=new int[R+2];
24for(int i=lo;i<=hi;i++){
25 count[charAt(a[i],d)+2]++;
26 }
27for(int r=0;r<R+1;r++){
28 count[r+1]+=count[r];
29 }
30for(int i=lo;i<=hi;i++){
31 aux[count[charAt(a[i],d)+1]++]=a[i];
32 }
33for(int i=lo;i<=hi;i++){
34 a[i]=aux[i - lo];
35 }
36for(int r=0;r<R;r++){
37 sort(a,lo+count[r],lo+count[r+1]-1,d+1);
38 }
39 }
40 }
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论