当计算集合中的n个元素时，如果能够构建一个小得多的k个值的集合，那么这个时候就可以使用计数排序。给定n个元素的集合，桶排序构造了n个桶来切分输入集合，因此桶排序能够降低处理时其在额外空间的开销。如果一个散列函数，hash(Ai)，用来均匀地将n个元素分配到n个桶中，那么如图4-18所示的桶排序在最坏情况下也能够以O(n)的时间进行排序。如果希望使用桶排序，那么需要满足以下两点。
图 4-18 桶排序详细介绍均匀分布
输入数据需要均匀分布在一个给定的范围内。基于这种分配，算法创建了n个桶来平分输入数据。
有序散列函数
桶必须是有序的。也就是说，如果i＜j，桶bi中的元素要字典序小于桶bj中的元素。
桶排序不适合排序随机字符串，但是，它能够被用来排序在区间[0,1)间均匀分配的浮点数。
一旦所有待排序的元素都被放入桶中，桶排序从左至右对每个桶中的值使用插入排序。每一个桶中的元素按照顺序从左至右抽取出来重新构造原始的数组。