排序算法之：梳排序（Comb Sort）的进阶优化与性能分析 题目描述 梳排序是冒泡排序的一种改进算法，由 Włodzimierz Dobosiewicz 于 1980 年提出，后由 Stephen Lacey 和 Richard Box 重新发现。其核心思想是通过较大的间隔比较和交换元素，逐步缩小间隔至 1，最终完成排序。本题要求实现梳排序，并探讨其关键参数（收缩因子）对性能的影响，以及如何优化以避免最坏情况。 解题过程 基本思想 梳排序通过一个初始间隔（通常为数组长度）开始，比较相距较远的元素，消除数组末端的微小无序情况。 间隔按收缩因子（通常取 1.3）逐步缩小，重复比较和交换，直到间隔为 1 时执行最后一次冒泡排序操作。 算法步骤 步骤 1 ：初始化间隔 gap = n （数组长度），并设置收缩因子 shrink = 1.3 。 步骤 2 ：循环直到 gap = 1 且本轮无交换： 更新间隔： gap = max(1, floor(gap / shrink)) 。 遍历数组索引 i 从 0 到 n - gap - 1 ： 比较 arr[i] 和 arr[i + gap] ，若逆序则交换。 步骤 3 ：当 gap = 1 时，算法退化为冒泡排序，但此时数组已基本有序，效率较高。 关键优化：收缩因子的选择 理论最优收缩因子为 1.3（经验值），可减少不必要的比较次数。 若收缩因子过小（如 1.1），间隔下降过快，可能无法有效消除远端无序；若过大（如 2），则接近希尔排序，但可能错过局部优化机会。 避免最坏情况 最坏时间复杂度为 O(n²)，但通过以下优化可接近 O(n log n)： 在间隔迭代中加入提前终止条件：若本轮无交换且 gap > 1 ，则直接缩小间隔继续。 对间隔为 1 的最后一轮，利用冒泡排序的优化（记录交换位置），减少冗余比较。 示例演示 对数组 [8, 4, 1, 3, 2] 排序： 初始 gap = 5/1.3 ≈ 3 ：比较索引 0-3（8 与 3）、1-4（4 与 2），交换后得 [3, 2, 1, 8, 4] 。 更新 gap = 3/1.3 ≈ 2 ：比较索引 0-2（3 与 1）、1-3（2 与 8）、2-4（1 与 4），无需交换。 更新 gap = 2/1.3 ≈ 1 ：执行冒泡排序，最终得 [1, 2, 3, 4, 8] 。 性能分析 平均时间复杂度：O(n² / 2^p)（p 为收缩因子迭代次数），实践中接近 O(n log n)。 空间复杂度：O(1)，为原地排序。 稳定性：非稳定排序（远距离交换可能破坏相同元素的相对顺序）。