桶排序

桶排序在平均情况下以线性时间运行。 像计数排序一样，桶排序速度很快，因为它考虑了一些关于输入的内容。 桶排序认为输入是由随机过程生成的，该过程将元素均匀地分布在区间 μ=[0,1] 上。

1. 将 μ 分成 n 个不重叠的区间，称为桶。
2. 将每个输入数字放入其桶中
3. 使用简单的算法对每个桶进行排序，例如插入排序，然后
4. 连接已排序的列表。

桶排序认为输入是一个 n 元素数组 A，并且数组中的每个元素 A [i] 满足 0≤A [i] <1。 该代码依赖于链表（桶）的辅助数组 B [0....n-1]，并认为存在维护此类列表的机制。

BUCKET-SORT (A)
 1. n ← length [A]
 2. for i ← 1 to n
 3. do insert A [i] into list B [n A[i]]
 4. for i ← 0 to n-1
 5. do sort list B [i] with insertion sort.
 6. Concatenate the lists B [0], B [1] ...B [n-1] together in order.

示例：说明在数组上进行 BUCKET-SORT 的操作。

解决方案

图：桶排序：步骤 1，按排序顺序将键放置在桶中

图：桶排序：步骤 2，连接列表

图：桶排序：最终排序序列