不基于比较的排序：基数排序

本篇只是讨论桶排序的具体实现，想了解更多算法内容可以在我的博客里搜，建议大家看看这篇排序算法总结：排序算法总结_鱼跃鹰飞的博客-CSDN博客

 桶排序的原理：

代码：sort1是一个比较二逼的实现方式浪费空间，sort2是一个正式的方法 

package sort;import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;public class RadixSort {public static void radixSort(int[] arr) {int maxBit = getMaxBit(arr);sort2(arr, 0, arr.length - 1, maxBit);}/*** 具体的基数排序过程* @param arr 排序原始数组* @param start 要排序范围开始下标* @param end 要排序范围结束下标* @param maxBit*/public static void sort(int[] arr, int start, int end, int maxBit) {final int bucketSize = 10;//先copy一份数据，注意这里的第三个参数要+1，因为是左闭右开int[] copy = Arrays.copyOfRange(arr, start, end+1);//创建一个Queue数组，长度为10作为桶Queue<Integer>[] queues = new LinkedList[bucketSize];for(int i = 0; i < bucketSize; i++) {queues[i] = new LinkedList();}for(int digit = 0; digit < maxBit; digit ++) {for(int i = start; i <= end; i ++) {int bucketNum = digit == 0? copy[i]%10 : (copy[i]/(digit*10))%10;//如果是个位的话，直接模10，10位的话，除以digit*10。。。digit*100queues[bucketNum].offer(copy[i]);}//每一次把所有的数放完之后，从桶中倒出，先进去先倒出来(队列实现)int curIndex = 0;for (int i = start; i <= end; i++) {//从0到9挨个取出每个桶里的数据，依次放入copy数组中//这就是从桶里倒数据的过程for (Queue<Integer> queue : queues) {while (!queue.isEmpty()) {copy[curIndex ++]  = queue.poll();}}}}//把排完序的数组复制到原来的数组，如果这个方法是有返回值的，也可以直接返回copyfor(int i = 0; i < copy.length;i++) {arr[i] = copy[i];}}/*** 基数排序的省空间的解法* @param arr 原始数组* @param start 开始下标* @param end 结束下标* @param maxDigit*/public static void sort2(int[] arr, int start, int end, int maxDigit) {final int radixCount = 10;//创建一个辅助数组用于中间过程的转换，长度为区间长度int[] help = new int[end - start + 1];//如果最高位是maxDigit，那从0到maxDigit-1依次进行每一轮的入桶和出桶过程for(int digit = 0; digit < maxDigit; digit ++) {//统计数组，作为桶使用int[] countArr = new int[radixCount];//每一轮的入桶操作，countArr[i]代表当前位是i的有多少个数for(int i = start; i <= end; i++) {int digitNum = getDigitNum(arr[i], digit);countArr[digitNum] ++;}//把countArr改造为前缀和//这个循环结束了countArr[i]代表当前位小于等于i的有多少个(i这个数最后的下标是countArr[i]-1)for(int i = 0; i < countArr.length; i++) {countArr[i] = i == 0? countArr[i] : countArr[i] + countArr[i-1];}//根据前缀和数组计算当前数字要放的位置for(int i = help.length - 1; i >= 0; i --) {//取当前位的数int digitNum = getDigitNum(arr[i], digit);//辅助数组中的countArr[i]代表当前位小于等于i的有多少个，那等于i的最后一个数应该放置在countArr[i]-1位置//放完之后等于i的最后没有放元素的还有countArr[i]-1个help[--countArr[digitNum]] = arr[i];}//每一轮拷贝回原数组，方便下次循环用for(int i = start; i < end;i++) {arr[i] = help[i];}}}public static int getDigitNum(int num, int digit) {if(digit == 0) return num % 10;if(num < Math.pow(10, digit)) {return 0;}int digitNum = num;while(digit > 0) {digitNum = (digitNum / 10);digit --;}return digitNum%10;}public static int getMaxBit(int[] arr) {int maxBit = 0;for(int i = 0; i < arr.length; i++) {int curBit = 0;int val = arr[i];while(val != 0) {curBit ++;val = val/10;}maxBit = Math.max(maxBit, curBit);}return maxBit;}//判断两个数组每个位置的数是否相等public static boolean isEqualsArray(int[] arr1, int[] arr2) {if((arr1 == null && arr2 == null) || (arr1 == arr2)) return true;if(arr1 == null || arr2 == null || arr1.length != arr2.length)  return false;for(int i = 0; i < arr1.length; i++) {if(arr1[i] != arr2[i]) {return false;}}return true;}public static void main(String[] args) {int[] arr = {103, 9, 13, 17, 25, 27};int[] arr2 = {103, 9, 13, 17, 25, 27};int maxBit = getMaxBit(arr);System.out.println(maxBit);boolean isEquals = isEqualsArray(arr, arr2);System.out.println(isEquals);radixSort(arr);printArr(arr);/*int digitNum = getDigitNum(3020,1);System.out.println(digitNum);*/}public static void printArr(int[] arr) {for(int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}
}