桶分类平均在线性时间运行。与计算排序一样, 存储桶排序也很快速, 因为它考虑了有关输入的某些内容。桶排序认为输入是通过随机过程生成的, 该过程在元素μ= [0, 1]上均匀分布元素。
要对n个输入数字进行排序, 请按存储桶排序
- 将μ划分为n个非重叠间隔, 称为存储桶。
- 将每个输入数字放入其存储桶中
- 使用简单的算法（例如, 插入排序, 然后
- 连接已排序的列表。
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, 连接列表
文章图片
【桶排序算法实现详细分析】无花果：桶排序：最后的排序顺序
