1.动图展示

基数.gif

2.思路分析

基数排序第i趟将待排数组里的每个数的i位数放到tempj（j=1-10）队列中，然后再从这十个队列中取出数据，重新放到原数组里，直到i大于待排数的最大位数。
1.数组里的数最大位数是n位，就需要排n趟，例如数组里最大的数是3位数，则需要排3趟。
2.若数组里共有m个数，则需要十个长度为m的数组tempj（j=0-9）用来暂存i位上数为j的数，例如，第1趟，各位数为0的会被分配到temp0数组里，各位数为1的会被分配到temp1数组里……
3.分配结束后，再依次从tempj数组中取出数据，遵循先进先进原则，例如对数组{1，11，2，44，4}，进行第1趟分配后，temp1={1,11}，temp2={2}，temp4={44，4}，依次取出元素后{1，11，2，44，4}，第一趟结束
4.循环到n趟后结束，排序完成
通过基数排序对数组{53, 3, 542, 748, 14, 214, 154, 63, 616}：
7.基数排序 - 图2

3.复杂度分析（空间换时间）


每一次关键字的桶分配都需要O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。
假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2n) ，当然d要远远小于n，因此基本上还是线性级别的。
系数2可以省略，且无论数组是否有序，都需要从个位排到最大位数，所以时间复杂度始终为O(dn) 。其中，n是数组长度，d是最大位数。
2. 空间复杂度：
基数排序的空间复杂度为O(n+k)*，其中k为桶的数量，需要分配n个数。

4.代码实现（不含负数）

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

推导过程

  1. //第1轮(针对每个元素的个位进行排序处理)
  2.         for(int j = 0; j < arr.length; j++) {
  3.             //取出每个元素的个位的值
  4.             int digitOfElement = arr[j] / 1 % 10;
  5.             //放入到对应的桶中
  6.             bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
  7.             bucketElementCounts[digitOfElement]++;
  8.         }
  9.         //按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
  10.         int index = 0;
  11.         //遍历每一桶，并将桶中是数据，放入到原数组
  12.         for(int k = 0; k < bucketElementCounts.length; k++) {
  13.             //如果桶中，有数据，我们才放入到原数组
  14.             if(bucketElementCounts[k] != 0) {
  15.                 //循环该桶即第k个桶(即第k个一维数组), 放入
  16.                 for(int l = 0; l < bucketElementCounts[k]; l++) {
  17.                     //取出元素放入到arr
  18.                     arr[index++] = bucket[k][l];
  19.                 }
  20.             }
  21.             //第l轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
  22.             bucketElementCounts[k] = 0;
  24.         }
  25.         System.out.println("第1轮，对个位的排序处理 arr =" + Arrays.toString(arr));
  28.         //==========================================
  30.         //第2轮(针对每个元素的十位进行排序处理)
  31.         for (int j = 0; j < arr.length; j++) {
  32.             // 取出每个元素的十位的值
  33.             int digitOfElement = arr[j] / 10  % 10; //748 / 10 => 74 % 10 => 4
  34.             // 放入到对应的桶中
  35.             bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
  36.             bucketElementCounts[digitOfElement]++;
  37.         }
  38.         // 按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
  39.         index = 0;
  40.         // 遍历每一桶，并将桶中是数据，放入到原数组
  41.         for (int k = 0; k < bucketElementCounts.length; k++) {
  42.             // 如果桶中，有数据，我们才放入到原数组
  43.             if (bucketElementCounts[k] != 0) {
  44.                 // 循环该桶即第k个桶(即第k个一维数组), 放入
  45.                 for (int l = 0; l < bucketElementCounts[k]; l++) {
  46.                     // 取出元素放入到arr
  47.                     arr[index++] = bucket[k][l];
  48.                 }
  49.             }
  50.             //第2轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
  51.             bucketElementCounts[k] = 0;
  52.         }
  53.         System.out.println("第2轮，对个位的排序处理 arr =" + Arrays.toString(arr));
  56.         //第3轮(针对每个元素的百位进行排序处理)
  57.         for (int j = 0; j < arr.length; j++) {
  58.             // 取出每个元素的百位的值
  59.             int digitOfElement = arr[j] / 100 % 10; // 748 / 100 => 7 % 10 = 7
  60.             // 放入到对应的桶中
  61.             bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
  62.             bucketElementCounts[digitOfElement]++;
  63.         }
  64.         // 按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
  65.         index = 0;
  66.         // 遍历每一桶，并将桶中是数据，放入到原数组
  67.         for (int k = 0; k < bucketElementCounts.length; k++) {
  68.             // 如果桶中，有数据，我们才放入到原数组
  69.             if (bucketElementCounts[k] != 0) {
  70.                 // 循环该桶即第k个桶(即第k个一维数组), 放入
  71.                 for (int l = 0; l < bucketElementCounts[k]; l++) {
  72.                     // 取出元素放入到arr
  73.                     arr[index] = bucket[k][l];
  74.                     index++；
  75.                 }
  76.             }
  77.             //第3轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
  78.             bucketElementCounts[k] = 0;
  79.         }
  80.         System.out.println("第3轮，对个位的排序处理 arr =" + Arrays.toString(arr)); */

