保定网站制作系统,河南省城乡和住房建设厅网站,多用户 wordpress,软件设计师教程简介
之前的文章我们讲了count排序#xff0c;但是count排序有个限制#xff0c;因为count数组是有限的#xff0c;如果数组中的元素范围过大#xff0c;使用count排序是不现实的#xff0c;其时间复杂度会膨胀。
而解决大范围的元素排序的办法就是基数排序。
基数排序…简介
之前的文章我们讲了count排序但是count排序有个限制因为count数组是有限的如果数组中的元素范围过大使用count排序是不现实的其时间复杂度会膨胀。
而解决大范围的元素排序的办法就是基数排序。
基数排序的例子
什么是基数排序呢
考虑一下虽然我们不能直接将所有范围内的数字都使用count数组进行排序但是我们可以考虑按数字的位数来进行n轮count排序每一轮都只对数字的某一位进行排序。
最终仍然可以得到结果并且还可以摆脱count数组大小的限制这就是基数排序。
假如我们现在数组的元素是1221, 15, 20, 3681, 277, 5420, 71, 1522, 4793。
先看动画看下最直观的基数排序的过程 在上面的例子中我们先对个位进行count排序然后对十位进行count排序然后是百位和千位。
最后生成最终的排序结果。
基数排序的java代码实现
因为基数排序实际上是分别按位数的count排序。所以我们可以重用之前写的count排序的代码只是需要进行一些改造。
doCountingSort方法除了传入数组外还需要传入排序的位数digit我们用1101001000来表示。
看一下改造过后的doCountingSort方法 public void doRadixSort(int[] array, int digit){int n array.length;// 存储排序过后的数组int output[] new int[n];// count数组用来存储统计各个元素出现的次数int count[] new int[10];Arrays.fill(count,0);log.info(初始化count值:{},count);// 将原始数组中数据出现次数存入count数组for (int i0; in; i) {count[(array[i]/digit)%10];}log.info(count之后count值:{},count);// 这里是一个小技巧我们根据count中元素出现的次数计算对应元素第一次应该出现在output中的下标。//这里的下标是从右往左数的for (int i1; i10; i) {count[i] count[i - 1];}log.info(整理count对应的output下标:{},count);// 根据count中的下标构建排序后的数组//插入一个之后相应的count下标要减一for (int i n-1; i0; i--){output[count[(array[i]/digit)%10]-1] array[i];count[(array[i]/digit)%10]--;}log.info(构建output之后的output值:{},output);//将排序后的数组写回原数组for (int i 0; in; i)array[i] output[i];}
跟count排序变化不大区别就是这里我们需要使用count[(array[i]/digit)%10]来对每一位进行排序。
另外为了计算出位数digit的值我们还需要拿到数组中最大元素的值
public int getMax(int[] array){int mx array[0];for (int i 1; i array.length; i)if (array[i] mx){mx array[i];}return mx;}
看下怎么调用 public static void main(String[] args) {int[] array {1221, 15, 20, 3681, 277, 5420, 71, 1522, 4793};RadixSort radixSortnew RadixSort();log.info(radixSort之前的数组为:{},array);//拿到数组的最大值用于计算digitint max radixSort.getMax(array);//根据位数遍历进行count排序for (int digit 1; max/digit 0; digit * 10){radixSort.doRadixSort(array,digit);}}
看下输出结果 很好结果都排序了。
基数排序的时间复杂度
从计算过程我们可以看出基数排序的时间复杂度是O(d*(nb)) 其中b是数字的进制数比如上面我们使用的是10进制那么b10。
d是需要循环的轮数也就是数组中最大数的位数。假如数组中最大的数字用K表示那么dlogb(k)。
综上基数排序的时间复杂度是O((nb) * logb(k))。
当k nc其中c是常量时上面的时间复杂度可以近似等于O(nLogb(n))。
考虑下当bn的情况下基数排序的时间复杂度可以近似等于线性时间复杂度O(n)。 原文链接 本文为阿里云原创内容未经允许不得转载。
