算法学习：基数排序

背景介绍：
是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机（Tabulation Machine）上的贡献。

算法规则：
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。基数排序可以采用两种方式分别是LSD（Least Significant Digital）和 MSD（Most Significant Digital）；我们以LSD方式为例，从数组R[1..n]中每个元素的最低位开始处理，假设基数为radix，如果是十进制，则radix=10。基本过程如下所示：
1.计算R中最大的元素，求得位数最大的元素，最大位数记为distance；
2.对每一位round<=distance，计算R[i] % radix即可得到；
3.将上面计算得到的余数作为bucket编号，每个bucket中可能存放多个数组R的元素；
4.按照bucket编号的顺序，收集bucket中元素，就地替换数组R中元素；
5.重复2~4，最终数组R中的元素为有序。

代码实现（Java版本）

升序排序法(LSD)：

      /**
       * 基数排序法
       * 升序排列
       * @param data
       */
      public  void sortByAsc(int[] data) {
          /** step1:确定排序的趟数*/     
          int max=data[0];     
          for(int i=1;i<data.length;i++){     
              if(data[i]>max){     
                  max=data[i];     
              }     
          }   
          /** step2:判断位数*/
          int digit = 0;       
          while(max > 0){     
              max/=10;     
          digit++;     
          }  
          /**初始化一个二维数组，相当于二维数组，可以把重复的存进去*/
          List<ArrayList<Integer>> temp = new ArrayList<>();
          for(int i = 0;i < 10;i++){
              temp.add(new ArrayList<Integer>());
          }
          /**开始合并收集*/
          for(int i = 0; i < digit; i++){
              /** 对每一位进行排序 */
              for(int j = 0; j < data.length; j++){
                  /**求每一个数的第i位的数，然后存到相对应的数组中*/
                  int digitInx = data[j]%(int)Math.pow(10, i + 1)/(int)Math.pow(10, i);
                  ArrayList<Integer> tempInside = temp.get(digitInx);
                  tempInside.add(data[j]);
                  temp.set(digitInx,tempInside );
              }
              /**收集数组元素*/
              int count = 0;
              for(int k = 0;k < 10;k++){
                  for(;temp.get(k).size()>0;count++){
                      ArrayList<Integer> temp2 = temp.get(k);
                      data[count] = temp2.get(0);
                      temp2.remove(0);
                  }
              }
          }
      } 

升序排序法(MSD)：

      /**
       * 基数排序法
       * 降序排列
       * @param data
       */
      public  void sortByDesc(int[] data) {

          /** step1:确定排序的趟数*/     
          int max=data[0];     
          for(int i=1;i<data.length;i++) {     
              if(data[i]>max) {     
                  max=data[i];     
              }     
  
          }   
          /** step2:判断位数*/
          int digit = 0;       
          while(max > 0) {     
              max/=10;     
              digit++;     
          }  
          /**初始化一个二维数组，相当于二维数组，可以把重复的存进去*/
          List<ArrayList<Integer>> temp = new ArrayList<>();
          for(int i = 0;i < 10;i++) {
              temp.add(new ArrayList<Integer>());
          }
          /**开始合并收集*/
          for(int i = 0; i < digit; i++) {
              /** 对每一位进行排序 */
              for(int j = 0; j < data.length; j++) {
                  /**求每一个数的第i位的数，然后存到相对应的数组中*/
                  int digitInx = data[j]%(int)Math.pow(10, i + 1)/(int)Math.pow(10, i);
                  ArrayList<Integer> tempInside = temp.get(digitInx);
                  tempInside.add(data[j]);
                  temp.set(digitInx,tempInside );
              }
              int count = data.length - 1;
              for(int k = 0;k < 10;k++) { 
                  for(;temp.get(k).size()>0;count--) {
                      ArrayList<Integer> temp2 = temp.get(k);
                      data[count] = temp2.get(0);
                      temp2.remove(0);
                  }
              }
          }
      }