运行结果

  1. 基数排序前 [53, 3, 542, 748, 14, 214]
  2. 基数排序后 [3, 14, 53, 214, 542, 748]

5.代码实现（含负数）

含负数，则每个数都加上最小负数的绝对值+1，把所有数变为正数，排序后，再减掉添加的部分即可。

  1.  public static void RadixSort2(int[] arr) {
  2.         //遍历找到最大的数值
  3.         int max = arr[0];
  4.         int min =0;
  5.         for (int i = 1; i < arr.length; i++) {
  6.             if (max < arr[i]) {
  7.                 max = arr[i];
  8.             }if (arr[i] < min){//找出比0小的最小的负数
  9.                 min =arr[i];
  10.             }
  11.         }
  12.      //存在负数，让该负数变成非零整数，其他数以及最大值也加上相应的数值，再进行排序
  13.      排序完再减掉该数值
  14.         if(min<0) {
  15.             for(int mi = 0;mi<arr.length;mi++) {
  16.                 arr[mi] -= min;//将所有数都加上最小负数的绝对值，以保证所有数均为非负整数
  17.                 max -= min;//同时将最大也加上该值，若没有这一步，
  18.                             则下面求数组的最大值的位数还是原先数组的最大值的位数
  19.             }
  20.         }
  22.         //求该最大值的长度，即位数
  23.         int maxLength = (max + "").length();
  25.         //定义二维数组，代表10桶，每个桶里面存放一位数组
  26.         int[][] bucket = new int[10][arr.length];//避免越界
  28.         //定义数组，存放每个桶含有的数字个数
  29.         int[] counts = new int[10];
  31.         for (int t = 0, n = 1; t < maxLength; t++, n = n * 10) {
  32.             for (int j = 0; j < arr.length; j++) {
  33.                 int num = arr[j] / n % 10;//一开始个位数
  34.                 bucket[num][counts[num]] = arr[j]; //将遍历的每个数字按个位数 存放到对应的桶里，然后桶里的数值+1
  35.                 counts[num]++;
  36.             }
  38.             //遍历每个桶，并将桶的数据放回原数组
  39.             int index = 0;
  40.             for (int k = 0; k < counts.length; k++) {
  41.                 if (counts[k] != 0) {
  42.                     //循环该桶
  43.                     for (int i = 0; i < counts[k]; i++) {
  44.                         arr[index] = bucket[k][i];
  45.                         index++;
  46.                     }
  47.                 }
  48.                 //将桶里的数放回数组。还需要将原先的桶里的数据清空
  49.                 counts[k] = 0;
  50.             }
  51.         }
  52.      //排完序后，将所有数减去一开始增加的部分
  53.         if(min<0) {
  54.             for(int mi = 0;mi<arr.length;mi++) {
  55.                 arr[mi] += min;//排完序后，再将数缩小回来
  56.             }
  57.         }
  58.     }

运行结果

  1. 原数组:[11, -1, 3, 5, 6, 2, -100, 0]
  2. ---基数排序----
  3. [-100, -1, 0, 2, 3, 5, 6, 11]