算法练习_高位优先的字符串排序算法

概念

在许多排序应用中，决定顺序的键都是字符串，因此，对字符串的处理十分重要。
低位优先的字符串排序算法以及键索引计数法可以参考之前博客 算法练习_低位优先的字符串排序算法

高位优先的字符串排序算法

低位优先的字符串排序适用于定长字符串，而要实现一个通用的字符串排序（字符串长度不一定相同），需要从左向右地遍历字符串。

高位优先的字符串排序算法类似于快速排序，将数组按照首字母，切分为小数组，再递归地对小数组进行排序。排序过程依然遵循键索引计数法的四个步骤：

• 频率统计
• 将频率转换为索引
• 数据分类
• 回写

在遍历字符串的过程中，当索引超过了某字符串的末尾，则返回 -1 ，将返回结果 +1 ，得到非负整数。因此，使用 charAt 方法，返回值可能有 R+1 种不同的情况。加上键索引计数法本身需要的一个额外的位置，因此，计算频率的数组 count 大小为 R+2。

图解

代码实现

public class MSD {
    private static final int R = 256;
    private static final int M = 1;//小数组阈值（设置为1，暂不引入插入排序）
    private static String[] aux;

    private static int charAt(String s, int d) {
        if (d < s.length()) {
            return s.charAt(d);
        }
        return -1;
    }

    public static void sort(String[] a) {
        int N = a.length;
        aux = new String[N];
        sort(a, 0, N - 1, 0);

    }

    public static void sort(String[] a, int lo, int hi, int d) {
        if (hi < lo + M) {
            //对小数组切换排序算法-插入排序
            return;
        }
        int[] count = new int[R + 2];
        //计算频率
        for (int i = lo; i <= hi; i++) {
            count[charAt(a[i], d) + 2]++;
        }
        //将频率转换为索引
        for (int i = 0; i < R + 1; i++) {
            count[i + 1] += count[i];
        }
        //数据分类
        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] - 1, d + 1);
        }
    }

    public static void main(String[] args) {
        String[] a = new String[]{"she",
                "sells",
                "seashells",
                "she",
                "by",
                "the"};
        MSD.sort(a);
        Assert.check(a[0].equals("by"));
        Assert.check(a[1].equals("seashells"));
        Assert.check(a[3].equals("she"));
        Assert.check(a[5].equals("the"));
    }

}