桶排序的进阶应用：对浮点数进行排序 题目描述：设计一个算法对范围在 [ 0,1)内的n个均匀分布的浮点数进行排序，要求平均时间复杂度为O(n)。 解题过程： 问题分析： 输入是n个在 [ 0,1)区间内均匀分布的浮点数 常规比较排序算法的时间复杂度下界是O(n log n) 桶排序在数据分布均匀时可以达到O(n)的平均时间复杂度 算法设计： 创建n个桶（链表或数组），每个桶负责一个小区间 将 [ 0,1)区间平均分成n个小区间，第i个桶负责区间 [ i/n, (i+1)/n) 遍历数组，将每个元素放入对应的桶中 对每个非空桶内的元素进行排序（可使用插入排序） 按顺序将各个桶中的元素合并 具体步骤： 步骤1：初始化n个空桶 步骤2：将每个元素乘以n，取整数部分作为桶索引 步骤3：将元素放入对应桶中 步骤4：对每个桶内的元素进行插入排序 步骤5：按桶顺序连接所有元素 时间复杂度分析： 分配阶段：O(n) 每个桶的排序：由于数据均匀分布，每个桶内元素数量接近1，插入排序为O(1) 合并阶段：O(n) 总平均时间复杂度：O(n) 示例演示： 输入：[ 0.23, 0.45, 0.12, 0.89, 0.67 ]，n=5 桶分配： 桶0： [ 0,0.2)：0.12 桶1： [ 0.2,0.4)：0.23 桶2： [ 0.4,0.6)：0.45 桶3： [ 0.6,0.8)：0.67 桶4： [ 0.8,1.0)：0.89 排序后直接连接得到有序数组 关键点： 数据必须均匀分布才能保证性能 桶的数量选择很重要，通常等于元素个数 对每个桶使用插入排序是因为桶内元素较少时效率高