基本介绍

基数排序属于“分配式排序”，它通过元素的各个位的值，将元素放置对应的“桶”中
基数排序属于稳定性排序，效率高，但是过多的元素会出现虚拟机运行内存的不足（千万个元素）

基本思想

把元素统一为同样长度的数组长度 元素较短的数前面补0，比如（1 15 336 看成 001 015 336）
然后从最低位开始，以此进行排序
下图为动图演示：
基数排序 - 图1

代码

  1. import java.util.Arrays;
  3. /**
  4.  * @Author leijs
  5.  * @date 2021/8/17
  6.  */
  7. public class RadixSort {
  9.     public static void main(String[] args) {
  10.         int[] arr = {1, 4, 3, 6, 8, 4, 9, 6, 2};
  11.         int[] arr1 = sort(arr);
  12.         for (int i = 0; i < arr1.length; i++) {
  13.             System.out.print(arr1[i]);
  14.         }
  15.     }
  17.     public static int[] sort(int[] arr) {
  18.         // 获取最高位数
  19.         int maxDigit = getMaxDigit(arr);
  20.         return redixSort(arr, maxDigit);
  22.     }
  24.     private static int[] redixSort(int[] arr, int maxDigit) {
  25.         int mod = 10;
  26.         int dev = 1;
  28.         for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
  29.             // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
  30.             int[][] counter = new int[mod * 2][0];
  32.             for (int j = 0; j < arr.length; j++) {
  33.                 int bucket = ((arr[j] % mod) / dev) + mod;
  34.                 //自动扩容，并保存数据
  35.                 counter[bucket] = arrayAppend(counter[bucket], arr[j]);
  36.             }
  38.             int pos = 0;
  39.             for (int[] bucket : counter) {
  40.                 for (int value : bucket) {
  41.                     arr[pos++] = value;
  42.                 }
  43.             }
  44.         }
  45.         return arr;
  46.     }
  48.     private static int[] arrayAppend(int[] arr, int value) {
  49.         arr = Arrays.copyOf(arr, arr.length + 1);
  50.         arr[arr.length - 1] = value;
  51.         return arr;
  52.     }
  54.     private static int getMaxDigit(int[] arr) {
  55.         int max = arr[0];
  56.         for (int value : arr) {
  57.             if (max < value) {
  58.                 max = value;
  59.             }
  60.         }
  61.         return String.valueOf(max).length();
  62.     }
  63. }