引用资料

[1] algs4 MSD.java 完整代码实现

http://algs4.cs.princeton.edu/51radix/MSD.java.html

[2] 搭建java环境以及安装algs4程序（win版本，其余可参考官网for students部分）

http://algs4.cs.princeton.edu/windows/

说明

完整源码（见引用[1]）；
环境设置（见引用[2]）；
这个精彩的实现值得花时间一行一行怼明白；

MSD

高位优先的字符串排序（most significant digit first) ：
- 从左往右，递归排序；
- 适合于字符串长度不一的情况；
- 出现大量重复的字符串是最坏；

字母表基数R

选用一个 R=26 的字母表，涵盖小写字母（这个选择会影响后面代码写下标）；
注意这个说法索引值，和后面的数组下标是不同的，这个代码容易出错就是下标和索引值的对应关系没搞明白；

索引值	字母
a
1	b
…. …
18	s
19	t
…. …
25	z

待排序的字符串

she
sells
seashells
by
the
sea
shore
the
shells
she
sells
are
surely
seashells

逐行代码解释

代码的大框架

★ 标记的注释是需要仔细区分的盲点；

// 算法启动
    public static void sort(String[] a) {
        // 输入一个字符串数组 a 获取字符串数组的长度（即待排序的字符串个数）
        int n = a.length;

        // 声明一个备用字符串数组aux 用于排序时回写
        String[] aux = new String[n];

        // 启动递归排序 初始排序长度涵盖全部字符串[0,n-1]
        // aux作为参数传入，相当于一个全局变量，aux只声明了一次 ★
        sort(a, , n-, , aux);
    }


    // 将字符串数组从 [lo，hi]的元素a[i] 按照 第d个字母 排序
    private static void sort(String[] a, int lo, int hi, int d, String[] aux) {

        // 函数局部变量，每次sort 都会重新创建一个count[]数组 ★
        // 注意cout[]的长度为R+2 ★
        int[] count = new int[R+];

        // 计算频率
        for (int i = lo; i <= hi; i++) { }
        // 频率转换成索引
        for (int r = ; r < R+; r++) { }
        // 数据分布
        for (int i = lo; i <= hi; i++) { }
        // 回写
        for (int i = lo; i <= hi; i++) { }
        // 递归排序
        for (int r = ; r < R; r++) { }

    }

频率计算

MSD

// 频率计算
        int[] count = new int[R+];
        for (int i = lo; i <= hi; i++) {
            int c = charAt(a[i], d);
            count[c+]++;
        }

解释

// 频率计算
        // 1. count数组的作用是记录每个字母出现的频率（就是出现次数）
        // 2. 把长度声明成 R+2 ;
        //    R 个位置用来放对应字母的出现次数
        //    1 个位置用来应对达到字符串结尾
        //    1 个位置是用于后面转化为索引 ★（下个标题说明）
        int[] count = new int[R+];

        // for是一个从lo到hi的循环，就是遍历要排序的那些字符串，可能这一波排这5个字符串，
        // 可能这一波排那3个字符串，实现只关注 子字符串数组 的效果；
        for (int i = lo; i <= hi; i++) {

            // 假设现在是第一轮排序，也就是按照首字母排，d = 0
            // 那么，以第一个字符串she为例，she的首字母是s
            // s 在字母表R的 索引值 是 18（注意字母表的索引值是从 0 开始记的）
            // c = 18  
            int c = charAt(a[i], d);

            // c + 2 = 20 count[20]++ 此时count[20] = 1
            // 纵观全部的字符串，以首字母为准计算频率的话
            // 最终有 10 个 s 开头的字符串，
            // 也就是 sells seashells sea shore shells she sells surely seashells


            count[c+]++;
        }

            // 该循环结束之后

            // a 打头的字符串个数是 count[0+2] =  count[2] = 1
            // b 打头的字符串个数是 count[1+2] =  count[3] = 1
            // s 打头的字符串个数是 count[18+2] = count[20] = 10
            // t 打头的字符串个数是 count[19+2] = count[21] = 2
            // 其余位置 count[r] = 0 因为没有这些字母打头

