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