5.1 字符串排序
对于许多排序应用，决定顺序的键都是字符串。本节中，我们将会考虑能够利用字符串的特殊性质将字符串键排序的方法。
我们学习两类完全不同的字符串排序方法。
- 第一类方法会从右到左检查键中的字符。这种方法被称为低位优先(LSD)的字符串排序。使用数字代替字符的原因要追溯到相同方法在各种数字类型中的应用。如果将一个字符串看作一个256进制的数字，那么从右向左检查字符串就等价于先检查数字的最低位。这种方法适合键的长度都相同的字符串排序应用。
- 第二类方法会从左向右检查键中的字符，首先查看最高位字符。这些方法称为高位优先（MSD）高位优先的吸引人之处在于，不需要检查所有的输入就能完成排序。高位优先的字符串排序和快速排序类似，需要将数组切割为独立的部分并递归的调用相同的方法来处理子数组。要学习的第一个方法会为每个字符创建一个切分，第二种方法则总会产生三个切分，分别对应被搜索键的第一个字符小于、等会或大于切分键的第一个字符的情况。
5.1.1 键索引计数法
作为热身，我们先学习一种适用于小整数键的简单排序方法。
老师统计学生的分数的时候可能会遇到如下问题。学生被分为若干组，标号为1、2、3等。在某些情况下，我们希望全班同学按组分类。因为组的编号是较小的整数，使用键索引计数法排序是很合适的。假设数组a[]中的每个元素都保存了一个名字和组号，组号在0到R-1之间，代码a[i].key()会返回指定学生的组号。这种方法有四个步骤
5.1.1.1 频率统计
第一步就是使用int数组count[]计算每个键出现的频率。对于数组中的每个元素，使用它的键访问count[]中的相应元素并加1.如果键为r，则将count[r+1]+1。（为什么需要+1，下一步就明白了）。在上图的例子中，首先将count[3]加1，因为Anderson在第二组中，然后将count[4]+2，因为Brown和Davis都在第三组中。
5.1.1.2 将频率转换为索引
接下来，我们使用count[]计算每个键在排序结果中的起始索引位置。因为第一组有三个人，第二组有5个人，因此第三组在排序结果中的起始位置为8。一般来说，任意给定的键的起始索引均为所有较小的键所对应的出现频率之和。对于每个键r，小于r+1的键的频率之和为小于r的键的频率佳航count[r]。因此从左向右将count[]转换为一张用于排序的索引表是容易的
5.1.1.3 数据分类
在将count[]转换为一张索引表之后，将所有元素(学生)移动到一个辅助数组aux[]进行排序。每个元素在aux[]的位置由它的键（组别）对应的count[]决定，在移动之后将count[]的值+1，保证count[r]总是下一个键为r的元素在aux[]中的索引位置。这个过程只需要遍历一遍即可。
5.1.1.4 回写
最后一步是将结果从辅助数组复制回原数组
代码
/**
* 键索引数组排序法
*/
public class KeyIndexSort {
public static void sort(KeyIndex[] a) {
int N = a.length;
String[] aux = new String[N];
int[] count = new int[N + 1];
//计算出现频率
for (int i = 0; i < N; i++) {
count[a[i].key() + 1]++;
}
//频率转换为索引
for (int i = 0; i < N; i++) {
count[i + 1] += count[i];
}
//将元素分类
for (int i = 0; i < N; i++) {
aux[count[a[i].key()]++] = a[i].getString();
}
//复制到原数组
for (int i = 0; i < N; i++) {
a[i].setString(aux[i]);
}
}
}
class KeyIndex {
private String string; //键
private int key; //索引
public KeyIndex(String string, int key) {
this.string = string;
this.key = key;
}
public String getString() {
return string;
}
public int key() {
return key;
}
public void setString(String string) {
this.string = string;
}
}
5.1.2 低位优先的字符串排序
第一个学习的字符串排序算法是低位优先（LSD）的字符串排序。适用于字符串长度相同的排序
如果字符串的长度均为W，就从右向左以每个位置的字符作为键，用键索引计数法将字符串排序W遍。
低位优先的字符串排序
/**
* 低位优先的字符串排序
*/
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];
}
}
}
}
从理论上来说，低位优先的字符串排序的意义重大，因为是一种适用于一般应用的线性时间排序算法，无论N有多大，只遍历W遍数据。
对于典型的应用，R远小于N，因此命题B说明算法的总运行时间与WN成正比.N个成为W的字符串的输入总共含有WN个字符，因此低位优先的字符串排序的运行时间与输入规模成正比。
5.1.3 高位优先的字符串排序
要实现一个通用的字符串排序算法，我们考虑从左向右遍历所有字符。我们知道，以a开头的字符串应该排在b开头的字符串前面实现这种思想的一个很自然方法就是递归算法，称为高位优先（MSD）的字符串排序。首先使用键索引计数法对所有字符串按首字符排序，然后将每个首字符对应的子数组排序。和快速排序一样，高位优先的字符串会将数组切分为能够独立排序的子数组完成排序任务，但它切分会为每个首字母得到一个子数组，而不是像快速排序那样产生固定的两个或者三个切分。
5.1.3.1 对字符串末尾的约定
特别注意到达字符串末尾的情况。在排序中，合理的做法是将所有字符都已被检查过的字符所在的子数组排在所有子数组的前面，这样就不需要递归的将该子数组排序。为了简化这两步计算，我们使用了一个接受两个参数的私有方法charAt()来讲字符串中字符索引转换为数组索引，当指定的位置超过了字符串的末尾时返回-1。然后将所有返回值加1，得到了一个非负的int值并用它作为count[]的索引。这种转换意味着字符串的每个字符都可能产生R+1不同的值：0表示字符串的结尾，1表示第一个字母表的第一个字符，2表示字母表的第二个字符，因为键索引计数法本来就需要一个额外的位置，所以使用代码int count[]=new int[R+2];创建统计频率的数组。
5.1.3.2 高位优先的字符串排序中count[]数组的意义
算法5.2 高位优先的字符串排序
/**
* 高位优先字符串排序
*/
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[a.length];
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;
}
// 如果不在非常小的时候使用快速排序使用如下代码
// if(lo>=hi) return;
int[] count = new int[R + 2];
//统计频率
for (int i = lo; i <= hi; i++) {
count[a[i].charAt(d) + 2]++;
}
//频率转换为索引
for (int r = 0; r < R + 1; r++) {
count[r + 1] += count[r];
}
//数据分类
for (int i = lo; i <= hi; i++) {
aux[count[a[i].charAt(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] - 1, d + 1);
}
}
}
在将一个字符串数组a[]排序的时候，首先根据首字符用键索引计数法进行排序，然后（递归的）根据子数组中的字符串的首字符将子数组排序。
算法5.2的简洁令人刮目相看，它隐藏了一些复杂计算。花时间研究下图的算法顶层调用轨迹能确保你理解这个算法。
5.1.3.3 小型子数组
如果我们需要处理大量微型数组，快速处理它们。加入你需要对数百万个ASCII字符串（R=256）排序且不会对小数组进行特殊处理。每个字符串产生一个含有它自己的子数组，你需要将数百万个大小为1的子数组排序。但每次排序都要产生count[]初始化为0并且转换为索引。这种代价太高了，因此小数组切换到插入排序对于高位优先数组是必须的。
适用于字符串排序的插入排序
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 - 1, j);
}
}
}
//substring能直接比较出d位以后的大小
public static boolean less(String v, String w, int d) {
return v.substring(d).compareTo(w.substring(d)) < 0;
}
5.1.3.4 等值键
对于大量含有等值键的子数组，高位优先的字符串排序很慢。如果出现相同的子字符串过快，切换排序方法条件将不会出现，递归会检查相同键的每一个字符。因此，高位优先排序的最坏情况及时所有键相同
5.1.3.5 额外空间
为了进行切分，高位优先的算法使用了两个辅助数组：一个用来将数据分类的aux[]和另一个保存统计频率的count[]。aux[]大小为N且可以在递归方法sort()外创建。但是每次递归都会创建一个count[]数组，需要空间。
5.1.3.7 性能
高位优先的字符串排序算法的性能取决于数据。
- 对于随机输入。高位优先的字符串排序只会检查足以区别字符串所需的字符。算法的运行时间是亚线性的。（只会检查输入字符的一小部分）
- 对于非随机输入，高位优先的字符串排序算法可能仍是亚线性的，但需要检查的字符可能比随机情况下要多
- 最坏情况下。高位优先字符串检查所有字符，它的运行时间是线性的。
5.1.4 三向字符串快速排序
我们可以根据高位优先的字符串排序算法改进快速排序，仅根据键的首字母进行三向切分，仅在中间子数组中的下一个字符（因为键的首字母都与切分字符相等）继续递归排序。
三向字符串快速排序只将数组切分为三部分。三向字符串快速排序能够很好的处理等值键、有较长公共前缀的键、取值范围较小的键和小数组---------所有高位优先的字符串排序算法不擅长的情况。和快速排序一样，三向字符串快速排序也不需要额外的空间。递归所用的隐式栈除外。
算法5.3 三向字符串快速排序
/**
* 三向字符串快速排序
*/
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;
int gt = hi;
int i = lt + 1;
int v = charAt(a[lo], d);
while (i <= gt) {
int t = charAt(a[i], d);
if (t < v) exch(a, i++, lt++);
else if (t > v) exch(a, gt--, i);
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 t = a[i];
a[i] = a[j];
a[j] = t;
}
}
在将字符串数组a[]排序时，根据首字母进行三向切分，然后递归的得到三个子数组排序：一个含有所有首字母小于切分字符的字符串子数组，一个含有所有首字母等于切分字符的字符串子数组，最后一个事含有所有首字符大于切分字符的字符串子数组。
5.1.1.3随机化
和快速排序一样，最好在排序前将所有数据打乱，防止出现有序或者接近有序的情况。
5.1.1.4 性能
考虑字符串键都很长（简单点，长度都相同）且前面大半部分字符相同，这种情况下，性能与字符串的长度乘以2NlnN成正比，而三向字符串排序的运行时间则与N乘以字符串的长度（需要发现所有的相同开头字母）再加上2NlnN此比较（对剩下的较短部分进行排序）的和成正比
5.1.5 字符串排序算法的选择
