【数据结构与算法】非比较排序（计数排序、桶排序、基数排序） (2)

思路：是一种特殊的桶排序
初始化0-9号十个桶，
按个位数字，将关键字入桶，入完后，依次遍历10个桶，按检出顺序回填到数组中，如
321 322 331 500 423 476 926
0：500
1：321 331
2：322
3：423
4：无
5：无
6：476 926
检出后数组序列为： 500 321 331 423 476 926，然后取十位数字重复过程一，得到
0：500
1：无
2：321 423 926
3：331
4：无
5：无
7：476
检出后数组序列为： 500 321 423 926 331 476，然后取百位数字重复过程一，得到
0：无
1：无
2：无
3：321 331
4：423 476
5：500
9：926
检出后数组序列为： 321 331 423 476 500 926，已然有序
但是我们应该继续入桶，不过因为再高位全部是0了，这些元素会按顺序全部进入0号桶，这时0号桶的size==数组的size，这时结束标志
最后再回填到数组，数组就是升序排列的了

代码实现 法一：ArrayList实现二维数组（形象表示桶） public static void main(String[] args) { int[] arr = {2, 6, 3, 2, 5, 32, 42, 2, 5, 4, 7, 9, 3}; radixSort(arr, 0, arr.length - 1); for (int i : arr) { System.out.print(i + " "); } } // 10个桶，每个桶装的数个数不定，适合用数组加ArrayList private static ArrayList[] bucket = new ArrayList[10]; // 初始化桶 static { for (int i = 0; i < bucket.length; i++) { bucket[i] = new ArrayList(); } } public static void radixSort(int[] arr, int begin, int end) { int d = 1; //入桶依据的位初始化为1 int dNum = maxbits(arr, begin, end); //获取最大数字的位数 while (d <= dNum) { //做dNum次入桶出桶操作 radixSort(arr, begin, end, d++); //依据第二个参数d入桶和出桶 } } private static void radixSort(int[] arr, int begin, int end, int d) { //全部入桶 for (int i = begin; i <= end; i++) { putInBucket(arr[i], getDigitOn(arr[i], d)); //把每个数字的第d位入桶 } //每个桶中的元素依次压入原数组 int k = 0; //k是原数组下标 for (int j = 0; j < bucket.length; j++) {// 每个桶 for (Object m : bucket[j]) { arr[k++] = (Integer) m; } } clearAll(); // 记得清空桶 } private static int getDigitOn(int num, int d) { //获取num的第d位的数字 return ((num / ((int) Math.pow(10, d - 1))) % 10); } private static void putInBucket(int data, int digitOn) { //入桶 bucket[digitOn].add(data); } private static void clearAll() { //对每个桶调用clear方法进行清空 for (ArrayList b : bucket) { b.clear(); } } private static int maxbits(int[] arr, int begin, int end) { //获取数组中的最大元素的位数 int max = Integer.MIN_VALUE; for (int i = begin; i <= end; i++) { max = Math.max(max, arr[i]); } int dNum = 0; while (max != 0) { //获取最大值的位数 dNum++; max /= 10; } return dNum; } 法二：前缀和数组模拟

首先按照数组元素的个位数组将其入桶

其次构造前缀和数组

逆向遍历原数组，根据个位数字找到其在目标有序数组中的位置

循环最大数的位数次，模拟了入桶出桶过程

public static void radixSort(int[] arr) { if (arr == null || arr.length < 2) { return; } radixSort(arr, 0, arr.length - 1, maxbits(arr)); } public static int maxbits(int[] arr) { int max = Integer.MIN_VALUE; for (int i = 0; i < arr.length; i++) { max = Math.max(max, arr[i]); } int res = 0; while (max != 0) { res++; max /= 10; } return res; } public static void radixSort(int[] arr, int begin, int end, int digit) { final int radix = 10; int i = 0, j = 0; int[] bucket = new int[end - begin + 1]; for (int d = 1; d <= digit; d++) { int[] count = new int[radix]; for (i = begin; i <= end; i++) { j = getDigit(arr[i], d); count[j]++; } for (i = 1; i < radix; i++) { //获得前缀和数组 count[i] = count[i] + count[i - 1]; } for (i = end; i >= begin; i--) { //倒叙遍历原数组 j = getDigit(arr[i], d); bucket[count[j] - 1] = arr[i]; count[j]--; } for (i = begin, j = 0; i <= end; i++, j++) { //辅助数组拷贝回原数组 arr[i] = bucket[j]; } } } public static int getDigit(int x, int d) { //获取数字x的第d位数字 return ((x / ((int) Math.pow(10, d - 1))) % 10); }