字符串排序问题在很多行业都有应用，其排序方法也有很多。
1、低位优先字符串排序(LSD)
所谓低位优先就是指以字符串最后字符起为序对字符串进行排序，其原理与基数排序相似。其要求字符串是带排序字符串等长，比如银行卡号、电话号码之类。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21public class LSD {
public static void sort(String[] a,int W){
//通过前w个字符将a[]排序
int N = a.length;
int R = 256;
String[] aux = new String[N];
for(int d=W-1;d>=0;d--){
//根据第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];//回写
}
}
}
分析：
上述代码中R为256是考虑到拓展后的ASCII码最多为256个。
aux数组是临时数组，进行排序操作。我们来分析最大的那个for循环，首先生成一个count数组，其大小为R+1，此时进入第一个for循环，这个for循环是用来计算字符出现频率，通过a[i].charAt(d)+1操作，我们就能对出现的元素进行ASCII码定位，至于为什么加1之后再说。循环之后进入第二个for循环，这个循环用于将频率转换为索引，此时就能看到之前加1的作用。
上图代表了前三个for循环的过程，第二列代表了对频率的计算，第三列将频率转化为索引，count的下标就能代表有多少数小于下标，比如count[1]=3就代表小于1的数据共有3条，与原数据相符。所以如果在第二个循环中不加1的话就无法达到上述效果，之所以要达到这样的效果是因为这样可以保证count[r]总是下一个键为r的元素在aux中的索引位置，比如a[0]中的8就在aux[5]中，a[1]、a[2]、a[3]中的尾数0都可以直接找count[0]的值进行定位(注意由于第三个循环的影响，count[0]的值一直在不断变化)。
2、高位优先字符串排序(MSD)
高位优先是以字符串最初字符起为序对字符串进行排序，此时对字符串并没有等长要求。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55public class MSD {
private static int R = 256;//基数
private static final int M = 15;//小数组的切换阈值
private static String[] aux;//数据分类的辅助数组
private static int charAt(String s,int d){
if(d<s.length())
return s.charAt(d);
else
return -1;
}
public static void sort(String[] a){
int N = a.length;
aux = new String[N];
sort(a,0,N-1,0);
}
private static void sort(String[] a,int lo,int hi,int d){
if(hi<=lo+M){
insertion(a,lo,hi,d);
return;
}
int[] count = new int[R+2];
for(int i=lo;i<=hi;i++)
count[charAt(a[i],d)+2]++;
for(int r=0;r<=R+1;r++)
count[r+1] = count[r];
for(int i=lo;i<=hi;i++)
aux[count[charAt(a[i],d)+1]++] = a[i];
for(int i=lo;i<=hi;i++)
a[i]=aux[i-lo];
for(int r=0;r<R;r++)
sort(a,lo+count[r],lo+count[r+1],d+1);
}
private static void insertion(String[] a, int lo, int hi, int d) {
for (int i = lo; i <= hi; i++)
for (int j = i; j > lo && less(a[j], a[j-1], d); j--)
exch(a, j, j-1);
}
private static void exch(String[] a, int i, int j) {
String temp = a[i];
a[i] = a[j];
a[j] = temp;
}
private static boolean less(String v, String w, int d) {
for (int i = d; i < Math.min(v.length(), w.length()); i++) {
if (v.charAt(i) < w.charAt(i)) return true;
if (v.charAt(i) > w.charAt(i)) return false;
}
return v.length() < w.length();
}
}
分析：
上图详细计算了第一轮排序时，count、aux、a数组的变化情况，这些步骤在LSD中几乎一致。但是不一样的是，在对d=0的情况进行排序之后，还需要以d=1、d=2等情况进行递归排序。1
2for(int r=0;r<R;r++)
sort(a,lo+count[r],lo+count[r+1],d+1);
此处使用count[r]和count[r+1]就是为了把不同分组区分开，我们先来分析下第一轮结束后count数组的变化。
我们把上述数据带入递归中进行匹配可以发现，count[0]和count[1]、count[1]和count[2]、count[18]和count[19]以及count[19]和count[20]之间出现了数据上的区别，它们所代表的值就是每一组开始的下标，比如count[0]和count[1]就代表从0开始是a组，count[1]和count[2]就代表从1开始是b组，count[18]和count[19]代表从2开始是s组，count[19]和count[2]代表从12开始是h组。理解这层关系后就能进行递归完成d递增的排序，并最后得到正确排序。
3、三向字符串快速排序
和三向切分快速排序相似，也是采用切分的方法对字符串进行分组，以尽可能使字符串组分散。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35public class Quick3String {
private static int charAt(String s,int d){
if(d<s.length())
return s.charAt(d);
else
return -1;
}
public static void sort(String[] a,int lo,int hi,int d){
if(hi<=lo)
return;
int lt=lo,gt=hi;
int v = charAt(a[lo],d);
int i = lo+1;
while(i<=gt){
int t = charAt(a[i],d);
if(t<v)
exch(a,lt++,i++);
else if(t>v)
exch(a,i,gt--);
else
i++;
}
sort(a,lo,lt-1,d);
if(v>=0)
sort(a,lt,gt,d+1);
sort(a,gt+1,hi,d);
}
private static void exch(String[] a, int i, int j) {
String temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
分析：
通过v得到切分字符，然后进行比较，小于、等于、大于该字符的字符串进行分组，先排序，然后递归调用。
总结