本博客采用创作共用版权协议, 要求署名、非商业用途和保持一致. 转载本博客文章必须也遵循署名-非商业用途-保持一致的创作共用协议.
对于字符串数据排序问题的总结, 如有错误, 欢迎指出.
#键索引计数法
这种排序算法是以下两种排序算法的基础
假设有以下一组数据
| 组号 |
姓名 |
| 2 |
Anderson |
| 3 |
Brown |
| 3 |
Davis |
| 1 |
Harris |
算法步骤:
- 首先进行组号出现的频率统计, 使用count数组记录每个组号出现的次数
1
2
| for(i = 0; i < N; i++)
count[a[i].key() + 1)]++; //a[i].key()返回组号, count的下标从2开始, 可以由下面找到答案
|
- 将频率转换为索引, 使用count来计算每个组号在排序结果中的起始索引位置
1
2
| for(int r = 0; r < R; r++)
count[r + 1] += count[r] #1组数组下标应该从零开始, 没有第0组, 第2组下标应该从1开始(1组有一个成员), 3组下标从2开始(1组和2组共两个成员)
|
- 数据分类, 将count[]转换为索引表后, 将名字移动到对应的辅助数组中排序
1
2
| for(int i = 0; i < N; i++)
aux[count[a[i].key()]++] = a[i] //count[a[i].key()]表示某一组的下标, ++表示同组的下一个名字的下标
|
1
2
| for(i = 0; i < N; i++)
a[i] = aux[i];
|
#低位优先的字符串排序
低位优先排序算法是通过建索引计数法完成的, 从每个字符串的最右侧开始, 以每个位置的字符作为key键(相当于组号), 用键索引计数法对字符串排序W遍(假设所有字符串长度为W)
由于键索引计数法的排序是稳定的, 则可以推出低位优先的字符串排序算法能够稳定的排序定长字符串
算法缺点:
- 只能用于处于等长字符串排序
- 需要额外的count[]和aux[]数组空间
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
| public class LSD {
public static void sort(String[] a, int W) {
int N = a.length;
int R = 256;
String[] aux = new String[N];
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];
}
}
}
}
|
#高位优先的字符串排序
高位优先排序算法用于更通用的情形(字符串不定长), 首先用键索引计数法对所有字符串首字母排序, 然后在递归的将每个首字母所对应的子数组排序(忽略首字母)
当指定位置超出字符串的末尾应该返回-1.越界则输出-1. 这种转换意味着字符串中的每个字符都可能产生R+1中不同的值，同时键索引计数法本来就需要一个额外的位置，所以使用代码int count[] = new int[R + 2];
在高位优先排序中, 每次递归过程都会创建一个count数组并转换成索引, 当数据量过大, 会造成很大的空间代价, 所以当进行小数组排序时, 切换为使用插入排序算法, 避免重复检查已知相同字符带来的成本
算法缺点:
- 高位优先的字符串排序使用了两个辅助数组（aux[]和count[]）
- 高位优先的字符串排序的最坏情况就是所有的键均相同
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
55
| public 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.sort(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 r = 0; r < R; r++) {
sort(a, lo + count[r], lo + count[r + 1] - 1, d + 1);
}
}
public static class Insertion {
public static void sort(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 boolean less(String v, String w, int d) {
return v.substring(d).compareTo(w.substring(d)) < 0;
}
private static void exch(String[] a, int i, int j) {
String temp = a[i];
a[i] = a[j];;
a[j] = temp;
}
}
}
|
#三向字符串快速排序
根据高位优先, 改进为快速排序策略, 这种方法是前两种方法的结合
根据字符串数组的首字母进行三向切分, 然后递归的将得到的三个子数组排序, 一个含有所有首字母小于切分字符的字符串子数组, 一个含有所有首字母等于切分字符的子数组, 一个含有所有首字母大于气氛字符串的子数组
三项字符串快速排序能够很好地处理等值键、有较长公共前缀的键、取值范围较小的键和小数组，且只需要递归所需的隐式栈的额外空间
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
|
public 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) {
sort(a, 0, a.length - 1, 0);
}
private 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;
}
}
|
#参考链接
