本篇只是讨论桶排序的具体实现，想了解更多算法内容可以在我的博客里搜，建议大家看看这篇排序算法总结：排序算法总结_鱼跃鹰飞的博客-CSDN博客
桶排序的原理：
文章来源：https://www.toymoban.com/news/detail-642689.html
代码：sort1是一个比较二逼的实现方式浪费空间，sort2是一个正式的方法 文章来源地址https://www.toymoban.com/news/detail-642689.html
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*100
queues[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();
}
}
}
}
//把排完序的数组复制到原来的数组，如果这个方法是有返回值的，也可以直接返回copy
for(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] + " ");
}
}
}
到了这里，关于不基于比较的排序：基数排序的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
