1. 简介
梳排序（Comb Sort）是由波兰计算机专家 Włodzimierz Dobosiewicz 于 1980 年在华沙大学提出的排序算法。我们知道，冒泡排序（Bubble Sort）是一种效率较低的排序算法，其最坏情况下的时间复杂度为 O(n²)。梳排序正是在冒泡排序的基础上进行改进的，类似于希尔排序（Shell Sort）对插入排序（Insertion Sort）的优化。
在本教程中，我们将学习梳排序如何改进冒泡排序，并理解它为何又被称为“带间隔的冒泡排序”。
2. 冒泡排序回顾
冒泡排序是一种基于比较的排序算法，它的基本思想是将较大的元素“冒泡”到数组末尾。我们通过多次遍历数组完成排序，每次遍历中比较相邻元素，如果顺序错误就交换它们。
以下是冒泡排序的伪代码：
algorithm BubbleSort(A):
// INPUT
// A = the reference to the shuffled array
// OUTPUT
// The sorted array A with all its elements in increasing order
i <- 0
// Perform n passes of the array
for i <- 0 to N - 1:
isSwapped <- false
// Look at the subarray A[0 : N-i-1]
// Step through the input array element by element
for j <- 1 to N - i - 1:
// Compare each element with its neighbor, swapping values if necessary
if A[j - 1] > A[j]:
temp <- A[j - 1]
A[j - 1] <- A[j]
A[j] <- temp
isSwapped <- true
if not isSwapped:
break
return A
如果某一轮遍历没有发生任何交换，说明数组已经有序，可以提前终止。
2.1. 兔子与乌龟
考虑一个无序数组：A = [9, 3, 4, 0, 8, 7, 6, 5, 1, 2]，我们观察冒泡排序每轮迭代后的数组状态：
Iteration | Array
----------|-------------------------------------
0 | [9, 3, 4, 0, 8, 7, 6, 5, 1, 2]
1 | [3, 4, 0, 8, 7, 6, 5, 1, 2, 9]
2 | [3, 0, 4, 7, 6, 5, 1, 2, 8, 9]
3 | [0, 3, 4, 6, 5, 1, 2, 7, 8, 9]
4 | [0, 3, 4, 5, 1, 2, 6, 7, 8, 9]
5 | [0, 3, 4, 1, 2, 5, 6, 7, 8, 9]
6 | [0, 3, 1, 2, 4, 5, 6, 7, 8, 9]
7 | [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
其中元素 9 被称为“兔子”，它很快被移动到末尾；而元素 1 被称为“乌龟”，它每次只能向前移动一步。这正是冒泡排序效率低下的主要原因。
3. 梳排序算法
梳排序的核心思想是：先对相距较远的元素进行比较和交换，逐步缩小这个距离（gap），从而减少“乌龟”的影响，提高排序效率。
3.1. 基础梳排序
梳排序使用一个“gap”序列来决定每次比较的元素间隔。初始 gap 为数组长度，然后每次按比例缩小（通常为 1.3），直到 gap 为 1，此时算法退化为冒泡排序。
例如，对于长度为 16 的数组，若 shrink factor 为 1.3，则 gap 序列为：12, 9, 6, 4, 3, 2, 1。
研究表明，1.3 是最优的缩小因子，可以有效平衡效率与实现复杂度。
3.2. 伪代码
以下是梳排序的伪代码实现：
algorithm CombSort(A):
// INPUT
// A = the shuffled array
// OUTPUT
// The sorted array with all its elements in increasing order
gap <- length(A)
isSwapped <- true
// Keep iterating and stop if and only if the gap equals 1 and the array is fully sorted
while gap != 1 or isSwapped:
isSwapped <- false
gap <- floor(gap / 1.3)
if gap < 1:
gap <- 1
// Look at the subarray A[0 : N-gap-1]
for i <- 0 to N - gap - 1:
// Compare each pair of elements separated by a gap, swapping values if necessary
if A[i] > A[i + gap]:
temp <- A[i]
A[i] <- A[i + gap]
A[i + gap] <- temp
isSwapped <- true
return A
该算法的外层循环会持续运行，直到 gap 为 1 且没有发生任何交换操作。此时数组已经有序。
4. 梳排序的时间复杂度
梳排序的时间复杂度仍然是 O(n²)，但在实际应用中比冒泡排序快很多。以下是梳排序与冒泡排序在不同数据规模下的性能对比：
| n | 梳排序耗时（ms） | 冒泡排序耗时（ms） |
|---|---|---|
| 10 | 0.0045960 | 0.00151599 |
| 100 | 0.077594 | 0.023565999 |
| 1000 | 1.606186 | 1.7639360 |
| 10000 | 24.872394 | 178.3646059 |
| 100000 | 327.263792 | 18536.333664 |
| 1000000 | 4079.795338 | - |
可以看到，随着数据量增大，梳排序的性能优势越来越明显。
5. Python 实现
下面是使用 Python 实现梳排序的完整代码：
def comb_sort(arr):
gap = len(arr)
is_swapped = True
while gap != 1 or is_swapped:
is_swapped = False
gap = int(gap / 1.3)
if gap <= 1:
gap = 1
for i in range(0, len(arr) - gap):
if arr[i] > arr[i + gap]:
arr[i], arr[i + gap] = arr[i + gap], arr[i]
is_swapped = True
# 示例用法
arr = [8, 4, 1, 56, 3, -44, 23, -6, 28, 0]
comb_sort(arr)
print("Sorted array:", arr)
该实现遵循了伪代码逻辑，使用了 1.3 作为缩小因子，并在每次迭代中调整 gap 值，直到数组完全有序。
✅ 该算法原地排序
✅ 无需额外空间
⚠️ 不稳定排序算法（相同元素可能交换位置）
❌ 时间复杂度仍为 O(n²)，不适用于大规模数据排序
6. 总结
梳排序是对冒泡排序的一种有效改进，通过引入 gap 概念，使得排序过程能够快速消除“乌龟”现象，从而显著提升性能。虽然其最坏时间复杂度仍为 O(n²)，但在实际测试中，其效率远高于冒泡排序。
✅ 优点：
- 实现简单
- 性能优于冒泡排序
- 原地排序，空间复杂度低
❌ 缺点：
- 时间复杂度仍为 O(n²)
- 不如快速排序、归并排序等算法高效
如果你需要一个简单、轻量级的排序方法，而又不希望像冒泡排序那样慢，那么梳排序是一个不错的选择。