桶排序
桶排序是一种非比较排序算法，它将元素分配到多个桶中，每个桶单独排序后合并。它适用于均匀分布的数据，在特定情况下可以达到线性时间复杂度。
算法原理
桶排序的基本思想是：将数组分成若干个桶，每个桶负责一个范围的元素。将元素分配到对应的桶中，然后对每个桶进行排序（可以使用其他排序算法），最后将所有桶的元素合并起来。
算法步骤
- 确定桶的数量和范围
- 创建空桶
- 将元素分配到对应的桶中
- 对每个桶进行排序
- 将所有桶的元素合并起来
时间复杂度
- 最坏情况：O(n²) - 当所有元素都分配到同一个桶时
- 平均情况：O(n + k)，其中 n 是元素个数，k 是桶的数量
- 最好情况：O(n) - 当元素均匀分布时
空间复杂度
O(n + k) - 桶排序需要额外的空间来存储桶和输出数组。
稳定性
桶排序是稳定的排序算法（取决于桶内使用的排序算法），相等元素的相对顺序不会改变。
适用场景
- 数据均匀分布的情况
- 浮点数排序
- 需要线性时间复杂度的排序
优缺点
- 优点：在数据均匀分布时效率很高；可以并行处理不同的桶
- 缺点：需要额外的空间；当数据分布不均匀时效率低；桶的数量和范围需要合理选择