算法（第4版） Chapter 5.1 字符串排序

柔情只为你懂 2022-02-23 12:58 147阅读 0赞

Algorithms Fourth Edition  
Written By Robert Sedgewick & Kevin Wayne  
Translated By 谢路云  
Chapter 5 Section 1 字符串排序

--------------------

参考资料  
[http://blog.csdn.net/guanhang...][http_blog.csdn.net_guanhang...]

--------------------

# 引入 #

*  字符串方便比较吗？不方便
 *  怎么办呢？把每一个字符对应成一个数字 toIndex(c)
 *  一共有多少个字符？ R个
 *  数字R需要几个二进制位来表示？ lgR个
    
     *  如扩展ASCII码共256个字符，需要8位二进数来表示。
 *  区别
    
     *  Alphabet.toChar(index) 把数字对应成字符。这个是字母表的第i位
     *  String.charAt(index) 字符串的第i位是什么字符。这个是字符串的第i位。  
        字符表API

--------------------

![字符表API][API]

## 标准字符表 ##

![标准字符表][2948898247-58821b0eaa1e2_articlex]

# 键索引计数 #

输入字符串和字符串对应的组别（组别也是字符串的键）  
在满足组别有小到大排序的情况下，将字符串按字母顺序排序  
![20160424212942624][]

# 算法步骤 #

第一步，记录组别的频率  
（为了得到某个字符串在排序后的范围，比如组别2肯定在组别1后面，在组别3前面，把每个组别有多少个人记录下来，方便我们定位）

*  共 **5** 组，从第 0 组到第 4 组。 创建数组大小为 **6**（ = 5 + 1 ）。int\[\] count=new count\[6\];
 *  count\[\]记录频率
 *  记录的位置是键值+1，加1是方便后期更新键的位置起点

![20160424211047487][]

第二步，转化为索引  
（得到每个组别的**位置起点**）

![20160424211226461][]

第三步，分类

*  创建一个副本（因为在遍历正本，正本当前不能被覆盖）
 *  **按组别** 丢进副本里，丢到该组别的位置起点处
    
     *  当前的数据是有序的
     *  下面是个人的小思考，可不用看
     *  如果原先的数据是有序的，那么在每个组别中的数据也将会是有序的
     *  如果原先的数据是无序的，那么先排序
     *  有种递归的思想
        
         *  外面先排好序，里面一层一层的去排序
         *  里面先排好序，外面一层一层的去排序
 *  该组别的位置起点 **向后挪一位** （因为当前位被用了）

第四步，复制

*  把副本的数据拷贝回正本

![20160424211349258][]

## 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<N;i++) //访问数组2N次
        count[a[i].key()+1]++;
    // Transform counts to indices.
    for(int r = 0;r<R;r++) //访问数组2R次，进行R次加法
        count[r+1]+=count[r];
    // Distribute the records.
    for(int i = 0;i<N;i++) //访问数组3N次，使计数器值增大N次并移动数据N次
        aux[count[a[i].key()]++]=a[i];
    // Copy back.
    for(int i = 0;i<N;i++) //访问数组2N次，移动数据N次
        a[i]=aux[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);
        }
    }

[http_blog.csdn.net_guanhang...]: http://blog.csdn.net/guanhang89/article/details/51240654
[API]: /images/20220223/9eb75b654c9a4b5fab0216f70832814c.png
[2948898247-58821b0eaa1e2_articlex]: /images/20220223/ae781a8a354c49f8968336527b16ad17.png
[20160424212942624]: /images/20220223/1cb9f72d7f7b4285be2ba4bb692e4323.png
[20160424211047487]: /images/20220223/3efdb710d9014edfbc111a1d0322b0c0.png
[20160424211226461]: /images/20220223/5ec750db143942199976f2f4f6f06dab.png
[20160424211349258]: /images/20220223/1838e068faff4156a719bc84d43b9903.png