Algorithms Fourth Edition
Written By Robert Sedgewick & Kevin WayneTranslated By 谢路云Chapter 5 Section 1 字符串排序参考资料
引入
字符串方便比较吗？不方便
怎么办呢？把每一个字符对应成一个数字 toIndex(c)
一共有多少个字符？ R个
-
数字R需要几个二进制位来表示？ lgR个
如扩展ASCII码共256个字符，需要8位二进数来表示。
-
区别
Alphabet.toChar(index) 把数字对应成字符。这个是字母表的第i位
String.charAt(index) 字符串的第i位是什么字符。这个是字符串的第i位。
字符表API
标准字符表
键索引计数
输入字符串和字符串对应的组别（组别也是字符串的键）
在满足组别有小到大排序的情况下，将字符串按字母顺序排序
算法步骤
第一步，记录组别的频率
（为了得到某个字符串在排序后的范围，比如组别2肯定在组别1后面，在组别3前面，把每个组别有多少个人记录下来，方便我们定位）共 5 组，从第 0 组到第 4 组。 创建数组大小为 6（ = 5 + 1 ）。int[] count=new count[6];
count[]记录频率
记录的位置是键值+1，加1是方便后期更新键的位置起点
第二步，转化为索引
（得到每个组别的位置起点）
第三步，分类
创建一个副本（因为在遍历正本，正本当前不能被覆盖）
-
按组别 丢进副本里，丢到该组别的位置起点处
当前的数据是有序的
下面是个人的小思考，可不用看
如果原先的数据是有序的，那么在每个组别中的数据也将会是有序的
如果原先的数据是无序的，那么先排序
-
有种递归的思想
外面先排好序，里面一层一层的去排序
里面先排好序，外面一层一层的去排序
该组别的位置起点 向后挪一位 （因为当前位被用了）
第四步，复制
把副本的数据拷贝回正本
KeyIndexedCounting 代码
-
复杂度
访问数组11N+4R+1次
索引计数法是稳定的
int N = a.length;String[] aux = new String[N]; //访问数组N次int[] count = new int[R+1]; //访问数组R+1次// Compute frequency counts.for(int i = 0;i
低位优先排序
结合索引排序，从字符串的低位（从右面开始），从右到左，每个字符都当一次该字符串的键，给整个字符串排序
以下代码的局限性：每个字符串的长度是相等的。稍作修改可适应不等长的字符串。
LSD 代码
-
复杂度
-
访问数组
最坏情况：~7WN + 3WR 次
最好情况：8N+3R 次
空间： R+N
-
public class LSD { public static void sort(String[] a, int W) { // Sort a[] on leading W characters. int N = a.length; int R = 256; String[] aux = new String[N]; for (int d = W - 1; d >= 0; d--) { // Sort by key-indexed counting on dth char. int[] count = new int[R + 1]; // 创建数组大小为R+1 for (int i = 0; i < N; i++) // Compute frequency counts. 频率 count[a[i].charAt(d) + 1]++; for (int r = 0; r < R; r++) // Transform counts to indices. 索引 count[r + 1] += count[r]; for (int i = 0; i < N; i++) // Distribute. 按组别丢到副本里去 aux[count[a[i].charAt(d)]++] = a[i]; for (int i = 0; i < N; i++) // Copy back. 赋回正本 a[i] = aux[i]; } }} 高位优先排序
考虑不等长字符串的比较
e.g. as 排在 aspect 前面。因此增加一个组别，记录字符为空的频次。
-
这个组别应该在最前面，为count[0]
怎么让字符为空落到count[0]里呢？
字符为空时，对应数字为0（具体实现的时候为返回-1，再在-1的基础上+1）
其他字符对应的数字在原来基础上+1（就是给0腾个位置出来，不占用0，所有位次顺移）
-
int[] count=new int[R+2];
原为R+1
再在原来的基础上+1，即为R+2
字符为空，也即搜寻的时候超出字符串的原来长度
MSD 代码
public class MSD { private static int R = 256; // radix 256个字符 private static final int M = 15; // cutoff for small subarrays 数组小到多少的时候用插入排序？ private static String[] aux; // auxiliary array for distribution 副本 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); } // Sort from a[lo] to a[hi], starting at the dth character. 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]; // 数组大小R+2 for (int i = lo; i <= hi; i++)// Compute frequency counts.频次，只累计了hi-lo+1次 count[charAt(a[i], d) + 2]++; // 每个对应数字在原来基础上+1 for (int r = 0; r < R + 1; r++) // Transform counts to indices. 索引 count[r + 1] += count[r]; for (int i = lo; i <= hi; i++) // Distribute.丢到对应组别里去 aux[count[charAt(a[i], d) + 1]++] = a[i]; // 每个对应数字在原来基础上+1 // aux的赋值从aux[0]开始，到aux[hi-lo]结束 // 在这里count会发生变化。原来这里的count只是为了移动到下一位为下一个元素找位置用，现在这里的count[i]还可以通过是否到达count[i+1]来判断是否可以结束递归 for (int i = lo; i <= hi; i++) // Copy back. 注意aux的起终点和a的对应关系 a[i] = aux[i - lo]; // Recursively sort for each character value. for (int r = 0; r < R; r++) //私认为初始化条件r=1更好，因为r=0都是字符为空的子字符串 sort(a, lo + count[r], lo + count[r + 1] - 1, d + 1); // 将当前相同字符的分为一组，每组以下一位字符为比较对象排序 }} -
LSD
从右到左，每次都是N个字符作为一组，整体进行排序
-
MSD
从从到右，每次是第i位相同的字符串分成一组，按第i+1位排序
三向字符串快速排序
可以处理等值键，较长公共前缀，小数组，取值范围较小的键
避免创建大量空数组，不需要额外空间
Quick3string 代码
-
复杂度
平均： 2NlnN
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; // 从第二个字符串的d位开始 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) // d位字母相同且不为空，则这部分从下一位开始再比较 sort(a, lt, gt, d + 1); sort(a, gt + 1, hi, d); }}