思路
- 设置固定空桶数
- 将数据放到对应的空桶中
- 将每个不为空的桶进行排序
- 拼接不为空的桶中的数据,得到结果
步骤演示
假设一组数据(长度为 20)为
1 | [63,157,189,51,101,47,141,121,157,156,194,117,98,139,67,133,181,13,28,109] |
现在需要按 5 个分桶,进行桶排序,实现步骤如下:
- 找到数组中的最大值 194 和最小值 13,然后根据桶数为 5,计算出每个桶中的数据范围为
(194-13+1)/5=36.4
; - 遍历原始数据,以第一个数据 63 为例,先找到该数据对应的桶序列(
Math.floor(63 - 13) / 36.4) =1
),然后将该数据放入序列为 1 的桶中(从 0 开始算); - 当向同一个桶中第二次插入数据时,判断桶中已存在的数字与新插入的数字的大小,按从左到右,从小打大的顺序插入。如第一个桶已经有了 63,再插入 51,67 后,桶中的排序为 (51,63,67) ,一般通过链表来存放桶中数据。
- 全部数据装桶完毕后,按序列,从小到大合并所有非空的桶(0,1,2,3,4 桶)
- 合并完之后就是排序好的数据了
步骤图示:
动画:
实现
1 | public static void main(String[] args) { |
时间复杂度
桶排序最好情况下使用线性时间 O (n)。事实上,桶排序算法的总时间复杂度,取决与对各个桶之间数据进行排序的时间复杂度,因为其它部分的时间复杂度都为 O (n)。
很显然,桶划分的越多,各个桶中的数据越少,排序所用的时间也会越少。但相应的空间消耗就会增大。在额外空间充足的情况下,尽量增大桶的数量,极限情况下每个桶只有一个数据时,或者是每只桶只装一个值时,完全避开了桶内排序的操作,桶排序的最好时间复杂度就能够达到 O (n)。
比如高考总分 750 分,全国几百万人,我们只需要创建 751 个桶,循环一遍挨个扔进去,排序速度是毫秒级。
但是如果数据经过桶的划分之后,桶与桶的数据分布极不均匀,有些数据非常多,有些数据非常少,比如 [8,2,9,10,1,23,53,22,12,9000] 这十个数据,我们分成十个桶装,结果发现第一个桶装了 9 个数据,这是非常影响效率的情况,会使时间复杂度下降到 O(nlog2n),解决办法是我们每次桶内排序时判断一下数据量,如果桶里的数据量过大,那么应该在桶里面回调自身再进行一次桶排序。
空间复杂度
稳定性
稳定性是指,比如 a 在 b 前面,a=b,排序后,a 仍然应该在 b 前面,这样就算稳定的。
桶排序中,假如升序排列,a 已经在桶中,b 插进来是永远都会 a 右边的(因为一般是从右到左,如果不小于当前元素,则插入改元素的右侧),所以桶排序是稳定的。
当然了,如果采用元素插入后再分别进行桶内排序,并且桶内排序算法采用快速排序,那么就不是稳定的。
适用范围
用排序主要适用于均匀分布的数字数组,在这种情况下能够达到最大效率。
Reference
- 排序算法之桶排序的深入理解以及性能分析 - https://dailc.github.io/2016/12/03/baseKnowlenge_algorithm_sort_bucketSort.html
- https://www.geeksforgeeks.org/bucket-sort-2/
- Bucket Sort Program in Java - https://netjs.blogspot.com/2019/01/bucket-sort-program-in-java.html
- 这或许是东半球讲十大排序算法最好的一篇文章 - https://cxyxiaowu.com/articles/2019/06/11/1560233679033.html