content: package com.aaja.demo.basic;
  
  import java.util.ArrayList;
  import java.util.Arrays;
  
  /**
   * <p>Title: Lee10_RadixSort</p>
   * <p>Description: 基数排序</p>
   *
   * ①基本思想：
   *      基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。
   *      有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高
   *      优先级高的在前，高优先级相同的低优先级高的在前。
   * ②算法描述：
   *      取得数组中的最大数，并取得位数；
   *      arr为原始数组，从最低位开始取每个位组成radix数组；
   *      对radix进行计数排序（利用计数排序适用于小范围数的特点）；
   * @author aaja
   * @date 2020/7/22 21:20
   */
  public class Lee10_RadixSort {
  
      public int[] sort(int[] sourceArray) throws Exception {
          // 对 arr 进行拷贝，不改变参数内容
          int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
  
          int maxDigit = getMaxDigit(arr);
          return radixSort(arr, maxDigit);
      }
  
      /**
       * 获取最高位数
       */
      private int getMaxDigit(int[] arr) {
          int maxValue = getMaxValue(arr);
          return getNumLenght(maxValue);
      }
  
      private int getMaxValue(int[] arr) {
          int maxValue = arr[0];
          for (int value : arr) {
              if (maxValue < value) {
                  maxValue = value;
              }
          }
          return maxValue;
      }
  
      protected int getNumLenght(long num) {
          if (num == 0) {
              return 1;
          }
          int lenght = 0;
          for (long temp = num; temp != 0; temp /= 10) {
              lenght++;
          }
          return lenght;
      }
  
      private int[] radixSort(int[] arr, int maxDigit) {
          int mod = 10;
          int dev = 1;
  
          for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
              // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
              int[][] counter = new int[mod * 2][0];
  
              for (int j = 0; j < arr.length; j++) {
                  int bucket = ((arr[j] % mod) / dev) + mod;
                  counter[bucket] = arrayAppend(counter[bucket], arr[j]);
              }
  
              int pos = 0;
              for (int[] bucket : counter) {
                  for (int value : bucket) {
                      arr[pos++] = value;
                  }
              }
          }
          return arr;
      }
  
      /**
       * 自动扩容，并保存数据
       *
       * @param arr
       * @param value
       */
      private int[] arrayAppend(int[] arr, int value) {
          arr = Arrays.copyOf(arr, arr.length + 1);
          arr[arr.length - 1] = value;
          return arr;
      }
  
  }
  