字符串排序

低位优先的字符串排序

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];
            }
        }
    }
}

高位优先的字符串排序

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) {
        //以第d个字符为键将a[lo]至a[hi]排序
        if (hi <= lo + M) {
            Insertion.sort(a, lo, hi, d);  //当子数组很小
            return;
        }
        int[] count = new int[R + 2];  //计算频率，R+2是因为charAt可能产生-1
        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 r = 0; r < R; r++) {
            sort(a, lo + cout[r], lo + count[r + 1] - 1, d + 1);
        }
    }
}

对很小的数组进行插入排序：

public class SmallSD {
    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[i], d); j--) {
                exch(a, j, j - 1);
            }
        }
    }

    private static boolean less(Sring v, String w, int d) {
        return v.substring(d).compareTo(w.substring(d)) < 0;
    }
}

三项字符串快速排序

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++;
        }
        // a[lo..lt-1] < v=a[lt..gt] < a[gt+1..hi]
        sort(a, lo, lt - 1, d);
        if (v >= 0) sort(a, lt, gt, d + 1);
        sort(a, gt + 1, hi, d);
    }
}

性能分析

在将基于大小为R的字母表的N个字符串排序的过程中调用charAt()方法次数的增长数量级（平均长度为w，最大长度为W）。

算法	是否稳定	原地排序	运行时间	额外空间	优势领域
字符串的插入排序	是	是	N到N^2之间	1	小数组或是已经有序的数组
快速排序	否	是	Nlog^2N	logN	通用排序算法，特别适合用于空间不足的情况
归并排序	是	否	Nlog^2N	N	稳定的通用排序算法
三项快速排序	否	是	N到NlogN之间	logN	大量重复键
低位优先的字符串排序	是	否	NW	N	较短的定长字符串
高位优先的字符串排序	是	否	N到Nw之间	N+WR	随机字符串
三项字符串快速排序	否	是	N到Nw之间	W+logN	通用排序算法，特别适合用于含有较长公共前缀的字符串