让咱们先往返顾一下计数排序：
计数排序需要依据原始数列的取值规模，创立一个统计数组，用来统计原始数列中每一一个可能的整数值所呈现的次数。文章源自微观生活（93wg.com）微观生活-https://93wg.com/10605.html
原始数列中的整数值，以及统计数组的下标是逐一对应的，以数列的最小值作为偏移量。比如原始数列的最小值是90， 那么整数95对应的统计数组下标就是 95-90 = 5。文章源自微观生活（93wg.com）微观生活-https://93wg.com/10605.html
那么，桶排序之中所谓的“桶”，又是什么概念呢？文章源自微观生活（93wg.com）微观生活-https://93wg.com/10605.html
每一一个桶（bucket）代表一个区间规模，里面可以承载一个或多个元素。桶排序的第一步，就是创立这些桶，肯定每一一个桶的区间规模：文章源自微观生活（93wg.com）微观生活-https://93wg.com/10605.html
具体树立多少个桶，怎么肯定桶的区间规模，有不少不同的方式。咱们这里创立的桶数量等于原始数列的元素数量，除了了最后一个桶只包括数列最大值，前面各个桶的区间依照比例肯定。文章源自微观生活（93wg.com）微观生活-https://93wg.com/10605.html
区间跨度 = （最大值-最小值）/ （桶的数量 - 1）文章源自微观生活（93wg.com）微观生活-https://93wg.com/10605.html
第二步，遍历原始数列，把元素对号入坐放入各个桶中：文章源自微观生活（93wg.com）微观生活-https://93wg.com/10605.html
第三步，每一个桶内部的元素分别排序（显然，只有第一个桶需要排序）：文章源自微观生活（93wg.com）微观生活-https://93wg.com/10605.html
第四步，遍历所有的桶，输出所有元素：文章源自微观生活（93wg.com）微观生活-https://93wg.com/10605.html
0.5，0.84，2.18，3.25，4.5文章源自微观生活（93wg.com）微观生活-https://93wg.com/10605.html
到此为止，排序收场。
代码中，所有的桶保留在ArrayList聚拢之中，每一一个桶被定义成一个链表（LinkedList<Double>），这样便于在尾部插入元素。
定位元素属于第几个桶，是依照比例来定位：
* / d
同时，代码使用了JDK的聚拢工具类Collections.sort来为桶内部的元素进行排序。Collections.sort底层采取的是归并排序或Timsort，小火伴们可以简单地把它们当成是一种时间繁杂度 O（nlogn）的排序。
假定原始数列有n个元素，分成m个桶（咱们采取的分桶方式 m=n），平均每一个桶的元素个数为n/m。
下面咱们来逐渐分析算法繁杂度：
第一步求数列最大最小值，运算量为n。
第二步创立空桶，运算量为m。
第三步遍历原始数列，运算量为n。
第四步在每一个桶内部做排序，因为使用了O（nlogn）的排序算法，所以运算量为 n/m * log * m。
第五步输出排序数列，运算量为n。
加起来，总的运算量为 3n+m+ n/m * log * m = 3n+m+n 。
去掉系数，时间繁杂度为：
O）
至于空间繁杂度就很显明了：
空桶占用的空间 + 数列在桶中占用的空间 = O（m+n）。
以上就是微观生活（93wg.com）关于“「算法」什么是桶排序”的详细内容，希望对大家有所帮助！
评论