一般化描述，此时的 count[] 数组， 数组下标 r ， count[r] 代表的是
- 以第 d 个字母为准（目前是首字母）；
- 字母表中索引值为 r-2 的字符串个数；

频率转换成索引

MSD

// 频率转换成索引
        for (int r = ; r < R+; r++)
            count[r+] += count[r];

解释

// 频率转换成索引
        // 这是一个遍历字母表的循环，从r = 0 到 r = R
        for (int r = ; r < R+; r++)
        // 每一次循环，都使得自己加上前一项的值
            count[r+] += count[r];

// 循环前count[]数组
r                            
                                                                         
空白表示 

// 循环后count[]数组
r                            
                                       

// 手工打可能错了，简单点说就是，循环后
        count[] = 
        count[] = 
        count[~] = 
        count[] = 
        count[~]=

思考

此时 count[] 不再表示是出现次数，而是某个字母的回到 a[] 的起始位置：
- count[1] = 0 ，说明 r = 1 这个数组下标对应的字母在将来的排序结果回到数组 a[] 时会出现在下标为 count[1] 的位置；
- 这里 count[1]= 0 也就是会出现在 a[] 的首位，会出现在排序结果首位必然是a打头的字符串 are 啊！
- 字母a 在字母表R中的索引值是， count[1] 中的 1 是 0+1 ；
再看一个字母，比如 s ：
- 从结果往回推，s前面有一个a打头，一个b打头，也就是排在全部s打头字符串前面的字符串有两个；
  - 再看 count[19] ，刚好 count[19] = 2 ，这不是巧合，这就是循环加出来的；
  - 循环的作用现在终于清楚了，本质就是不断计算前面总共有多少个字符串（例如：如果去排队，你前面有三个人，那么你就是第四个人，你就排在第四位了）；
  - 而 count[19] 中的 19 刚好就是 s 在字母表R中的索引值+1， 19 就是 18+1 ；
  - 可是 count[3~19] 全是 2 啊，这不会混淆吗？不会，因为待排序的字符串没有以字母c 到字母 r打头的，本轮是以 d = 0 也就是首字母排序，只看首字母；
一般化描述，此时的 count[] 数组， 数组下标 r ， count[r] 代表的是：
- 在字母表R中索引值是r - 1的字母在将来的排序结果中的该被摆放的起始位置下标；

数据分类

MSD

// 数据分类
        for (int i = lo; i <= hi; i++) {
            int c = charAt(a[i], d);
            aux[count[c+]++] = a[i];
        }

解释

// 数据分类
      // 循环遍历需要排序的子字符串数组 从lo到hi
        for (int i = lo; i <= hi; i++) {

        // c 是字母在字母表R中的索引值
        // d = 0 ，取得是字符串的首字母 比如she 取得就是s，
        // 就是找s 在字母表中的索引值 c = 18
            int c = charAt(a[i], d);

        // aux 是函数参数数组，相当于全局变量，因为只声明一次；
        // 但是每次sort都只会用aux的[0, hi - lo] 部分（下一个标题解释）
        // 下面这句需要拆成 3 个 步骤 ： 

        // 1. 取出 count[c+1]， 比如she（首字母索引值）的 c = 18, 
        //    要用count[18 + 1] = count[19] = 2
        //    这里其实是上个标题说的，count[19]存的才是c = 18对应字母s的起始位置下标;

        // 2. aux[count[c+1]] = a[i] 
        //    没有写错的，就是先完成赋值，才会进行其他++操作；
        //    这里是说， aux[count[c+1]] = aux[2] = a[i] = she
        //    也就是说 she 先被放到辅助数组aux下标为2（也就是第三个位置）
        //    因为前面要留着位置放 a 打头的 are 以及 b 打头的by 啊！
        //    空两个位置妥妥的，问，为什么知道留两个位置？
        //    答，前面一步索引算过了，都空好位置了，都算好每个不同字母打头需要的起始位置下标了！
        //    到此为此，对于本次循环为什么是从lo到hi也会有新的理解；
        //    因为这下我们需要做的就是把待排序的字符串们一个个当到辅助数组合适的位置上，
        //    当然是针对字符串的个数来遍历了，不要和前面的R弄混淆；

        // 3. count[c+1]++
        //   count[c+1] 也就是 cout[19] ++ 也就是cout[19] = 2 + 1 = 3
        //   排好了一个字符串，用掉了一个位置，当然要加1
        //   注意，这里是在对count[]操作，而不是对aux操作
        //   aux只有存取作用，值要么被覆盖要么不妨东西

             aux[count[c+]++] = a[i];

}

