桶排序把值域划分成若干个区间（桶），把元素放进对应桶中，再在每个桶内排序，最后按桶序合并。

Ph1zの理解： 桶排序就像按成绩分班——90~100 分一班，80~90 分一班……每个班内部再排成绩，最后按班序输出。如果成绩均匀分布，每个班人数差不多，班内排序很快，整体接近线性。但如果全挤在一个班……那就退化了。

正确性证明

• 每个元素都会被放进唯一对应的桶；
• 桶内排序后，桶内元素从小到大排列；
• 按桶编号顺序输出时，所有桶之间的元素大小关系也正确；
• 因为桶编号按区间顺序排列，桶内排序保证区间内顺序正确，故合并后得到全局有序序列。 ✓

复杂度分析

设有 $m$ 个桶，平均每个桶里有 $n/m$ 个元素。若每个桶内用插入排序，复杂度为：

$$T(n)=O(n)+m\cdot O\left({\left(\frac{n}{m}\right)}^2\right)=O(n)+O\left(\frac{n^2}{m}\right).$$

情况	时间复杂度	直觉
最好	$O(n)$	每个桶最多 1 个元素，桶内不用排
平均（均匀分布）	$O(n)$	每桶 $\approx n/m$ 个，$m$ 取 $\mathrm{\Theta }(n)$ 时
最坏	$O(n^2)$	所有元素落入同一个桶，退化为插入排序

空间复杂度： $O(n)$（桶 + 桶内元素）。

稳定性： 视桶内排序策略而定；若桶内使用稳定排序并且按桶顺序合并，可保持稳定。