每日算法 — 使用java实现梳排序：冒泡排序的gap衰减优化策略

引言

梳排序（Comb Sort）是由Wlodzimierz Dobosiewicz于1980年提出的一种改进版交换排序算法。它是对经典冒泡排序的巧妙优化，通过引入逐步衰减的间隔（gap）来消除冒泡排序中著名的”乌龟问题”——即尾部的小元素需要极多次交换才能移动到头部。

梳排序的名称来源于梳子（comb）的比喻：初始时像用一把宽齿梳子梳理乱发，先处理远距离的元素对；随着间隙逐渐缩小，最终细齿梳理完成精确排序。这种多阶段的分治思路让梳排序在实际运行中表现优异，平均性能接近快速排序。

核心思想

冒泡排序只比较相邻元素，导致小元素在数组末尾时需要逐一”冒泡”到前端，时间复杂度始终为 O(n²)。梳排序的突破在于：

初始间隔较大：比较相距较远的元素对，快速将远距的逆序对消除
间隔逐步衰减：通常使用缩减因子 shrink = 1.3（经验最优值），每次 gap = gap / 1.3
最终间隔为1：当 gap 衰减到1时，执行一次标准的冒泡排序收尾

经验表明，1.3 是最优的缩减因子。若因子过小（如2），则远距离交换不足；若因子过大（如1.1），则迭代次数过多。

算法实现

import java.util.Arrays;
import java.util.Random;

/**
 * 梳排序实现类
 * 核心思想：通过逐步衰减的间隔进行多轮交换排序，消除冒泡排序的"乌龟问题"
 */
public class CombSort {

    // 经验最优的间隔缩减因子，由研究者通过大量实验得出
    private static final double SHRINK_FACTOR = 1.3;

    /**
     * 执行梳排序
     * @param arr 待排序数组
     */
    public static void combSort(int[] arr) {
        int n = arr.length;
        // 初始间隔设为数组长度
        int gap = n;
        // 标记本轮是否发生过交换
        boolean swapped = true;

        // 当间隔大于1或仍有交换发生时继续排序
        while (gap > 1 || swapped) {
            // 计算新的间隔，确保至少为1
            if (gap > 1) {
                gap = (int) (gap / SHRINK_FACTOR);
                // 防止间隔为0
                if (gap < 1) {
                    gap = 1;
                }
            }

            swapped = false;

            // 对相距gap的元素进行交换排序
            for (int i = 0; i + gap < n; i++) {
                if (arr[i] > arr[i + gap]) {
                    // 交换逆序对
                    int temp = arr[i];
                    arr[i] = arr[i + gap];
                    arr[i + gap] = temp;
                    swapped = true;
                }
            }
        }
    }

    /**
     * 带统计信息的梳排序，用于分析各轮gap的交换次数
     * @param arr 待排序数组
     */
    public static void combSortWithStats(int[] arr) {
        int n = arr.length;
        int gap = n;
        boolean swapped = true;
        int round = 0;

        System.out.println("=== 梳排序执行过程 ===");

        while (gap > 1 || swapped) {
            if (gap > 1) {
                gap = (int) (gap / SHRINK_FACTOR);
                if (gap < 1) gap = 1;
            }

            swapped = false;
            int swapCount = 0;
            round++;

            for (int i = 0; i + gap < n; i++) {
                if (arr[i] > arr[i + gap]) {
                    int temp = arr[i];
                    arr[i] = arr[i + gap];
                    arr[i + gap] = temp;
                    swapped = true;
                    swapCount++;
                }
            }

            System.out.printf("第%2d轮 gap=%2d 交换次数: %d%n", round, gap, swapCount);
        }

        System.out.println("总轮数: " + round);
    }

