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

题目描述
Flash Sort是一种基于数据分布的线性时间复杂度的非比较排序算法，适用于已知数据均匀分布的场合。其核心思想是通过数据的分布特征，将元素快速分配到对应的区间（类），再对每个区间进行插入排序，最后合并结果。本题要求理解Flash Sort的核心步骤，特别是其分布优化策略如何减少比较操作并提升排序效率。

解题过程

1. 核心思想：
   Flash Sort假设输入数组的元素服从均匀分布。算法先计算数据的最大值、最小值，根据数据范围将数组划分为多个区间（称为"类"），每个类对应一个值范围。通过线性扫描，将元素分配到对应类中，减少后续排序的规模。

2. 步骤分解：

   • 步骤1：确定数据范围
     扫描数组，找到最小值 minVal 和最大值 maxVal。计算数据范围：range = maxVal - minVal。
   • 步骤2：划分区间（类）
     设定类的数量 m（通常取 0.43 * n，n 为数组长度）。每个类的宽度为 classWidth = range / m。创建长度为 m 的辅助数组 L，用于记录每个类的元素数量。
   • 步骤3：分布元素到类中
     遍历数组，对每个元素 arr[i]，计算其所属的类索引：

     classIndex = floor((arr[i] - minVal) / classWidth)
     

     确保 classIndex 不超过 m-1（例如，最大值应属于最后一类）。更新 L[classIndex] 计数。
   • 步骤4：计算类边界
     根据 L 数组，计算每个类在输出数组中的起始位置（前缀和操作），形成类边界指针。
   • 步骤5：元素置换
     通过交换操作，将元素放置到对应类的区间内。此步骤需循环处理，确保每个元素被移动到正确区间。
   • 步骤6：类内排序
     对每个非空类进行插入排序（因类内元素数量少，插入排序高效）。
   • 步骤7：合并结果
     按类顺序连接排序后的区间，得到最终有序数组。

3. 分布优化策略：

   • 自适应类宽度：若数据分布不均匀，可动态调整 classWidth，避免某些类过大。例如，通过统计分布密度，合并稀疏类或拆分密集类。
   • 边界处理：对类边界元素特殊处理，防止因浮点计算误差导致索引越界。
   • 稳定性优化：Flash Sort本身不稳定，但可通过记录元素原始位置来实现稳定排序（需额外空间）。

4. 复杂度分析：

   • 时间复杂度：平均 O(n)，最坏 O(n²)（当数据分布极不均匀时，退化为插入排序）。
   • 空间复杂度：O(m)（辅助数组 L 和类边界指针）。

5. 应用场景：
   适用于数据量较大且分布均匀的情况（如科学计算中的浮点数据），但对离散数据或分布未知的数据效率可能下降。