桶排序

概述

桶排序（Bucket Sort） 是一种非比较排序算法，假设输入服从均匀分布，将元素分配到若干个桶中，对每个桶分别排序后依次合并。期望时间复杂度为 $O(n)$，最坏情况为 $\Theta (n^2)$。

定义

桶排序

桶排序假设输入数组 $A[\mathrm{1..}n]$ 中的元素均匀分布在区间 $[0,1)$ 上。

算法步骤：

1. 创建 $n$ 个空桶 $B[\mathrm{0..}n-1]$。
2. 将 $A[i]$ 放入桶 $B[\lfloor n\cdot A[i]\rfloor ]$ 中。
3. 对每个非空桶单独排序（通常使用插入排序）。
4. 按桶的顺序依次连接各桶中的元素。

期望时间复杂度：$O(n)$（均匀分布假设下） 最坏时间复杂度：$\Theta (n^2)$（所有元素落入同一个桶时）

核心性质

均匀分布假设

桶排序的高效性依赖于输入在 $[0,1)$ 上均匀分布的假设。在此假设下：

• 每个桶中期望包含 $O(1)$ 个元素。
• 对每个桶排序的期望时间为 $O(1)$（使用插入排序）。
• $n$ 个桶的总期望时间为 $O(n)$。

期望运行时间的分析

设 $n_i$ 为落入桶 $i$ 的元素个数，${\sum }_{i=0}^{n-1}{n}_i=n$。桶排序的总运行时间为：

$T(n)=\Theta (n)+{\sum }_{i=0}^{n-1}O(n_i^2)$

在均匀分布下，可以证明 $\mathrm{E}\left[{\sum }_{i=0}^{n-1}{n}_i^2\right]=2-1/n$，因此期望时间为 $O(n)$。

稳定性

桶排序可以是稳定的，取决于桶内使用的排序算法是否稳定。

适用场景

• 输入数据在已知范围内均匀分布。
• 适用于浮点数排序（尤其是 $[0,1)$ 区间内的数）。
• 可以推广到任意范围 $[a,b)$，通过线性映射将元素映射到 $[0,1)$。

章节扩展

第8章：线性时间排序

桶排序是第8章讨论的三种非比较排序算法之一，展示了在概率假设下突破比较排序下界的方法。

参见

• 比较排序
• 插入排序
• 随机化算法