【一、项目背景详细介绍】

梳状排序（Comb Sort）是一种基于冒泡排序改进的比较排序算法，由W. L. Rabin于1980年提出，其核心思想是逐步缩小“间距（gap）”进行比较与交换，解决冒泡排序中小值或大值“龟速”移动的问题。通过使用缩小因子（通常为1.3），Comb Sort能在实践中显著提高冒泡排序的性能，平均时间复杂度约为O(n²/2^p)，接近O(n²)但常数较小，适合中小规模数组排序。

Comb Sort简单易实现，原地排序，无额外空间开销，常用于教学和工程中需要快速编写但不追求最优性能的场景，也可作为其他排序算法的基线比较。

【二、项目需求详细介绍】

1. 功能需求

   • 在Java环境中实现Comb Sort算法，对整型数组和泛型可比较对象数组进行正序/逆序排序；

   • 支持自定义缩小因子（shrink factor），默认值1.3；

2. 性能需求

   • 平均时间复杂度略优于冒泡排序，但最坏情况仍为O(n²)；

   • 原地排序，额外空间复杂度O(1)；

3. 代码质量需求

   • 模块化设计：包括入口方法、计算下一个间距、核心排序循环；

   • 注释完备：说明间距更新、比较与交换逻辑；

   • 提供测试示例：包括空数组、单元素、随机数组和重复元素场景。

【三、相关技术详细介绍】

1. 间距（gap）概念

   • 初始间距为数组长度，随后每轮使用gap = floor(gap / shrinkFactor)更新；

   • 当gap减至1后，进行常规冒泡比较，确保完全有序；

2. 缩小因子（shrink factor）

   • 建议取值在1.2~1.5之间，常用1.3；影响算法收敛速度与性能；

3. 泛型与Comparable接口

   • 使用<T extends Comparable<T>>支持任意可比较对象；

4. 交换与原地排序

   • 比较arr[i]与arr[i+gap]，若逆序则交换；保持原地。

【四、实现思路详细介绍】

1. 入口方法

   • combSort(int[] arr, boolean ascending, double shrinkFactor)；

   • 泛型版本combSort(T[] arr, boolean ascending, double shrinkFactor)；

2. 核心循环

   • 初始化gap = arr.length，swapped = true；

   • 当gap > 1或swapped == true时：
     a) 更新gap = max(1, floor(gap / shrinkFactor))；
     b) 重置swapped = false；
     c) 遍历i从0到n - gap - 1，比较并交换arr[i]与arr[i+gap]，若交换则swapped = true；

3. 终止条件

   • 当gap == 1且未发生任何交换时，排序完成；

4. 升降序切换

   • 在比较时根据ascending使用>或<判断。

【五、完整实现代码】

// 文件：CombSort.java
// 描述：Comb Sort实现，支持整型与泛型，升序/逆序及自定义shrinkFactor

import java.util.Arrays;

public class CombSort {
    private static final double DEFAULT_SHRINK = 1.3;

    /**
     * 原生整型数组Comb Sort
     */
    public static void combSort(int[] arr, boolean ascending, double shrinkFactor) {
        if (arr == null || arr.length < 2) return;
        int n = arr.length;
        int gap = n;
        boolean swapped = true;
        while (gap > 1 || swapped) {
            // 更新间距
            gap = (int) Math.floor(gap / shrinkFactor);
            if (gap < 1) gap = 1;
            swapped = false;
            for (int i = 0; i + gap < n; i++) {
                if (ascending ? arr[i] > arr[i + gap] : arr[i] < arr[i + gap]) {
                    int tmp = arr[i]; arr[i] = arr[i + gap]; arr[i + gap] = tmp;
                    swapped = true;
                }
            }
        }
    }

    public static void combSort(int[] arr, boolean ascending) {
        combSort(arr, ascending, DEFAULT_SHRINK);
    }

    /**
     * 泛型数组Comb Sort
     */
    public static <T extends Comparable<T>> void combSort(T[] arr, boolean ascending, double shrinkFactor) {
        if (arr == null || arr.length < 2) return;
        int n = arr.length;
        int gap = n;
        boolean swapped = true;
        while (gap > 1 || swapped) {
            gap = (int) Math.floor(gap / shrinkFactor);
            if (gap < 1) gap = 1;
            swapped = false;
            for (int i = 0; i + gap < n; i++) {
                if (ascending ? arr[i].compareTo(arr[i + gap]) > 0 : arr[i].compareTo(arr[i + gap]) < 0) {
                    T tmp = arr[i]; arr[i] = arr[i + gap]; arr[i + gap] = tmp;
                    swapped = true;
                }
            }
        }
    }

    public static <T extends Comparable<T>> void combSort(T[] arr, boolean ascending) {
        combSort(arr, ascending, DEFAULT_SHRINK);
    }

    // 测试示例
    public static void main(String[] args) {
        int[] data = {5, 3, 8, 4, 2, 7, 1};
        System.out.println("原始：" + Arrays.toString(data));
        combSort(data, true);
        System.out.println("升序：" + Arrays.toString(data));
        combSort(data, false);
        System.out.println("降序：" + Arrays.toString(data));

        String[] strs = {"d","b","a","c"};
        System.out.println("原始字符串：" + Arrays.toString(strs));
        combSort(strs, true);
        System.out.println("排序后：" + Arrays.toString(strs));
    }
}

【六、代码详细解读】

• 初始gap=n，每轮按shrinkFactor缩小间距，并确保最小为1；

• 当gap>1或swapped仍为true时继续比较交换；

• 升降序通过比较符号切换；

• 泛型版本逻辑与整型版一致，使用compareTo进行比较。

【七、项目详细总结】

Comb Sort通过引入动态间距减少大跨度元素移动时间，显著改进了冒泡排序在小值或大值“龟速”移动时的性能。算法简单、原地且常数开销低，适用于中小规模数据排序，以及对性能要求不高但实现成本敏感的场景。

【八、项目常见问题及解答】

1. 问：为什么使用shrinkFactor=1.3？
   答：实践中1.3被证明能在速度与稳定性间取得较好平衡；

2. 问：Comb Sort是否稳定？
   答：算法不保证稳定性，相邻跨gap交换可能改变相等元素顺序；

3. 问：如何选择最佳shrinkFactor？
   答：可通过实验在目标数据集上调整，一般在1.2~1.5之间最优。

【九、扩展方向与性能优化】

1. 双向Comb Sort：在每轮同时从两端执行缩小间距比较，结合奇偶轮思想；

2. 并行Gap比较：使用多线程对不同起始点的间距比较交换并行处理；

3. 混合排序：对小gap值切换到插入排序或冒泡排序以降低常数；

4. 自适应因子调整：根据交换频率动态调整shrinkFactor；

5. 可视化演示：展示gap变化与元素移动过程，辅助教学。