排序算法之：Flash Sort（闪电排序）的分布优化策略 题目描述 Flash Sort是一种基于数据分布的线性时间排序算法，适用于数据分布均匀且取值范围已知的情况。其核心思想是通过数据的分布特征将元素分配到不同的"桶"中，再对每个桶进行局部排序，最后合并结果。该算法在特定条件下时间复杂度可接近O(n)，但需要额外的空间开销。 解题过程 数据分布分析 假设待排序数组为 arr ，长度为 n ，已知数据的最小值 minVal 和最大值 maxVal 。 将数据范围 [minVal, maxVal] 划分为 m 个等宽区间（通常取 m ≈ 0.43n ），每个区间对应一个桶。 元素分类与桶分配 遍历数组，根据公式计算每个元素所属的桶索引： \[ \text{bucketIndex} = \left\lfloor \frac{m \cdot (arr[ i ] - minVal)}{maxVal - minVal} \right\rfloor \] 统计每个桶中的元素数量，并构建前缀和数组 prefixSum ，用于记录每个桶的起始位置。 元素置换与局部排序 根据 prefixSum 将元素置换到对应的桶区间中。置换过程中采用循环交换策略，确保每个元素被放置到正确区间。 对每个非空桶使用插入排序（或其他简单排序算法）进行局部排序，因为桶内元素数量较少且分布集中。 合并结果 按桶顺序将排序后的桶内容依次拼接，得到最终有序数组。 示例 假设数组 [29, 10, 15, 37, 14] ， minVal=10 ， maxVal=37 ，设 m=3 ： 计算桶索引： 29 → floor(3*(29-10)/27) = 2 10 → 0 ，15 → 0 ，37 → 2 ，14 → 0 桶0： [10, 15, 14] ，桶2： [29, 37] 桶内插入排序：桶0→ [10,14,15] ，桶2→ [29,37] 合并结果： [10,14,15,29,37] 关键优化点 桶数量 m 的选取需平衡分布均匀性和桶内排序开销。 通过前缀和优化置换步骤，避免频繁移动元素。 若数据分布极度不均匀，退化为O(n²)时间复杂度，需结合其他算法（如快速排序）作为备用方案。