回写

MSD

// 回写
        for (int i = lo; i <= hi; i++) 
            a[i] = aux[i - lo];

解释

// 回写
  // 回写就是把暂时存放在aux中的排好序了的字符串们回写到元字符串数组
  // 循环从lo到hi，这是迁就a[]的写法， 因为本轮sort循环是排序sort(a,lo, hi, d)
  // 也就是元字符串数组从[lo，hi]的部分需要排序
  // 自然回写的时候，如果循环从lo到hi，那么自然回写到a[i]。


        for (int i = lo; i <= hi; i++) 
            a[i] = aux[i - lo];

为什么axu是[i - lo]？

这里需要回到本文代码框架大标题我打了★的两处注释，回忆一下 :
- aux[] 是一个参数传入每次调用的数组，相当于一个全局变量，大小是待排序的字符串个数，也就是与字符串数组 a 的长度相同；
- count[] 是一个在每次 sort 调用开始都会重新声明创建的数组, count[] 的大小时字母表大小R
- 本质就是前面一再提及的aux[]每次只会被用到[0，hi-lo]部分;
- 简单想想就明白，在用首字母进行排序的时候， aux 当然是从 [0，len-1] 都会被用到（此时， hi 也就是 len -1， lo = 0 ），而随时排序的进行，我们进入到对字符串的排序之中，每次lo和hi都会变化：
  - 但是要知道每次调用的count都是全新的count啊！这个count可记不住当前需要排序的字符串在整个全部过程前面有多少字符串排在它前面 ;
  - 比如说，我们现在已经按照首字母排好序了，我们有10个s打头的字符串，这时候，我们进入到一下递归调用，对全部这些以s打头的字符串按照他们的第二个字母排序，she的第二个字母是h，sea的第二个字母是e，selles第二个字母也是e，也就是光看这里，只能知道h前面有两个e，但是这里的count是看不到are和by的，所以如果就 she sea selles 这三个字符串按照第二个字母排序的话，毫无疑问，这时候的 count 数组对应到h记下 h 前面有的字符串个数就是2，而不会是包括are以及by的4；
- 没错，在最终的排序结果a[]里面，are by就是在she前面，但是这里count看不到。正是因为看不到，根据这里的count，aux的 aux[0] aux[1] aux[2] 将被不断地拿来分别存放类似于 she sea selles 的待排序字符串，然后被回写到a的 a[lo] a[lo+1] a[lo+1] ，因此这个循环可以有另外一种写法，那就是:

for(int index =  ; index <= hi - lo; index++)
     a[lo + index] = aux[index];

//  我认为这种写法对于aux的辅助作用表述地更清晰，
//  aux之所以需要被声明成a.length，仅仅只是因为在按照首字母排序的时候，它所有的位置都要被用到，
//  而随着排序进行，一直都只有[0, hi -lo]这些位置才会被用到了；

递归排序

MSD

// 递归排序
        for (int r = ; r < R; r++)
            sort(a, lo + count[r], lo + count[r+] - , d+, aux);

解释

