四川建设安全协会网站,网站设计规划范文,杭州程序员培训班,石家庄网站建设德信互联科技有限公司转载自 漫画#xff1a;什么是桶排序
计数排序需要根据原始数列的取值范围#xff0c;创建一个统计数组#xff0c;用来统计原始数列中每一个可能的整数值所出现的次数。
原始数列中的整数值#xff0c;和统计数组的下标是一一对应的#xff0c;以数列的最小值作为偏移…转载自 漫画什么是桶排序
计数排序需要根据原始数列的取值范围创建一个统计数组用来统计原始数列中每一个可能的整数值所出现的次数。
原始数列中的整数值和统计数组的下标是一一对应的以数列的最小值作为偏移量。比如原始数列的最小值是90 那么整数95对应的统计数组下标就是 95-90 5。 那么桶排序当中所谓的“桶”又是什么概念呢
每一个桶bucket代表一个区间范围里面可以承载一个或多个元素。桶排序的第一步就是创建这些桶确定每一个桶的区间范围 具体建立多少个桶如何确定桶的区间范围有很多不同的方式。我们这里创建的桶数量等于原始数列的元素数量除了最后一个桶只包含数列最大值前面各个桶的区间按照比例确定。
区间跨度 最大值-最小值/ 桶的数量 - 1
第二步遍历原始数列把元素对号入座放入各个桶中 第三步每个桶内部的元素分别排序显然只有第一个桶需要排序 第四步遍历所有的桶输出所有元素
0.50.842.183.254.5
到此为止排序结束。 public static double[] bucketSort(double[] array){//1.得到数列的最大值和最小值并算出差值ddouble max array[0];double min array[0];for(int i1; iarray.length; i) {if(array[i] max) {max array[i];}if(array[i] min) {min array[i];}}double d max - min;//2.初始化桶int bucketNum array.length;ArrayListLinkedListDouble bucketList new ArrayListLinkedListDouble(bucketNum);for(int i 0; i bucketNum; i){bucketList.add(new LinkedListDouble());}//3.遍历原始数组将每个元素放入桶中for(int i 0; i array.length; i){int num (int)((array[i] - min) * (bucketNum-1) / d);bucketList.get(num).add(array[i]);}//4.对每个通内部进行排序for(int i 0; i bucketList.size(); i){//JDK底层采用了归并排序或归并的优化版本Collections.sort(bucketList.get(i));}//5.输出全部元素double[] sortedArray new double[array.length];int index 0;for(LinkedListDouble list : bucketList){for(double element : list){sortedArray[index] element;index;}}return sortedArray;}public static void main(String[] args) {double[] array new double[] {4.12,6.421,0.0023,3.0,2.123,8.122,4.12, 10.09};double[] sortedArray bucketSort(array);System.out.println(Arrays.toString(sortedArray));}
代码中所有的桶保存在ArrayList集合当中每一个桶被定义成一个链表LinkedListDouble这样便于在尾部插入元素。
定位元素属于第几个桶是按照比例来定位
(array[i] - min) * (bucketNum-1) / d
同时代码使用了JDK的集合工具类Collections.sort来为桶内部的元素进行排序。Collections.sort底层采用的是归并排序或Timsort小伙伴们可以简单地把它们当做是一种时间复杂度 Onlogn的排序。 假设原始数列有n个元素分成m个桶我们采用的分桶方式 mn平均每个桶的元素个数为n/m。
下面我们来逐步分析算法复杂度
第一步求数列最大最小值运算量为n。
第二步创建空桶运算量为m。
第三步遍历原始数列运算量为n。
第四步在每个桶内部做排序由于使用了Onlogn的排序算法所以运算量为 n/m * log(n/m ) * m。
第五步输出排序数列运算量为n。 加起来总的运算量为 3nm n/m * log(n/m ) * m 3nmn(logn-logm) 。
去掉系数时间复杂度为
O(nmn(logn-logm)
至于空间复杂度就很明显了
空桶占用的空间 数列在桶中占用的空间 Omn。
