桶排序的进阶应用：对浮点数进行排序

题目描述
给定一个包含浮点数的数组，设计一个高效的排序算法对其进行升序排序。要求利用桶排序的思想，处理浮点数在 [0, 1) 范围内的均匀分布情况，并分析其时间复杂度和空间复杂度。

解题过程

1. 理解问题与桶排序原理

   • 桶排序适用于数据分布均匀的场景，将数据分到有限数量的桶中，每个桶内单独排序后合并。
   • 对于浮点数，若已知其范围（如 [0, 1)），可将其映射到桶中，利用均匀分布特性保证桶内数据量均衡。

2. 设计桶的映射规则

   • 假设数组长度为 n，创建 n 个空桶（链表或动态数组）。
   • 遍历每个浮点数 x，计算其桶索引：
     index = floor(x * n)
     例如：n=10，x=0.78 → 索引为 floor(0.78*10)=7。
     此映射确保数据均匀分散到 n 个桶中。

3. 分桶操作

   • 遍历数组，将每个元素放入对应的桶中。

     buckets = [[] for _ in range(n)]  # 初始化n个空桶
     for x in arr:
         index = int(x * n)  # 计算桶索引
         buckets[index].append(x)
     

4. 桶内排序与合并

   • 对每个非空桶使用简单排序算法（如插入排序），因桶内数据量小，插入排序高效。
   • 按桶顺序（索引 0 到 n-1）合并所有桶，得到有序数组。

     result = []
     for bucket in buckets:
         insertion_sort(bucket)  # 桶内排序
         result.extend(bucket)
     

5. 复杂度分析

   • 时间复杂度：
     • 分桶 O(n)，桶内排序平均 O(n)（均匀分布时每个桶大小接近1），最坏 O(n²)（所有数据集中于一桶）。
     • 平均复杂度 O(n)，优于比较排序下界 O(n log n)。
   • 空间复杂度：O(n)（存储桶和结果）。

6. 处理特殊情况

   • 若数据含 1.0：映射索引为 n，会越界。需扩展桶数至 n+1 或限制 x*n < n。
   • 非均匀分布：可结合样本采样优化桶范围，避免桶间数据量失衡。

关键点

• 桶排序通过分布均匀性将排序成本分散到各桶，突破比较排序下限。
• 浮点数映射时需注意边界处理，避免索引越界。