// 递归排序

        // 什么是从左往右？ 就是sort里面那个（， ， ，d+1，）的d+1 ; 
        // 以she距离，d = 0 就是按照 s 去排序，d = 1 就是按照 h 去排序
        // 更准确的说应该是，she selles sea 
        // 1. d = 0 时，以首字母去排序，都是s；
        // 2. d = 1 时候，以每个字符串的第二个字母去排序
        //  she  是 h
        // selles  是 e
        // sea  是 e
        // d = 1 排序的时候是用 h e e 在比较了，所以叫做从左往右；


        // 那么这个r = 0 到 r < R 的循环又是怎么回事呢？
        // 这是在确定需要排序的子字符串数组范围；
        // 比如首轮按照首字母排好序的10个s打头，肯定需要再排一次的；
        // 我们知道根据上面的演算，每次数据分类都有个 aux[count[c+1]++] = a[i];
        // 这个++操作不得了，比如s， c[18 +1] = c[19] = 2 一路++，到最后首轮结束
        // count[19] = 12 ，因为是从2 加个10次，12没问题；

        // 那么12代表的是什么？
        // 12代表的是从a[]的视角看，到包含了全部的s打头的字符串为止，有12个字符串；
        // 12就是排在全部s打头的字符串后面的第一个字符串，也就是本例中t字母打头的字符串的起始下标
        // 这个下标必然限定了所有t打头字符串的上限，一刀就切在这里了，
        // 之后t打头字符串内部怎么排会也只会是12（含12）开始之后的事情了，
        // 因为前面可有12个或a或b或s开头的家伙啊；


        // 此时的count[19] 
        // 就是 排在 字母索引值为19-1的字母s 后面的第一个字符串的起始下标；
        // 也就是t 的起始下标；

        // 而count[18 + 1] - 1 恰好就是 字母索引值为18 的字母s 的结束下标；

        // s 前面的字母是 b ，s 的起始下标就是 索引值为2-1的字母b 的count[2] = 2
        // 实际上此时count[2 ~ 18]全是2，因为不存在c到r打头的字符串，
        // 这部分count[]的值从转换为索引之后就一直保留到现在了；
        // s 的结束下标， 是 count[18+1] - 1

        // 首轮排序的时候lo = 0 ， hi = len - 1；
        // sort(a, 0 + count[18], 0 + count[18+1] - 1) = sort(a, 2, 11) 
        // count[18] = 2 转换为索引后一直不变的
        // count[19] = 12 见上面
        // 就是对s打头的进行递归排序；

        // sort(a, 0 + count[19], 0 + count[19+1] - 1) = sort(a, 12, 13)
        // count[19] = 12 见上面
        // count[20] = 14 （转换为索引后的count[20] = 12， t出现两次，刚好变成14）
        // 就是对t打头的进行递归排序；

         // 一个子字符串数组的开头接着一个子字符串数组的结尾；
         // 一个子字符串数组的结尾接着一个子字符串数组的开头；

         // 这个循环有点绕，之所以要从r = 0 到 r = R；
         // 是因为我们也不知道那些字母在本轮被拿来排序了，那些没有，以及那些字母存在那些不存在；
         // lo限定了子字符串数组的整体开始；
         // 横着看，这就是DFS

        for (int r = ; r < R; r++)
            sort(a, lo + count[r], lo + count[r+] - , d+, aux);

一般化描述，此时数组下标 r ， count[] 表示的是：
- count[r] 是字母表R中索引值为 r的字母的起始下标位置；
- cout[r + 1] - 1 就是字母表R中索引值为 r的字母的结束下标位置；
比如说已经进入到了子数组，然后又3个元素一堆，5个元素一堆，4个元素一堆，这样分成三块的话：
- 3-元素 的起始下标肯定是 [lo+0] ；
- 5-元素 的肯定是 [lo+3] ；
- 4-元素 的肯定是 [lo+8] ；

补充

转入插入排序

