20 -- 排序算法之基数排序

 举例说明：

1、第一轮：按照每个元素的 个 位取出，然后将这个数放在对应的桶（数组）中；在按照这个桶的顺序，放入原来的数组中 -->

 2、第二轮：按照每个元素的 十 位取出， -->

  3、第三轮：按照每个元素的 百 位取出， -->

 总结：从中可以看到 --> 排序的次数 等于 待排序中的最大位数的个数

 代码实现：

  1 import java.util.Arrays;
  2 
  3 //基数排序(桶排序)
  4 public class RadixSort {
  5 
  6     public static void main(String[] args) {
  7         int[] arr = {53,3,542,748,14,214};
  8         radixSort2(arr);
  9     }
 10     
 11     public static void radixSort(int[] arr) {
 12         System.out.println("第一轮：针对每个元素的个位数进行排序");
 13         //第一轮：针对每个元素的个位数进行排序
 14         //定义10个桶(基数为0~9),为了防止极端情况(基数全部一样)，每个桶的大小与数组中元素的个数一样【空间换时间】
 15         int[][] bucket = new int[10][arr.length];
 16         
 17         //记录每个桶中的位数
 18         int[] countOfBucket = new int[10];
 19         //放置
 20         int digitOfEmement = 0;
 21         for(int j = 0; j < arr.length; j ++) {
 22             digitOfEmement = arr[j] % 10;
 23             bucket[digitOfEmement][countOfBucket[digitOfEmement]] = arr[j];
 24             countOfBucket[digitOfEmement] ++;
 25         }
 26         
 27         //依次取出每个桶中的数据放入到数组中
 28         int index = 0;
 29         for(int i = 0; i < bucket.length; i++) {
 30             for(int j = 0; j < countOfBucket[i]; j++) {
 31                 arr[index] = bucket[i][j];
 32                 index ++;
 33             }
 34             //清空记录每个桶装的数据的个数，用于下次使用
 35             countOfBucket[i] = 0;
 36         }
 37         System.out.println(Arrays.toString(arr));
 38     
 39         System.out.println("第二轮：针对每个元素的十位数进行排序");
 40         for(int j = 0; j < arr.length; j++) {
 41             digitOfEmement = arr[j] / 10 % 10;
 42             bucket[digitOfEmement][countOfBucket[digitOfEmement]] = arr[j];
 43             countOfBucket[digitOfEmement] ++;
 44         }
 45         
 46         index = 0;
 47         for(int i = 0; i < bucket.length; i++) {
 48             for(int j = 0; j < countOfBucket[i]; j++) {
 49                 arr[index] = bucket[i][j];
 50                 index ++;
 51             }
 52             countOfBucket[i] = 0;
 53         }
 54         System.out.println(Arrays.toString(arr));
 55         
 56         
 57         System.out.println("第三轮：针对每个元素的百位数进行排序");
 58         for(int j = 0; j < arr.length; j++) {
 59             digitOfEmement = arr[j] / 100 % 10;
 60             bucket[digitOfEmement][countOfBucket[digitOfEmement]] = arr[j];
 61             countOfBucket[digitOfEmement] ++;
 62         }
 63         
 64         index = 0;
 65         for(int i = 0; i < bucket.length; i++) {
 66             for(int j = 0; j < countOfBucket[i]; j++) {
 67                 arr[index] = bucket[i][j];
 68                 index ++;
 69             }
 70             countOfBucket[i] = 0;
 71         }
 72         System.out.println(Arrays.toString(arr));
 73         
 74      }
 75 
 76     
 77     //总结出规律得出
 78     public static void radixSort2(int[] arr) {
 79         //定义十个桶，每个桶的大小为数组的长度
 80         int[][] bucket = new int[10][arr.length];
 81         
 82         //一维数组：记录每个桶中中放置的数据的个数
 83         int[] countOfBucket = new int[10];
 84         int max = arr[0]; //假设第一个数为数组中最大位数个数
 85         for(int i = 1; i < arr.length; i++) {
 86             if (arr[i] > max) {
 87                 max = arr[i];
 88             }
 89         }
 90         
 91         int maxLength = (max + "").length();
 92         
 93         int digitOfElemnt = 0;
 94         int index = 0;
 95         //i：根据最大位数循环
 96         //radix : 每次以...为基准【个、十、百、千 ...】
 97         for(int i = 0, radix = 1; i < maxLength; i++, radix *= 10) {
 98             for(int j = 0; j < arr.length; j++) {
 99                 //取出基准数
100                 digitOfElemnt = arr[j] / radix % 10; 
101                 //根据基准数入桶
102                 bucket[digitOfElemnt][countOfBucket[digitOfElemnt]] = arr[j];
103                 countOfBucket[digitOfElemnt] ++;
104             }
105             
106             index = 0;
107             //从0~9遍历桶，依次取出各个元素重新装入原数组中
108             for(int k = 0; k < bucket.length; k ++) {
109                 for(int l = 0; l < countOfBucket[k]; l ++) {
110                     arr[index] = bucket[k][l];
111                     index ++;
112                 }
113                 countOfBucket[k] = 0;
114             }
115             System.out.println("第" + (i+1) + "次：" + Arrays.toString(arr));
116         }
117         
118     }
119     
120 }

运行结果：

 总结【注意】：

从基数排序（桶排序）的示意图和代码实现部分可以看出，基数排序是典型的用空间换取时间的例子，并且它不适合做负数的排序。