每日算法 — 使用java实现Comb Sort：梳子排序与冒泡排序优化

算法概述

Comb Sort（梳子排序）是由 Stephen Lacey 和 Richard Box 于 1991 年提出的一种改进型比较排序算法。它针对冒泡排序的主要缺陷——只能交换相邻元素导致的低效率——进行了关键优化。通过引入逐渐缩小的间隔（gap），Comb Sort 可以在排序初期快速将远距离的小元素移动到数组前端，从而显著提升排序效率。

核心思想

冒泡排序的 worst-case 时间复杂度为 O(n²)，其主要瓶颈在于只能比较相邻元素。当最小的元素位于数组末尾时，需要 n-1 轮交换才能移动到正确位置。

Comb Sort 的改进策略是：

1. 初始 gap 较大：从数组长度开始，比较相隔 gap 的两个元素
2. 逐步缩小 gap：每轮将 gap 乘以一个收缩因子（通常为 1.3），直到 gap 变为 1
3. 最终冒泡排序：当 gap = 1 时，执行最后一轮冒泡排序确保数组完全有序

gap 序列与收缩因子

收缩因子（shrink factor）是决定 Comb Sort 性能的关键参数。经过大量实验验证，1.3 是最优选择：

• 因子过小（如 1.1）：gap 缩小太慢，增加不必要的比较次数
• 因子过大（如 2.0）：gap 缩小太快，可能遗漏未排序的元素对

最优 gap 序列近似为：n, n/1.3, n/1.3², …, 1

Java 实现

基础实现

public class CombSort {
    // 最优收缩因子，经实验验证
    private static final double SHRINK_FACTOR = 1.3;

    /**
     * Comb Sort 主方法
     * @param arr 待排序数组
     */
    public static void combSort(int[] arr) {
        int n = arr.length;
        // 初始 gap 为数组长度
        int gap = n;
        // 标记本轮是否发生交换
        boolean swapped = true;

        // 当 gap > 1 或本轮发生过交换时继续
        while (gap > 1 || swapped) {
            // 计算下一个 gap，确保至少为 1
            gap = (int) (gap / SHRINK_FACTOR);
            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;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90, 88, 76, 50};
        System.out.println("排序前: " + java.util.Arrays.toString(arr));
        combSort(arr);
        System.out.println("排序后: " + java.util.Arrays.toString(arr));
    }
}

泛型版本与比较器支持

import java.util.Comparator;

public class CombSortGeneric {
    private static final double SHRINK_FACTOR = 1.3;

    /**
     * 支持泛型和自定义比较器的 Comb Sort
     */
    public static <T> void combSort(T[] arr, Comparator<? super T> comparator) {
        int n = arr.length;
        int gap = n;
        boolean swapped = true;

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

            swapped = false;
            for (int i = 0; i + gap < n; i++) {
                if (comparator.compare(arr[i], arr[i + gap]) > 0) {
                    T temp = arr[i];
                    arr[i] = arr[i + gap];
                    arr[i + gap] = temp;
                    swapped = true;
                }
            }
        }
    }

    // 自然排序版本
    public static <T extends Comparable<? super T>> void combSort(T[] arr) {
        combSort(arr, Comparator.naturalOrder());
    }
}

完整测试与性能对比

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

public class CombSortBenchmark {
    private static final double SHRINK_FACTOR = 1.3;

    public static void combSort(int[] arr) {
        int n = arr.length;
        int gap = n;
        boolean swapped = true;
        while (gap > 1 || swapped) {
            gap = (int) (gap / SHRINK_FACTOR);
            if (gap < 1) gap = 1;
            swapped = false;
            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;
                }
            }
        }
    }

    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[] sizes = {1000, 5000, 10000, 50000};
        Random rand = new Random(42);

        System.out.println("规模\t\tComb Sort(ms)\tBubble Sort(ms)");
        for (int size : sizes) {
            int[] arr1 = new int[size];
            int[] arr2 = new int[size];
            for (int i = 0; i < size; i++) {
                arr1[i] = rand.nextInt(size);
                arr2[i] = arr1[i];
            }

            long start = System.currentTimeMillis();
            combSort(arr1);
            long combTime = System.currentTimeMillis() - start;

            start = System.currentTimeMillis();
            bubbleSort(arr2);
            long bubbleTime = System.currentTimeMillis() - start;

            System.out.printf("%d\t\t%d\t\t%d%n", size, combTime, bubbleTime);
        }
    }
}

复杂度分析

尽管最坏情况仍为 O(n²)，但在实际测试中，Comb Sort 的性能通常是冒泡排序的数倍到数十倍。对于 50000 个元素的随机数组，Comb Sort 通常可在 100ms 内完成，而冒泡排序可能需要数秒。

应用场景

1. 教学场景：作为冒泡排序改进的经典案例，帮助理解间隔排序思想
2. 小规模数据：对于 n 小于 1000 的数据，Comb Sort 实现简单且性能可接受
3. 嵌入式系统：原地排序、代码量小，适合内存受限环境
4. 快速排序的混合策略：在递归深度较小时切换到 Comb Sort 减少递归开销

总结

Comb Sort 通过对冒泡排序引入动态间隔，有效解决了远距离元素交换效率低的问题。虽然它不属于 O(n log n) 算法家族，但其简洁的实现和优于冒泡排序的实际表现，使其成为学习排序算法演进历程的重要一课。理解 Comb Sort 有助于深入掌握快速排序、希尔排序等更高级间隔排序算法的核心思想。