    /**
     * 标准冒泡排序，用于与梳排序对比
     * @param arr 待排序数组
     */
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    /**
     * 主程序：演示梳排序并与冒泡排序进行性能对比
     */
    public static void main(String[] args) {
        int size = 10000;
        Random random = new Random(42);

        // 生成随机测试数据
        int[] arr1 = new int[size];
        int[] arr2 = new int[size];
        for (int i = 0; i < size; i++) {
            arr1[i] = random.nextInt(size);
            arr2[i] = arr1[i];
        }

        // 梳排序性能测试
        long start1 = System.currentTimeMillis();
        combSort(arr1);
        long time1 = System.currentTimeMillis() - start1;

        // 冒泡排序性能测试（数据量大时会很慢，这里仅演示）
        long start2 = System.currentTimeMillis();
        // 对于大数组，冒泡排序过慢，这里只测试小数组
        if (size <= 5000) {
            bubbleSort(arr2);
        }
        long time2 = System.currentTimeMillis() - start2;

        System.out.println("数组大小: " + size);
        System.out.println("梳排序耗时: " + time1 + "ms");
        if (size <= 5000) {
            System.out.println("冒泡排序耗时: " + time2 + "ms");
        } else {
            System.out.println("冒泡排序: 数据量过大，跳过测试");
        }

        // 验证排序正确性
        boolean sorted = true;
        for (int i = 1; i < arr1.length; i++) {
            if (arr1[i] < arr1[i - 1]) {
                sorted = false;
                break;
            }
        }
        System.out.println("梳排序验证: " + (sorted ? "通过" : "失败"));

        // 小规模演示详细过程
        System.out.println("\n=== 小规模详细演示 ===");
        int[] demo = {64, 34, 25, 12, 22, 11, 90, 5};
        System.out.println("原始数组: " + Arrays.toString(demo));
        combSortWithStats(demo.clone());
        combSort(demo);
        System.out.println("排序结果: " + Arrays.toString(demo));
    }
}

算法详解

间隔衰减策略

梳排序的关键在于间隔（gap）的衰减方式。使用 gap = gap / 1.3 的衰减策略，可以让算法在前期快速消除远距离的逆序对，后期精细调整局部顺序。

轮次	初始gap=8时的衰减序列
1	8 → 6 (8/1.3≈6)
2	6 → 4 (6/1.3≈4)
3	4 → 3 (4/1.3≈3)
4	3 → 2 (3/1.3≈2)
5	2 → 1 (2/1.3≈1)
6+	1（标准冒泡排序收尾）

为什么1.3是最优因子

研究者通过实验对比了不同缩减因子的性能：
– 因子 2.0（类似希尔排序的初始间隔）：远距离交换不足，性能接近 O(n²)
– 因子 1.1：迭代轮次过多，开销增大
– 因子 1.3：在交换充分性和迭代次数之间取得最佳平衡

复杂度分析

指标	最优	平均	最差	说明
时间复杂度	O(n log n)	O(n² / 2^p)	O(n²)	p为间隔衰减轮数，实际表现接近O(n log n)
空间复杂度	O(1)	O(1)	O(1)	原地排序，仅使用常数额外空间
稳定性	不稳定	不稳定	不稳定	远距离交换会破坏相等元素的相对顺序

与冒泡排序和希尔排序的对比

特性	冒泡排序	梳排序	希尔排序
间隔策略	固定为1	逐步衰减至1	预定义序列衰减
平均时间	O(n²)	~O(n log n)	O(n^1.3)
最坏时间	O(n²)	O(n²)	O(n²)
空间	O(1)	O(1)	O(1)
实现难度	简单	简单	中等

梳排序可以看作是冒泡排序和希尔排序的”中间产物”：它像冒泡排序一样简单，又像希尔排序一样利用间隔来提升效率。

实际应用场景

梳排序适用于以下场景：

内存极度受限的环境：仅需 O(1) 额外空间，实现代码极短
数据基本有序但含有少量远距离逆序：梳排序能快速消除此类逆序
教学演示：作为冒泡排序改进的经典案例，展示算法优化的思路

总结

梳排序通过对间隔的巧妙衰减，成功克服了冒泡排序的最大缺陷。它证明了一个重要的算法设计原则：有时不需要发明全新的算法，只需对现有算法的关键参数进行优化，就能获得显著的性能提升。

本文的Java实现展示了梳排序的简洁代码和高效执行过程。在大数据量测试中，梳排序的性能远超冒泡排序，接近更复杂的快速排序。这一结果提醒我们：在算法设计中，理解问题的本质特征（如逆序对的距离分布）比盲目追求复杂数据结构更为重要。

Tagged with: Comb Sort 冒泡排序希尔排序排序算法梳排序间隔衰减