桶排序

计数排序&基数排序

思路来源

一周刷爆LeetCode，算法大神左神（左程云）耗时100天打造算法与数据结构基础到

笔记内容

• 特点：不基于比较的排序

• 算法思路

  1. 计数排序

     申明一个定长数组，遍历数据并在对应数值的下标频率统计加一，最后根据频率数组进行输出。

     待排序的数据必须有范围限制，能够用数组进行频率统计

  2. 基数排序

     找出最大位数，根据最大位数补全小于位数数值（在前面加0），根据位数从低到高进行排序（个 --> 十 --> 百 .....）

     在优化算法中，用词频表实现进行统计，然后逆序遍历数组，按照词频表中给出的最后一位下标进行填充排，输出排序。

     待排数据必须有进制

• 代码实现

  public class BucketSorting {
      public static void main(String[] args) {
         int[] target1 = {4,55,66,77,4,55,188,15,9,44,65};
         //countingSort(target1);
          bucketSort(target1);
      }
  
      //计数排序
      public static void countingSort(int[] target){
          int[] frequency = new int[200];
          int[] result = new int[target.length];
          int count = 0;
          for (int i = 0; i < target.length; i++) {
              frequency[target[i]]++;
          }
          for (int i = 0; i < frequency.length; i++) {
              if(frequency[i] != 0){
                  while (frequency[i] > 0){
                      result[count] = i;
                      count++;
                      frequency[i]--;
                  }
              }
          }
          print(result);
      }
  
      //基数排序
      public static void bucketSort(int[] target){
          int maxBit = maxBitNum(target); //最大位数
          int total = 10;
          for (int i = 1; i <= maxBit ; i++) {
              int[] frequency = new int[total];
              int[] result = new int[target.length];
              for (int j = 0; j < target.length; j++) {
                  int num = appointNum(target[j],i);
                  frequency[num]++;
              }
              for (int j = 1; j < frequency.length; j++) {
                  frequency[j] += frequency[j-1];
              }
              for (int j = target.length-1; j > -1 ; j--) {
                  int index = frequency[appointNum(target[j],i)]-1;
                  result[index] = target[j];
                  frequency[appointNum(target[j],i)]--;
              }
              target = result;
              //print(result);
          }
          print(target);
      }
  
      public static void print(int[] target){
          for (int i = 0; i < target.length; i++) {
              System.out.print(target[i]+" ");
          }
          System.out.println("");
      }
  
      //获取最大位数
      public static int maxBitNum(int[] target){
         int max = Integer.MIN_VALUE;
          for (int i = 0; i < target.length; i++) {
              int num = 0;
              int temp = target[i];
              while (temp != 0){
                  num++;
                  temp /= 10;
              }
              if(max < num){
                  max = num;
              }
          }
          return max;
      }
  
      //获取位置数
      public static int appointNum(int target,int d){
         return (target/(int)Math.pow(10,d-1))%10;
      }
  }