桶排序（Bucket sort）是排序算法的一种，适用于待排序数据值域较大但分布比较均匀的情况。
工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后依次把各个桶中的记录列出来记得到有序序列。计数排序可以近似看成桶尺寸为1时的桶排序。
桶排序按下列步骤进行：
- 设置一个定量的数组当作空桶
- 遍历序列，并将元素一个个放到对应的桶中
- 对每个不是空的桶进行排序
- 从不是空的桶里把元素再放回原来的序列中
时间复杂度
桶排序的平均时间复杂度为 （将值域平均分成块 + 排序 +重新合并元素），当 时为
桶排序的最坏时间复杂度为
代码实现