基数排序

原理

  • 通过(arr[i]+””).length获得最大数的位数
  • 从0到9创建10个桶
  • 从个位开始，个十百千将数组中的数按顺序放入桶中，不足的按0算
  • 依次将他们从桶中取出
  • 再分别放入高一位次的桶中
  • 依次取出
  • 直至到最大位数

    代码实现

    ```javascript import java.util.Arrays;

/**

  • @author laoduan
  • @create 2020-05-09-22:20 */ public class RadixSort { public static void main(String[] args) {
    1.  int arr[] = {53,3,542,748,14,214};
    2.  radixSort(arr);
    }
  1. public static void radixSort(int[] arr){
  3.     //得到数组中最大的数的位数
  4.     int max = arr[0];
  5.     for(int i =1;i<arr.length;i++){
  6.         if(arr[i]>max){
  7.             max=arr[i];
  8.         }
  9.     }
  10.     int maxLength = (max+"").length();
  11.     //二维数组包含10个一位数组
  12.     //为了防止在放入数的时候数据溢出，则每个一位数组大小定为arr.length
  13.     //基数排序是使用空间换时间的经典算法
  14.     int [][] bucket = new int[10][arr.length];
  16.     //为了记录每个桶中实际存放了多少个数组，定义一个一位数组来记录每个桶每次放入的数据个数
  18.     int [] bucketElementCounts = new int [10];
  20.     for (int i = 0, n = 1;i<maxLength;i++,n*=10){
  21.         for (int j=0 ; j<arr.length ;j++){
  22.             //取出每个元素个位的值
  23.             int digitOfElement = arr[j]/n%10;
  24.             //放入对应的桶中
  25.             bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
  26.             bucketElementCounts[digitOfElement]++;
  27.         }
  28.         //按照这个桶的顺序（一位数组的下标一次取出数据，放入原来数组）
  29.         int index = 0;
  30.         for (int k = 0;k<bucketElementCounts.length;k++){
  31.             //如果桶中有数据，则放入原数组
  32.             if(bucketElementCounts[k]!=0){
  33.                 for (int l = 0;l<bucketElementCounts[k];l++){
  34.                     arr[index++] = bucket[k][l];
  35.                 }
  36.             }
  37.             /**
  38.              * !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  39.              * !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  40.              * !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  41.              * !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  42.              */
  43.             //第l轮处理后，需要将每个bucketElementCounts[k] = 0
  44.             /**
  45.              * !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  46.              * !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  47.              * !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  48.              * !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
  49.              */
  50.             bucketElementCounts[k]= 0;
  51.         }
  53.         System.out.println("第"+(i+1)+"轮排序后的结果是"+ Arrays.toString(arr));
  54.     }
  57. }

}

```