private static void sort(String[] a, int lo, int hi, int d, String[] aux) {

        if (hi <= lo + CUTOFF) {
            insertion(a, lo, hi, d);
            return;
        }

书上提出在面对非常少的元素时，转入插入排序是可以提高效率的，原因在于：
- 递归排序的解释部分可以看到，以按照首字母排序举例，实际上会产生 R 个 sort ,相当于对从a到z的每个字母都会问一遍，有没有以这个字母打头的需要排序的，因此需要转入插排；
- algs4的插入排序，对于 lo>=hi 的时候会终止循环，这个在上面的代码没有写出来；
- 比如对于字母 g ，并没有以 g 打头的字符串， g 对应的 count[7] 和 h 的 count[8] 都是2，从现实角度光光看这两个变量就是， g 前面有 2 个字符串， h 前面也有 2 个字符串，那么必然不存在以 g 打头的，不然 count[7] 不会是2的，因此当被问到有没有 g 打头的需要进行子字符串数组调用的时候，会产生 sort（a,2,1） lo = 2,hi = 1 这个调用会终止的；

达到字符串尾部

private static int charAt(String s, int d) {
        assert d >=  && d <= s.length();
        if (d == s.length()) return -;
        return s.charAt(d);
    }

举例字符串 ab 和 abc 很明显，ab 是访问不到d = 2 第三个字母的，因为没有第三个字母，那么charAt（）就返回-1，否则返回字母表中的索引值；

// 频率计算
 count[c+]++;

c = - 时， count[c+] = count[]++; count[] = ;
c =  , 也就是遇到了字母 a ， count[ + ] = count[]++ = ;

固定地拿 count[1] 这个位置来记录 ab 这样的到达了字符串结尾的情况；
使得更短地总是排在前面，达到尾部了相当于获得了更前位的字母，比a还要前面一位；
这就是为什么 count[] 在每次声明的时候需要声明成 [R+2] 的长度；
因为 count[1] 用来放 -1 的情况了， count[0] 要留着计算索引，字母表的长度是 R ，所以最终是 1 + 1 + R = R + 2 ;

心得体会

algs4 是一个完整的代码库，如果要运行这个库里的代码需要安装按照官网的教程安装环境，我装了 linux 的版本、也装了 windows 的，后者容易出问题还是JDK环境变量设置的部分，不出错的话 windows 的版本，是可以一键安装的；
直接上手就啃 MSD.java 的代码可能会非常痛苦，毕竟既要给索引计算预留一个位置，又要给达到字符串尾部预留一个位置，还有可能在待排序的字符串个数 n 以及字母表长度 R 这些变量与一个时时刻刻转变含义的 count[] 数组进行交流时会感到手足无措；
因此 algs4 这本书第五章前面关于频率计算、索引转换、回写的讲解，是一定要先看的，在那里的 count[] 大小是 R+1 ，只给索引转换预留了一个位置，因为那些代码片段也是服务于 LSD.java 的 低位优先字符串排序LSD 适用于等长的字符串排序，所以不需要给达到字符串尾部预留位置了，大家长度都一样，在学习 MSD.java 一定要就着书上的轨迹图看，不然不容易看懂；
比如本例中正是由于字母表是从开始记得，所以才会对应的这些语句，这里多写少写一个 +1 -1 ，不是数组越界的问题而是根本就会出错，实际上书在这个部分的代码还特意标红来醒目，可见这里多容易错；
从代码推处理过程还是可以很容易顺藤摸瓜的，但是设计算法就很难了，这点还需要努力。

[算法] 关于algs4 MSD.java 高位优先的字符串排序 的逐行代码解释引用资料说明MSD字母表 基数R待排序的字符串逐行代码解释补充心得体会

引用资料

说明

MSD

字母表 基数R

待排序的字符串

逐行代码解释

代码的大框架

频率计算

MSD

解释

频率转换成索引

MSD

解释

思考

数据分类

MSD

解释

回写

MSD

解释

为什么axu是[i - lo]？

递归排序

MSD

解释

补充

转入插入排序

达到字符串尾部

心得体会

继续阅读

[算法] 关于algs4 MSD.java 高位优先的字符串排序的逐行代码解释引用资料说明MSD字母表基数R待排序的字符串逐行代码解释补充心得体会

字母表基数R