桶排序

当计算集合中的n个元素时,如果能够构建一个小得多的k个值的集合,那么这个时候就可以使用计数排序。给定n个元素的集合,桶排序构造了n个桶来切分输入集合,因此桶排序能够降低处理时其在额外空间的开销。如果一个散列函数,hash(Ai),用来均匀地将n个元素分配到n个桶中,那么如图4-18所示的桶排序在最坏情况下也能够以O(n)的时间进行排序。如果希望使用桶排序,那么需要满足以下两点。

阅读 ‧ 电子书库
图 4-18 桶排序详细介绍

均匀分布

输入数据需要均匀分布在一个给定的范围内。基于这种分配,算法创建了n个桶来平分输入数据。

广告:个人专属 VPN,独立 IP,无限流量,多机房切换,还可以屏蔽广告和恶意软件,每月最低仅 5 美元

有序散列函数

桶必须是有序的。也就是说,如果i<j,桶bi中的元素要字典序小于桶bj中的元素。

桶排序不适合排序随机字符串,但是,它能够被用来排序在区间[0,1)间均匀分配的浮点数。

一旦所有待排序的元素都被放入桶中,桶排序从左至右对每个桶中的值使用插入排序。每一个桶中的元素按照顺序从左至右抽取出来重新构造原始的数组。