桶排序(Bucket Sort)

桶排序是一种基于分配思想的排序算法。它先根据元素取值把数据划分到若干个有序排列的桶里,再对每个桶内部分别排序,最后按桶的顺序依次收集,得到整体有序的序列。

概述

桶排序假设输入数据在某个取值区间上大致均匀分布。它把该区间等分成多个子区间,每个子区间对应一个桶,元素按其取值落入相应的桶。若分布均匀,每个桶内元素很少,桶内排序代价极低,整体便能接近线性时间。

核心原理

• 分桶:按元素取值将其映射到对应区间的桶中,桶之间保持有序关系。
• 桶内排序:对每个非空桶用插入排序或递归桶排序等方法排序。
• 合并收集:按桶的顺序依次取出元素,自然得到全局有序结果。
• 性能依赖分布:输入均匀时期望线性;若数据集中于少数桶,则退化为桶内排序算法的复杂度。

应用场景

桶排序适合排序在已知区间上均匀分布的浮点数或大范围整数,例如均匀随机生成的数值。它也可用于外部排序中,把海量数据先分桶到不同文件再分别处理。与计数排序、基数排序同属分配式排序家族,在合适分布下效率突出。

常见问题

问:桶排序一定是线性时间吗?答:不一定,线性只是数据均匀分布时的期望复杂度;若元素大量集中在个别桶内,则退化为桶内所用排序算法的时间复杂度。

问:桶排序稳定吗?答:是否稳定取决于分桶时的插入顺序和桶内所用的排序算法;若桶内使用稳定排序并保持原相对顺序,则整体可以做到稳定。