一、基数排序(桶排序)介绍

  1. 基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或 bin sort，顾 名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用
  2. 基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法
  3. 基数排序(Radix Sort)是桶排序的扩展

  4. 基数排序是 1887 年赫尔曼·何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个 位数分别比较。

    二、基数排序基本思想

  5. 将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

  6. 这样说明，比较难理解，下面我们看一个图文解释，理解基数排序的步骤

    三、基数排序图文说明

    将数组 {53, 3, 542, 748, 14, 214} 使用基数排序, 进行升序排序
    排序算法-基数排序 - 图1

    四、基数排序代码实现

    要求：将数组 {53, 3, 542, 748, 14, 214} 使用基数排序, 进行升序排序
    代码实现：
    1.先分步骤分解推理完成

    1. public class RadixSort {
    2.  public static void main(String[] args) {
    3.      int arr[] = { 53, 3, 542, 748, 14,214}
    5.      radixSort(arr);
    7.      System.out.println("基数排序后 " + Arrays.toString(arr));
    8.  }
    9.  //基数排序方法
    10.  public static void radixSort(int[] arr) {
    11.      //定义一个二维数组，表示 10 个桶, 每个桶就是一个一维数组
    12.      //说明
    13.      //1. 二维数组包含 10 个一维数组
    14.      //2. 为了防止在放入数的时候，数据溢出，则每个一维数组(桶)，大小定为 arr.length
    15.      //3. 名明确，基数排序是使用空间换时间的经典算法
    16.      int[][] bucket = new int[10][arr.length];
    17.      //为了记录每个桶中，实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数
    18.      //可以这里理解
    19.      //比如：bucketElementCounts[0] , 记录的就是 bucket[0] 桶的放入数据个数
    20.      int[] bucketElementCounts = new int[10];
    21.      //第 1 轮(针对每个元素的个位进行排序处理)
    22.      for(int j = 0; j < arr.length; j++) {
    23.          //取出每个元素的个位的值
    24.          int digitOfElement = arr[j] / 1 % 10;
    25.          //放入到对应的桶中
    26.          bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
    27.          bucketElementCounts[digitOfElement]++;
    28.      }
    29.      //按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
    30.      int index = 0;
    31.      //遍历每一桶，并将桶中是数据，放入到原数组
    32.      for(int k = 0; k < bucketElementCounts.length; k++) {
    33.          //如果桶中，有数据，我们才放入到原数组
    34.          if(bucketElementCounts[k] != 0) {
    35.              //循环该桶即第 k 个桶(即第 k 个一维数组), 放入
    36.              for(int l = 0; l < bucketElementCounts[k]; l++) {
    37.                  //取出元素放入到 arr
    38.                  arr[index++] = bucket[k][l];
    39.              }
    40.          }
    41.          //第 l 轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
    42.          bucketElementCounts[k] = 0;
    43.      }
    44.      System.out.println("第 1 轮，对个位的排序处理 arr =" + Arrays.toString(arr));
    46.      //==========================================
    47.      //第 2 轮(针对每个元素的十位进行排序处理)
    48.      for (int j = 0; j < arr.length; j++) {
    49.          // 取出每个元素的十位的值
    50.          int digitOfElement = arr[j] / 10 % 10; //748 / 10 => 74 % 10 => 4
    51.          // 放入到对应的桶中
    52.          bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
    53.          bucketElementCounts[digitOfElement]++;
    54.      }
    55.      // 按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
    56.      index = 0;
    57.      // 遍历每一桶，并将桶中是数据，放入到原数组
    58.      for (int k = 0; k < bucketElementCounts.length; k++) {
    59.          // 如果桶中，有数据，我们才放入到原数组
    60.          if (bucketElementCounts[k] != 0) {
    61.              // 循环该桶即第 k 个桶(即第 k 个一维数组), 放入
    62.              for (int l = 0; l < bucketElementCounts[k]; l++) {
    63.                  // 取出元素放入到 arr
    64.                  arr[index++] = bucket[k][l];
    65.              }
    66.          }
    67.          //第 2 轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
    68.          bucketElementCounts[k] = 0;
    69.      }
    70.      System.out.println("第 2 轮，对个位的排序处理 arr =" + Arrays.toString(arr));
    72.      //==========================================
    73.      //第 3 轮(针对每个元素的百位进行排序处理)
    74.      for (int j = 0; j < arr.length; j++) {
    75.          // 取出每个元素的百位的值
    76.          int digitOfElement = arr[j] / 100 % 10; // 748 / 100 => 7 % 10 = 7
    77.          // 放入到对应的桶中
    78.          bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
    79.          bucketElementCounts[digitOfElement]++;
    80.      }
    81.      // 按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
    82.      index = 0;
    83.      // 遍历每一桶，并将桶中是数据，放入到原数组
    84.      for (int k = 0; k < bucketElementCounts.length; k++) {
    85.          // 如果桶中，有数据，我们才放入到原数组
    86.          if (bucketElementCounts[k] != 0) {
    87.              // 循环该桶即第 k 个桶(即第 k 个一维数组), 放入
    88.              for (int l = 0; l < bucketElementCounts[k]; l++) {
    89.                  // 取出元素放入到 arr
    90.                  arr[index++] = bucket[k][l];
    91.              }
    92.          }
    93.          //第 3 轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
    94.          bucketElementCounts[k] = 0;
    95.      }
    96.      System.out.println("第 3 轮，对个位的排序处理 arr =" + Arrays.toString(arr)); 
    97.  }
    98. }

