排序算法之：梳排序（Comb Sort）的增量序列优化与性能分析

题目描述
梳排序是冒泡排序的一种改进算法，通过引入“间隔因子”（通常取1.3）动态调整比较间距，逐步消除数组末端的“乌龟”值（小值位于末尾导致多次交换的问题）。要求实现梳排序，并分析不同增量序列（如原始1.3因子、素数序列等）对性能的影响。

解题过程

步骤1：理解基础梳排序原理

• 梳排序的核心思想是模拟梳子齿的间距，从较大间隔开始比较交换，逐步缩小间隔至1（此时退化为冒泡排序）。
• 初始间隔设为数组长度除以收缩因子（常用1.3），每轮迭代后间隔按同一因子缩小，并向下取整。
• 例如：数组长度n=10，初始间隔=10/1.3≈7，后续间隔依次为7/1.3≈5、5/1.3≈3、...、1。

步骤2：实现基础版本（固定收缩因子1.3）

1. 初始化间隔gap = n。
2. 循环直到gap=1：
   • 计算新间隔：gap = max(1, floor(gap / 1.3))。
   • 从索引0开始，比较元素arr[i]和arr[i+gap]，若逆序则交换。
3. 当gap=1时，执行最后一轮冒泡排序确保完全有序。

示例代码（固定因子1.3）：

def comb_sort(arr):
    n = len(arr)
    gap = n
    swapped = True
    
    while gap > 1 or swapped:
        gap = max(1, int(gap / 1.3))  # 动态缩小间隔
        swapped = False
        for i in range(n - gap):
            if arr[i] > arr[i + gap]:
                arr[i], arr[i + gap] = arr[i + gap], arr[i]
                swapped = True  # 标记发生交换

步骤3：分析收缩因子的影响

• 因子1.3的合理性：经验表明，1.3能有效减少间隔缩小的轮数，避免间隔序列过于密集（如2的幂）或稀疏（如线性递减）。
• 问题：固定因子可能导致间隔重复（如gap=4和gap=3均缩小到3），降低效率。

步骤4：优化增量序列

1. 素数间隔序列：使用素数作为间隔（如原始论文建议），避免公约数导致的重复比较。
   • 生成小于n的素数序列作为间隔，从最大素数开始。
   • 优点：减少重复比较；缺点：计算素数增加开销。
2. 动态因子调整：根据剩余待排序子数组的特征自适应调整因子（如接近有序时减小因子）。

示例优化（素数间隔）：

def generate_primes(n):
    # 生成小于n的素数列表（略去实现）
    primes = [2, 3, 5, 7, ...]  # 示例序列
    return [p for p in primes if p <= n]

def comb_sort_optimized(arr):
    n = len(arr)
    primes = generate_primes(n)
    gap_index = len(primes) - 1  # 从最大素数开始
    swapped = True
    
    while gap_index >= 0 or swapped:
        gap = primes[gap_index] if gap_index >= 0 else 1
        swapped = False
        for i in range(n - gap):
            if arr[i] > arr[i + gap]:
                arr[i], arr[i + gap] = arr[i + gap], arr[i]
                swapped = True
        gap_index -= 1  # 移至更小的素数

步骤5：性能对比与边界处理

• 时间复杂度：平均O(n²)，但优化后接近O(n log n)。最佳情况（已排序数组）为O(n)。
• 空间复杂度：O(1)原地排序。
• 边界案例：
  • 空数组或单元素数组直接返回。
  • 间隔缩小至1时需确保终止条件（结合swapped标志）。

总结
梳排序通过动态间隔平衡了冒泡排序的简单性和高效性。优化增量序列可进一步提升性能，但需权衡计算开销。实际应用中，若输入规模不大，固定因子1.3的版本已足够高效。