排序算法之：Flash Sort（闪电排序）的分布优化策略

题目描述：
Flash Sort是一种高效的线性时间排序算法，特别适用于已知数据分布的均匀分布数据集。它通过分析数据分布特征，将元素分配到不同桶中，然后对每个桶进行插入排序。与桶排序类似但具有更好的分布优化策略，能够在O(n)时间内完成排序。

解题过程：

1. 数据分布分析阶段

   • 首先遍历整个数组，找到最小值min和最大值max
   • 根据数组长度n，将数据范围[min, max]等分为m个区间（通常m约取0.1n到0.5n）
   • 计算每个区间的宽度：L = (max - min) / m

2. 分类计数阶段

   • 创建大小为m的计数数组count，初始化为0
   • 再次遍历数组，对每个元素x，计算其所属的区间索引：
     k = floor((x - min) / L)
     确保k在[0, m-1]范围内（对边界值进行特殊处理）
   • 统计每个区间中的元素数量，记录在count数组中

3. 前缀和计算阶段

   • 对count数组计算前缀和，得到每个区间的起始位置
   • 例如：prefix[0] = 0, prefix[i] = prefix[i-1] + count[i-1]
   • 这样prefix[i]就表示第i个区间元素在排序后数组中的起始位置

4. 元素重排阶段（核心步骤）

   • 创建一个与原数组相同大小的临时数组
   • 第三次遍历原数组，根据每个元素的区间索引k
   • 将其放入临时数组的prefix[k]位置，然后prefix[k]增加1
   • 这个阶段完成了元素的初步分类

5. 桶内排序阶段

   • 对临时数组中的每个区间（桶）分别进行插入排序
   • 由于数据分布均匀，每个桶的大小相对均衡
   • 插入排序在小规模数据上效率很高

6. 结果合并阶段

   • 将各个排序后的桶按顺序连接起来
   • 得到完全有序的最终数组

关键优化策略：

• 区间数量m的选择需要平衡：m太小时分类效果差，m太大时额外开销大
• 对于边界附近的元素需要特殊处理，防止索引越界
• 可以通过采样估计数据分布，动态确定最佳的m值
• 在数据分布极度不均匀时，可以递归应用Flash Sort

时间复杂度分析：

• 在均匀分布假设下，平均时间复杂度为O(n)
• 最坏情况（极端不均匀分布）退化为O(n²)
• 空间复杂度为O(n)用于临时数组