怎样才能访问没有备案的网站,上海做网站的公,想要个网站,工具型网站本篇只是讨论桶排序的具体实现#xff0c;想了解更多算法内容可以在我的博客里搜#xff0c;建议大家看看这篇排序算法总结#xff1a;排序算法总结_鱼跃鹰飞的博客-CSDN博客 桶排序的原理#xff1a; 代码#xff1a;sort1是一个比较二逼的实现方式浪费空间#xff0c;s…本篇只是讨论桶排序的具体实现想了解更多算法内容可以在我的博客里搜建议大家看看这篇排序算法总结排序算法总结_鱼跃鹰飞的博客-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, end1);//创建一个Queue数组长度为10作为桶QueueInteger[] 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;//如果是个位的话直接模1010位的话除以digit*10。。。digit*100queues[bucketNum].offer(copy[i]);}//每一次把所有的数放完之后从桶中倒出先进去先倒出来(队列实现)int curIndex 0;for (int i start; i end; i) {//从0到9挨个取出每个桶里的数据依次放入copy数组中//这就是从桶里倒数据的过程for (QueueInteger 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] );}}
}
