江苏龙网

  1. 首页 > 人文 > >

1T数据快速排序！十种经典排序算法总结( 六 )

< min) {min = i;}}//计算桶的数量（可以自定义实现）int bucketNumber = (max - min) / array.length + 1;List[] buckets = new ArrayList[bucketNumber];//计算每个桶存数的范围（可以自定义实现或者不用实现）int bucketRange = (max - min + 1) / bucketNumber;for (int value : array) {//计算应该放到哪个桶中（可以自定义实现）int bucketIndex = (value - min) / (bucketRange + 1);//延迟初始化if (buckets[bucketIndex] == null) {buckets[bucketIndex] = new ArrayList<>();}//放入指定的桶buckets[bucketIndex].add(value);}int index = 0;for (List bucket : buckets) {//对每个桶进行内部排序 ， 我这里使用的是快速排序 ， 也可以使用别的排序算法 ， 当然也可以继续递归去做桶排序quickSort(bucket);if (bucket == null) {continue;}//将不为null的桶中的数据按顺序写回到array数组中for (Integer integer : bucket) {array[index++] = integer;}}return array;}10 基数排序基数排序不是根据一个数的整体来进行排序的 ， 而是将数的每一位上的数字进行排序 。 比如说第一轮排序 ， 我拿到待排序数组中所有数个位上的数字来进行排序；第二轮排序我拿到待排序数组中所有数十位上的数字来进行排序；第三轮排序我拿到待排序数组中所有数百位上的数字来进行排序...以此类推 。 每一轮的排序都会累加上一轮所有前几位上排序的结果 ， 最终的结果就会是一个有序的数列 。
基数排序一般是对所有非负整数进行排序的 ， 但是也可以有别的手段来去掉这种限制（比如都加一个固定的数或者都乘一个固定的数 ， 排完序后再恢复等等） 。 基数排序和桶排序很像 ， 桶排序是按数值的区间进行划分 ， 而基数排序是按数的位数进行划分 。 同时这两个排序都是需要依靠其他排序算法来实现的（如果不算递归调用桶排序本身的话） 。 基数排序每一轮的内部排序会使用到计数排序来实现 ， 因为每一位上的数字无非就是0-9 ， 是一个小范围的数 ， 所以使用计数排序很合适 。
基数排序执行示意图：
1T数据快速排序！十种经典排序算法总结文章插图
具体的实现代码如下：
public int[] radixSort(int[] array) {if (array == null || array.length < 2) {return array;}//记录待排序数组中的最大值int max = array[0];for (int i : array) {if (i > max) {max = i;}}//获取最大值的位数int maxDigits = 0;while (max != 0) {max /= 10;maxDigits++;}//用来计数排序的临时数组int[] temp = new int[10];//用来存放每轮排序后的结果int[] sortedArray = new int[array.length];for (int d = 1; d <= maxDigits; d++) {//每次循环开始前都要清空temp数组中的值replaceArray(temp, null);//记录每个数出现的次数for (int a : array) {temp[getNumberFromDigit(a, d)]++;}//将temp数组进行转换 ， 记录每个数在最后排好序的数组中应该要存放的位置+1（如果有重复的就记录最后一个）for (int j = 1; j < temp.length; j++) {temp[j] += temp[j - 1];}//这里必须是从后往前遍历 ， 以此来保证稳定性for (int i = array.length - 1; i >= 0; i--) {int index = getNumberFromDigit(array[i], d);sortedArray[temp[index] - 1] = array[i];temp[index]--;}//一轮计数排序过后 ， 将这次排好序的结果赋值给原数组replaceArray(array, sortedArray);}return array;}private final static int[] sizeTable = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};/** * 获取指定位数上的数字是多少 */private int getNumberFromDigit(int number, int digit) {if (digit < 0) {return -1;}return (number / sizeTable[digit - 1]) % 10;}private void replaceArray(int[] originalArray, int[] replaceArray) {if (replaceArray == null) {for (int i = 0; i


推荐阅读


上一篇：用了5年才知道，微信转账和红包差别不小，建议与转告家里亲友

下一篇：Win10新预览版20236推送：刷新率调节更方便、可保留搜索历史