梳状排序：用1.3因子优化冒泡排序的高效算法

你大概已经知道冒泡排序在数据量稍微上来一点之后就会变得非常难堪。课堂上老师还在讲它的代码只有几行可你一旦拿它去排几千条数据就能清楚感受到什么叫“等得怀疑人生”。但你见过一个叫梳状排序Comb Sort的算法吗它没有引入分治、堆、递归这些复杂概念只靠一个数字——1.3——就让冒泡排序从“几乎没救”变成“还能再抢救一下”。这个数字看起来像是随手拍出来的背后却藏着一种很典型的算法改进思维先大步跨越再小步微调。读完这篇文章你不仅会写梳状排序还会理解它为什么能把冒泡的短板补上一块以及它到底适合在什么场景下用、在什么场景下应该果断放弃。1. 为什么冒泡排序最大的问题不只是“慢”1.1 冒泡排序的时间复杂度不是全部问题很多人印象里冒泡排序的缺点就是“慢”时间复杂度是 O(n²)。这个结论没有错但只是表面。同样是 O(n²) 的排序算法插入排序在数组接近有序时能跑得飞快选择排序的交换次数很少而冒泡排序的情况要更尴尬一些它对“逆序距离很大”的数据特别不友好。举个例子假设有一个数组最大元素在最前面这个元素会在第一趟冒泡中被一路交换到末尾因为它“足够大”能轻松地往右移动。可如果最小元素在末尾情况就完全不同了。每一轮冒泡它只能往左移动一个位置。如果数组有 10000 个元素最坏情况下这个小元素要经过 9999 轮比较交换才能到达正确位置。这种单步挪动才是冒泡排序最致命的地方。所以冒泡排序慢不仅是因为 O(n²)更是因为它把大量时间花在了“把隔得很远的逆序对逐步拉近”上。每一步都只处理相邻元素导致一个小元素需要跨越很多步才能回到自己的位置。这个问题不解决写再多优化分支也改变不了底层缺陷。1.2 乌龟与兔子冒泡排序的低效根源算法书里经常用“乌龟”和“兔子”来形容冒泡排序中的两类元素。大的元素像兔子一趟就能往末尾跳好远小的元素像乌龟只能一步一步向前爬。这个比喻很形象也点出了问题的本质冒泡排序的交换粒度太小了。如果我们站在更高的视角看任何排序算法的目的都在于消除逆序对。冒泡排序每次只消除相邻的逆序对效率自然低。插入排序实际上也是相邻移动但它在基本有序的数据上有很强的自适应能力。选择排序虽然也是 O(n²)但它每轮只做一次交换不会像冒泡那样频繁交换。所以冒泡排序在教学上价值很高但在实际使用中它往往是最不值得优先选择的 O(n²) 算法。梳状排序的想法就是从这里开始的既然问题出在“每次只能交换相邻元素”那我把交换的距离拉大先让元素跨大步走再慢慢缩小距离不就能让“乌龟”也变成“兔子”了吗这个思路和希尔排序对插入排序的改进很像只不过梳状排序直接作用在冒泡排序的框架上改造起来非常轻量。2. 梳状排序如何用一个数字改变交换策略2.1 跨过相邻交换先“粗梳”再“细梳”梳状排序的核心思想很容易理解先让数组里距离较远的元素进行比较和交换然后逐步缩短这个距离直到距离变成 1再做一次标准冒泡。这个过程就像用梳子梳头一开始梳齿间距很大可以快速理顺大范围的乱发然后不断缩小梳齿间距处理更细小的纠缠最后间距为 1把每一根头发都理顺。这个“距离”在算法里叫间隔gap也叫增量。初始间隔通常设为数组长度 n。每完成一趟比较交换间隔就按照某个规则缩小最终变成 1。当间隔大于 1 时算法处理的是远距离逆序对当间隔等于 1 时算法就退化成冒泡排序。这样做的好处是原本需要很多次相邻交换才能移动到位的小元素可以在间隔较大时一次性向前跳过多个位置。比如一个很小的元素在数组末尾如果当前间隔是 500那它一次比较交换就能往前跳 500 个位置。这个跨越能力是标准冒泡给不了的。2.2 1.3 这个神秘数字的来历与直觉你可能会问间隔每次缩小多少为什么偏偏是 1.3在常见的算法资料中梳状排序由 Stephen Lacey 和 Richard Box 在 1991 年重新引入并推广他们通过实验发现取 1.3 作为收缩因子时排序效率很好。这个数字并不是严格的数学最优解更像是一个在大量随机数据上测试后得到的经验值。理论上收缩因子越小间隔序列衰减越慢需要的趟数越多收缩因子越大间隔序列衰减越快可能快速进入相邻比较阶段却又退化成了冒泡排序。从直觉上可以这样理解如果收缩因子是 1.1间隔从 1000 缩到 1 大约需要 72 趟很慢如果收缩因子是 2.0间隔从 1000 缩到 1 只需要 10 趟太快了远距离快速整理的效果打折扣。1.3 的收敛速度刚刚好既能保持足够多的远距离比较趟数又不会拖泥带水。实际使用中如果你改成 1.25 或 1.2通常也会得到可接受的结果但比较次数往往会变多如果你改成 1.4 或 1.5算法会更快进入相邻比较阶段整体效果不一定变差但也很难超过 1.3。2.3 间隔序列从 n 到 1 的收缩过程梳状排序的完整过程可以这样描述初始间隔 gap 等于数组长度 n。在每一轮扫描中比较相距 gap 的两个元素如果顺序不对就交换。结束后把 gap 更新为 max(1, int(gap / 1.3)) 或者“当 gap 大于 1 时才更新”直到 gap 降到 1。当 gap 等于 1 时算法退化成冒泡排序。这里要注意一个细节标准冒泡排序在没有发生交换时可以提前终止。梳状排序也一样即使 gap 已经等于 1如果这趟扫描仍发生了交换说明数组还没排好序还需要继续执行相邻比较扫描。所以循环不能只看 gap 是否大于 1还要记录“是否有交换”。如果某趟 gap1 的扫描结束后没有任何交换就可以确定数组已经有序。这也是梳状排序实现里最容易出错的地方。很多初学版本只写了while (gap 1)最后在 gap1 时只做一遍比较交换就退出了结果数组未必有序。正确写法必须加上交换标记作为循环条件之一。3. 手写一个可用的梳状排序代码与关键细节3.1 C语言最小实现下面是一份可以直接运行的 C 语言梳状排序实现。为了体现最原始的版本我用整型数组和经典交换逻辑写#include stdio.h void comb_sort(int arr[], int n) { double shrink 1.3; int gap n; int swapped 1; while (gap 1 || swapped) { if (gap 1) { gap (int)(gap / shrink); } swapped 0; 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 1; } } } } int main() { int arr[] {9, 5, 1, 4, 3, 8, 2, 6, 7}; int n sizeof(arr) / sizeof(arr[0]); comb_sort(arr, n); for (int i 0; i n; i) { printf(%d , arr[i]); } return 0; }这段代码里while (gap 1 || swapped)是关键。当 gap 大于 1 时先缩小间隔再进行比较交换。当 gap 等于 1 时gap 1为假只有swapped为真时循环才会继续也就是继续做相邻比较直到某趟完全没有交换才结束。3.2 Python版本与循环条件如果你平时用 Python 写算法可以看这个版本def comb_sort(arr): n len(arr) gap n shrink 1.3 swapped True while gap 1 or swapped: if gap 1: gap max(1, int(gap / shrink)) 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 arr [9, 5, 1, 4, 3, 8, 2, 6, 7] comb_sort(arr) print(arr)这里为了保险在更新 gap 时用了max(1, int(gap / shrink))。如果不在 C 语言版本里做这个保护就必须用if (gap 1)的判断避免 gap 变成 0。两种方式都能保证 gap 最小为 1。3.3 验证输出与对比基准写完排序后不要只打印一遍结果就认为正确。更稳妥的验证是随机生成一个数组。用你实现的梳状排序排序。用标准库排序得到参考结果。用循环检查结果是否严格非递减。重复多组随机数据检查边界情况空数组、单元素数组、全部相同元素、完全逆序数组、完全有序数组。在这个验证过程中你可能会发现一个常见问题如果循环条件漏了swapped完全有序的数组可能没问题因为某趟没有交换就会提前结束但完全逆序的数组很可能在 gap1 只跑一遍就不管了导致结果排序不完整。这正好说明验证不能只看一组数据。如果要做性能对比我一般会生成不同长度的随机数组比如 1000、5000、10000分别记录冒泡排序和梳状排序的比较次数或运行耗时。注意在不同的编译器和运行环境下结果差异可能很大。更重要的是不要只测一次就下结论最好多测几轮取中位数。梳状排序在小数据量下优势不明显甚至在 n 小于 100 时可能和冒泡排序差不多数据量越大优势越明显。4. 复杂度、实测与1.3的适用范围4.1 理论复杂度最好、最坏和平均情况从理论上看梳状排序最坏时间复杂度仍然是 O(n²)。因为当间隔不断收缩到 1 之后算法本质上还是要做一轮可能很长的冒泡过程。但平均情况要比冒泡好得多。由于大跨度比较会快速消除远端逆序对实际运行中常用间隔序列的效果接近 O(n log n)但这个结论依赖间隔序列的选取。最好情况通常被认为是 O(n log n)因为当数组已经有序时第一轮 gapn 的比较不会发生交换但算法还要继续缩小 gap 并扫描。有些优化版本会利用交换标记提前退出但严格的分析并不容易统一。很多人直接说梳状排序的平均复杂度是 O(n²/2^p)p 表示增量数这只是一类近似表达工程上更关心的是它“在随机数据上比冒泡快很多但不一定能赶超快速排序”。不要把“接近 O(n log n)”误解成“和快排一样快”。快排、归并、堆排序都有非常成熟的工程实现梳状排序的优势不是理论复杂度而是实现简单、代码量小、不需要额外空间。在数据量不大的场景下这种简单本身就是竞争力。4.2 在中小规模数据上的实际观察我自己的体感是当数组规模在几百到几千这个区间时梳状排序的改进非常明显。比如数组长度 5000冒泡排序往往已经让人明显感觉到卡顿而梳状排序给人的感觉是“工序多但并不笨重”。这背后主要是逆序对被更快消除了。如果拿梳状排序和快速排序去比在随机数据上快速排序通常更快尤其在大数据量时。但快排有递归调用有退化风险还要考虑基准值选择梳状排序没有递归也没有栈开销。对于“不想写复杂排序、但希望比冒泡好用”的场景梳状排序是个很顺手的选择。需要强调的是这些观察都是基于常见随机数据分布。如果你的数据本身已经基本有序插入排序反而会更快如果你的数据包含大量重复值三路快排或计数类排序会更合适。不要指望一个算法在所有输入上都赢。4.3 何时该警惕梳状排序退化梳状排序最容易被诟病的地方是它不能保证稳定而且最坏情况仍然是 O(n²)。有一种观点认为如果遇到精心构造的“最差间隔序列”梳状排序甚至会退化回冒泡。虽然实际比赛中很少见但在工程中我们不能忽略这种可能性。另一个容易忽略的问题是非随机数据。比如数组里所有较小元素都集中在后部或者数据已经接近有序但存在少量逆序对梳状排序的间隔序列可能无法及时发挥优势。此时直接调用标准库排序或者选择插入排序可能是更好的选择。还有一点梳状排序不是稳定排序。如果待排序对象是一个结构体数组并且你希望相等键值的元素保持原有先后顺序那梳状排序并不合适。稳定性这个属性经常被初学者忽略但在数据库查询、多关键字排序场景中非常重要。5. 给梳状排序“打补丁”的常见做法5.1 提前终止和交换标记前面提到的swapped标记本质上就是一个补丁。它让算法在数组已经有序时不会继续做无意义扫描。这个优化成本极低但收益明显。尤其是在接近有序的数据集上没有这个标记的梳状排序可能还要跑完间隔序列然后做多轮相邻比较有了标记可能在 gap 还比较大时就提前结束了。实现时要注意当 gap 大于 1 时即使某趟没有发生交换也不能立刻退出循环因为大间隔情况下没有交换并不代表整体有序。只有 gap1 且没有交换时才可以确定排序完成。所以最稳妥的条件仍然是while (gap 1 || swapped)。5.2 混合排序与插入排序结合梳状排序的后期阶段也就是 gap 比较小的时候数组已经变得“基本有序”。这个时候再继续做冒泡式的相邻比较虽然能完成排序但不如插入排序高效。插入排序在基本有序的序列上表现很好所以一个常见的优化思路是当 gap 缩小到某个阈值比如 10 或 20改用插入排序完成剩余工作。这个思路和很多排序算法的工程优化一脉相承先用不稳定的、大跨度的方式让数组大致有序再用稳定的、擅长处理近有序数据的插入排序完成收尾。实际效果通常比纯梳状排序更好。代价是代码会多出一段插入排序逻辑但对已经理解插入排序的人来说成本并不高。5.3 更优的间隔序列比1.3更进一步的优化1.3 是经验值但不是唯一选择。有人尝试过用固定间隔序列代替gap / 1.3的收缩方式比如先按递减列表取增量nn/2.2n/2.2²……也有人研究过类似希尔排序的 Hibbard 序列、Sedgewick 序列等。对于梳状排序只要间隔能够从大跨度平滑过渡到 1排序的正确性都能得到保证区别主要在性能。如果你只是想写一个教学demo1.3 就够了。如果你想让梳状排序在特定硬件或特定数据分布下更快可以自己做实验记录不同收缩因子下的比较次数和交换次数再用统计方法选择一个更合适的值。但要注意这种调参对工程收益往往有限远不如直接选择快速排序或归并排序来得省心。6. 排序方案选择与真正的工程建议6.1 用“四步排查法”确认你的梳状排序没有问题如果你实现了梳状排序但结果不对不要急着怀疑电脑按照下面这个顺序排查看间隔更新gap 是否可能变成 0如果采用gap gap / 1.3在 gap1 时结果会是 0必须保证 gap 最小为 1。看循环条件是否包含 swapped 标记如果漏掉在 gap1 时只跑一趟就退出很可能排序不完整。看内层边界循环里使用i gap n还是i n - gap两者都可以但边界差一个元素会导致越界或漏比较。看初始状态数组长度为 0 或 1 时循环是否还能安全执行如果gap nn0 时会出现什么情况需要单独处理。大多数梳状排序报错或结果不对都逃不开这四类问题。排查时先从最简单的边界用例开始再逐步增加数据量和复杂数据分布。6.2 数据规模、稳定性、极端输入三个问题在决定是否使用梳状排序之前我建议你回答三个问题数据规模有多大如果是几百万条记录梳状排序通常不是首选直接使用qsort、std::sort或语言内置排序更可靠。是否需要稳定排序如果需要梳状排序直接出局。稳定排序选归并排序或插入排序。输入数据是否极端比如基本有序、大量重复、高度逆序、数据分布在多个桶里。每种情况都有更适合的算法梳状排序的“平均不错”不代表“全能”。工程上最容易犯的错误是在一个小规模场景里发现了梳状排序的优点然后把它推广到所有场景。正确做法是把排序算法当作工具箱根据输入特点选择。梳状排序可以放进这个工具箱但它不应该替代其他工具。6.3 梳状排序给算法学习带来的真正启发回到文章开头的问题1.3 到底救了冒泡排序吗如果“救”意味着让冒泡变成顶级排序那答案是否定的。但它确实用一个很简单的改动让冒泡排序的短板得到实质性改善先跨大步再走小步把“乌龟”变成“兔子”。这个思想在排序领域并不罕见。希尔排序这样改插入排序梳状排序这样改冒泡排序归并排序和快速排序则通过分治把问题规模一分为二。你会发现很多算法改进的本质不是发明新的扑克玩法而是改变“处理数据时允许元素一次移动多远”。你掌握了这个视角以后再学任何排序算法都能更快抓住它的骨架。如果你现在正在学习排序我的建议是先老老实实写完冒泡排序再写一个梳状排序对比两者的代码和效率。这个实验会让你对 O(n²) 和远距离交换产生更直观的理解。你不需要在每个项目里都用梳状排序但你应该理解1.3 这个数字是怎样把一个原本笨重的算法变成一个值得放在工具箱角落里的备用方案。