桶排序算法实现详细分析

桶分类平均在线性时间运行。与计算排序一样, 存储桶排序也很快速, 因为它考虑了有关输入的某些内容。桶排序认为输入是通过随机过程生成的, 该过程在元素μ= [0, 1]上均匀分布元素。

要对n个输入数字进行排序, 请按存储桶排序

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的操作。

A = (0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 068)

解：

图：存储桶排序：第1步, 将密钥按排序顺序放入垃圾箱

图：存储桶排序：步骤2, 连接列表

无花果：桶排序：最后的排序顺序