排序算法之：梳排序（Comb Sort） 题目描述 梳排序是冒泡排序的一种改进算法，由 Włodzimierz Dobosiewicz 于 1980 年提出，后由 Stephen Lacey 和 Richard Box 于 1991 年重新发现。其基本思想是通过一个较大的间隔（称为“梳子间隔”）开始比较和交换元素，逐步缩小间隔，最终使用间隔为 1 完成排序（即标准的冒泡排序）。梳排序通过提前消除远距离的逆序对，提升了冒泡排序的效率。 解题过程 初始化间隔 ： 初始间隔设置为数组长度 n ，并选择一个缩因子（通常为 1.3，经验证效果较好）。即 gap = n 。 迭代缩小间隔 ： 在每一轮中，将当前间隔 gap 按缩因子缩小（即 gap = floor(gap / 1.3) ），但需确保 gap ≥ 1 。若间隔缩小至 1，则算法进入最后的冒泡排序阶段。 单间隔排序 ： 对当前间隔 gap ，从数组起始位置开始，比较所有相距 gap 的元素对 (i, i+gap) 。若 arr[i] > arr[i+gap] ，则交换它们。这一过程需遍历整个数组直至无法再交换（类似冒泡排序，但步长为 gap ）。 终止条件 ： 当间隔为 1 且一整轮遍历中未发生任何交换时，说明数组已完全有序，算法终止。 举例说明 对数组 [8, 4, 1, 3, 2, 9] 进行梳排序： 初始间隔 gap = 6 / 1.3 ≈ 4 ： 比较并交换 (8,2) → [2,4,1,3,8,9] ， (4,9) （有序不交换）。 数组变为 [2,4,1,3,8,9] 。 缩小间隔 gap = 4 / 1.3 ≈ 3 ： 比较并交换 (2,3) （有序不交换）， (4,8) （有序不交换）， (1,9) （有序不交换）。 数组不变。 缩小间隔 gap = 3 / 1.3 ≈ 2 ： 比较并交换 (2,1) → [1,4,2,3,8,9] ， (4,3) → [1,3,2,4,8,9] ， (2,8) （有序不交换）， (4,9) （有序不交换）。 数组变为 [1,3,2,4,8,9] 。 间隔 gap = 2 / 1.3 ≈ 1 ： 执行冒泡排序：多次遍历后得到 [1,2,3,4,8,9] 。 关键点 缩因子 1.3 的经验值平衡了间隔缩小速度和排序效率。 梳排序平均时间复杂度为 O(n²)，但实际效率优于冒泡排序，接近 O(n log n)。