2.根据前面的推导过程，我们可以得到最终的基数排序代码

  1. public class RadixSort {
  2.     public static void main(String[] args) {
  3.         int arr[] = { 53, 3, 542, 748, 14,214}
  5.         radixSort(arr);
  7.         System.out.println("基数排序后 " + Arrays.toString(arr));
  8.     }
  9.     //基数排序方法
  10.     public static void radixSort(int[] arr) {
  11.         //根据前面的推导过程，我们可以得到最终的基数排序代码
  12.         //1. 得到数组中最大的数的位数
  13.         int max = arr[0]; //假设第一数就是最大数
  14.         for(int i = 1; i < arr.length; i++) {
  15.             if (arr[i] > max) {
  16.                 max = arr[i];
  17.             }
  18.         }
  19.         //得到最大数是几位数
  20.         int maxLength = (max + "").length();
  21.         //定义一个二维数组，表示 10 个桶, 每个桶就是一个一维数组
  22.         //说明
  23.         //1. 二维数组包含 10 个一维数组
  24.         //2. 为了防止在放入数的时候，数据溢出，则每个一维数组(桶)，大小定为 arr.length
  25.         //3. 名明确，基数排序是使用空间换时间的经典算法
  26.         int[][] bucket = new int[10][arr.length];
  27.         //为了记录每个桶中，实际存放了多少个数据,
  28.         //我们定义一个一维数组来记录各个桶的每次放入的数据个数
  29.         //可以这里理解
  30.         //比如：bucketElementCounts[0] , 记录的就是 bucket[0] 桶的放入数据个数
  31.         int[] bucketElementCounts = new int[10];
  32.         //这里我们使用循环将代码处理
  33.         for(int i = 0 , n = 1; i < maxLength; i++, n *= 10) {
  34.             //(针对每个元素的对应位进行排序处理)， 第一次是个位，第二次是十位，第三次是百位.. 
  35.             for(int j = 0; j < arr.length; j++) {
  36.                 //取出每个元素的对应位的值
  37.                 int digitOfElement = arr[j] / n % 10;
  38.                 //放入到对应的桶中
  39.                 bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
  40.                 bucketElementCounts[digitOfElement]++;
  41.             }
  42.             //按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
  43.             int index = 0;
  44.             //遍历每一桶，并将桶中是数据，放入到原数组
  45.             for(int k = 0; k < bucketElementCounts.length; k++) {
  46.                 //如果桶中，有数据，我们才放入到原数组
  47.                 if(bucketElementCounts[k] != 0) {
  48.                     //循环该桶即第 k 个桶(即第 k 个一维数组), 放入
  49.                     for(int l = 0; l < bucketElementCounts[k]; l++) {
  50.                         //取出元素放入到 arr
  51.                         arr[index++] = bucket[k][l];
  52.                     }
  53.                 }
  54.                 //第 i+1 轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
  55.                 bucketElementCounts[k] = 0;
  56.             }
  57.             //System.out.println("第"+(i+1)+"轮，对个位的排序处理 arr =" + Arrays.toString(arr));
  58.         }
  59.     }
  60. }