字符串排序（二）

高位优先的字符串排序
要实现一个通用的字符串排序算法（字符串的长度不一定相同），我们应当考虑从左向右遍历所有字符。显然，以a开头的字符串应当放在以b开头的字符串之前。实现这种思想的一个很自然的方法就是递归算法，被称为高位优先的字符串排序。首先用键索引计数法将所有字符串按照首字母排序，然后递归的将所有首字母对应的子数组排序。和快速排序一样，高位优先的字符串排序会将数组切分为能够独立排序的子数组来完成排序任务，但它的切分会为每个首字母得到一个子数组，而不是像快速排序那样产生固定的两个或三个切分。
在高位优先的字符串排序算法中，要特别注意到达字符串末尾的情况。在排序中，合理的做法是将所有的字符都已被检查过的字符串排在所有的子数组前面，这样就不需要递归的将该子数组排序。我们使用一个接收两个参数的私有方法toChar()来将字符串中的字符索引转化为数组索引，当指定的位置超过了字符串的末尾时该方法返回-1。然后将所有的返回值加1，得到一个非负的int值并用它作为count的索引。这种转换意味着字符串中每个字符都可能产生R+1种不同的值：0表示字符串的结尾，1表示字符串的第一个字符，以此类推。因为键索引计数法本来就需要一个额外的位置，所以使用代码int count[] = new int[R+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[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; 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+count[r+1]-1, d+1);
    }
}

---

三向字符串快速排序
我们也可以根据高位优先的字符串排序算法改进快速排序，根据键的首字母进行三向切分，仅在中间子数组的下一个字符（因为键的首字母与切分字符相等）继续递归排序。
三向字符串快速排序只会将数组分为三部分，因此当相应的高位优先的字符串排序产生的非空切分较多时，它需要移动的数据量就非常巨大，因为它需要进行一系列的三向切分才会获得多向切分的效果。但是，高位优先的字符串排序可能会产生大量（空）子数组，而三向字符串快速排序的切分总是三个。因此三项字符串快速排序能很好地处理等值键，有较长公共前缀的键和取值范围较小的键和小数组。

puprivateblic 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);
    }
}