GuangchaoSun's Blog

5.1 String Sorts

发表于  |    |   分类于   |  

字符串排序String Sorts

键索引计数法

  • 频率统计
    • 第一步就是用 int 数组count[]计算每个键出现的频率
  • 将频率转换成索引
    • 使用count[]来计算每个键在排序结果中的起始索引位置
  • 数据分类
    • 在将count[]数组转换为一张索引表之后，将所有元素移动到一个辅助数组aux[]
  • 回写
    • 最后一步将排序的结果复制回原数组中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int N = a.length
String[] aux = new String[N];
int[] count = new int[R+1];
for (int i=0;i<N;i++)
	count[a[i].key() + 1]++;
for (int r=0;r<R;r++) //R为每个分组里包含的元素的个数
	count[r+1] += count[r];
for (int i=0;i<N;i++)
	aux[count[a[i].key()]++] = a[i];
for (int i=0;i<N;i++)
	a[i] = aux[i];

命题A：键索引计数法排序N个键为0到R-1之间的整数的元素需要访问数组11N+4R+1次。

低位优先的字符串排序

命题B：低位优先的字符串排序算法能够稳定地将定长字符串排序。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public 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];
		}
	}
}

命题B（续）：对于基于R个字符的字母表的 N 个以长为 W 的字符串为键的元素，低位优先的字符串排序需要访问~7WN + 3WR 次数组，使用的额外空间和 N+R 成正比。

高位优先的字符串排序

代码实现：

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 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 Stirng[N];
		sort(a, 0, N-1, 0)
	}
	private static void sort(String[] a, int lo, int hi, int d){
		//以第d个字符将为键将a[lo]至a[hi]进行排序
		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 i=lo;i <= hi;i++)    //回写
			a[i] = aux[i - lo];
		for(int i=0;r < R;r++)      //递归的以每个字符为键进行排序
			sort(a, lo+count[r], lo+count[r+1]-1, d+1);
	}
}

小型子数组对于高位优先的字符串排序的性能至关重要。
对于含有大量等值键的子数组的排序会较慢

三向字符串快速排序

相比于前面两种字符串排序方式，三向字符串快速排序不需要额外的空间。

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 Quick3string{
	private static int charAt(Stirng 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);
	}
}

随机化：和快速排序一样，最好在排序之前将数组打乱或是将第一个元素和一个随机位置的元素交换以得到一个随机的切分元素。
命题E：要将含有N个随机字符串的数组排序，三向字符串快速排序平均需要比较字符~2NlnN次。

MSD.java