前一段时间我在技术论坛上刷到一个帖子标题大概是“我写了一个循环排序时间复杂度 O(n log n)比快排还稳。”评论区很快吵起来。有人直接说循环排序不是 O(n^2) 吗也有人贴出 LeetCode 上的循环排序解法说那明明是 O(n)。还有人分析半天最后发现大家说的“循环排序”压根不是同一个算法。我当时的第一反应是又一个把“复杂度”挂在嘴边、但没看清定义的人。可等我认真看完楼主贴出的代码和后面的讨论发现事情没那么简单。这个争议恰好暴露了算法分析里最容易被忽略的一个问题当我们说一个排序算法的时间复杂度是 O(n log n) 时到底在数什么操作是元素比较次数是数组写入次数还是 CPU 上的墙钟时间这篇文章就借“循环排序”这个案例把这笔账算清楚。顺便也会给出一个判断循环排序复杂度、验证复杂度结论的可执行路径。标题里那句“结果发现时间复杂度为 O(n log n)”我会拆开讲它可能对也可能只是说了一半。1. 先厘清循环排序到底在排什么1.1 两种都叫“循环排序”的算法网上搜“循环排序”至少能看到两种完全不同的东西。第一种是 LeetCode 里经常出现的 Cyclic Sort中文常译作“循环排序”。它解决的问题很特殊给你一个长度为 n 的数组里面是 1 到 n 的整数让你原地排序。思路非常简单每个元素都对应一个“正确索引”值等于索引加一。如果当前元素不在正确位置就把它换过去换过来的元素如果也不对就继续换直到当前位置正确。这个算法的时间复杂度是 O(n)空间复杂度 O(1)。第二种是 Wiki 上收录的 Cycle Sort中文同样被译作“循环排序”或“圈排序”。它适用于任意可比较元素的数组核心思想是遍历数组时把每个元素放到它最终应该在的位置但不会像选择排序那样每次交换两个元素而是沿着一个“环”做旋转尽可能少写入。这两种算法都叫循环排序但前提、流程、复杂度完全不同。论坛帖子的争论很大程度就是从这里开始的。1.2 核心思想把数组看成若干个环想理解循环排序先理解“环”这个比喻。假设有一个数组[3, 1, 2]我们给每个元素标上它“最终应该去的位置”。值3在排序后应该去索引2值1应该去索引0值2应该去索引1。如果你把这些映射关系连起来会得到一个环索引0 - 索引2 - 索引1 - 索引0。Cycle Sort 的做法是先选定一个起点位置然后不断把合适元素搬进来再把被挤出去的元素送到它该去的下一个位置直到回到起点。一个包含 k 个元素的环只需要 k1 次写入就能把整个环里所有元素放到正确位置。如果你画过排序算法的流程图会发现循环排序的流程图里最显眼的就是这个环。这也是它名字的由来。1.3 能减少写入但代价是查找为什么明明可以用选择排序解决还要绕环旋转因为选择排序每次交换都要赋两次值很多情况下这些“写入”是不必要的。Cycle Sort 刻意把写入次数压到理论最低最坏情况下一个 n 元素的数组写入次数约为 2n 次。但省写入是有代价的。为了知道某个元素应去哪个位置你需要比较它和后面所有元素的大小从而数出“到底有几个元素比它小”。这是一个线性扫描的过程。标准 Cycle Sort 里每个位置都要扫描一遍剩余数组所以比较次数会达到 O(n^2)。这就为后面那个“O(n log n)”的争议埋下了伏笔写入次数是 O(n)比较次数是 O(n^2)那这个算法的“时间复杂度”到底该算哪个2. 为什么有人会说循环排序的时间复杂度是 O(n log n)2.1 误读一把循环排序当成快速排序家族先排除一种最不值得争的情况。很多初学者看到“循环”两个字会下意识觉得它和“递归”、“分治”有关系然后联想到快速排序、归并排序的平均 O(n log n)。但实际上标准 Cycle Sort 并没有分治结构它更像是选择排序的变体。选择排序无论最好最坏比较次数都是 O(n^2)。Cycle Sort 在比较层面也一样不会因为名字里有“循环”就自动变成 O(n log n)。如果一个人只是说“循环排序是 O(n log n)”没有任何实现细节那这个结论大概率站不住脚。2.2 误读二只统计比较次数忽略写入和移动真正的争议出现在有人给了具体实现之后。论坛里的有些实现看起来确实更像“二分插入排序”假设数组的前半部分已经有序每次拿一个新的元素用二分查找找到它应该插入的位置然后把一段元素循环移动最后把新元素放到正确位置。这个思路里比较次数很好算。每插入一个元素二分查找需要 O(log n) 次比较插入 n 个元素总比较次数是 O(n log n)。如果你只在代码里数“比较了多少次”最终统计结果确实会呈现 n log n 的增长趋势。问题出在“写入”和“移动”上。在普通数组里做循环插入意味着插入位置后面的所有元素都要挪一位。每次插入最坏要移动 O(n) 个元素n 次插入之后移动次数是 O(n^2)。如果你把比较、写入、移动、循环变量更新全部算进“总操作数”这个算法并没有跑到 O(n log n)。所以“循环排序的时间复杂度是 O(n log n)”这个说法只有在一种特定口径下才成立只统计比较次数并且使用二分查找来定位插入点。一旦把数组写入和元素移动算进来它依然是 O(n^2)或者说至少不能简单地说它是 O(n log n)。2.3 如果要求严格O(n log n) 的说法成立吗现在可以给出一个更严谨的判断了。标准 Cycle Sort比较 O(n^2)写入 O(n)。如果你把所有操作合起来看时间复杂度可以写成 O(n^2)。基于二分插入的循环排序变体比较 O(n log n)但数组移动仍然 O(n^2)。严格说总时间复杂度还是 O(n^2)。如果额外使用链表、块状数组或平衡树来避免大规模移动移动量可以优化但空间复杂度会上升而且它已经不是经典意义上的“原地循环排序”了。标题里说的“结果发现它的时间复杂度为 O(n log n)”更准确的理解是这个实现里的元素比较次数达到了 O(n log n)。它没有打破比较排序 O(n log n) 的下界也没有超过快速排序只是把复杂度统计里最显眼的那一块优化掉了。3. 手写一个循环排序并验证复杂度3.1 标准 Cycle Sort先把流程跑通下面给出一个标准 Cycle Sort 的 Python 实现。这段代码的用途是演示流程而不是性能最优。它会在数组原地上操作并返回总写入次数。def cycle_sort(arr): writes 0 n len(arr) for start in range(n - 1): item arr[start] # 找出 item 最终应该在的位置 pos start for i in range(start 1, n): if arr[i] item: pos 1 # 如果 item 已经在正确位置跳过 if pos start: continue # 跳过重复元素 while item arr[pos]: pos 1 # 把 item 放进去并取出被替换的元素 arr[pos], item item, arr[pos] writes 1 # 继续处理被挤出来的元素直到回到起点 while pos ! start: pos start for i in range(start 1, n): if arr[i] item: pos 1 while item arr[pos]: pos 1 arr[pos], item item, arr[pos] writes 1 return writes这段代码最内层的循环是“扫描start1到n-1的元素统计小于item的数量”。不管输入是什么这个扫描都会执行。所以比较次数非常稳定地落在 O(n^2)。3.2 Cyclic Sort值域受限时的 O(n) 版本如果你遇到的是[1, n]排列这种特殊输入事情会简单很多。下面的版本才是刷题常见的“循环排序”def cyclic_sort(nums): i 0 while i len(nums): correct_index nums[i] - 1 if nums[i] ! nums[correct_index]: nums[i], nums[correct_index] nums[correct_index], nums[i] else: i 1 return nums这个版本为什么能到 O(n)因为每个元素最多被交换一次。它利用的是“值本身等于目标位置索引”这个强约束而不是通用比较排序。如果你把这段代码也叫做循环排序那它的复杂度确实是 O(n)。这也是社区里最经典的认知冲突两个人都在说循环排序一个人说的是通用 Cycle Sort一个人说的是值域受限的 Cyclic Sort复杂度结论自然对不上。3.3 用计数器验证比较次数复杂度分析不能只靠直觉尤其是遇到“看起来是 O(n log n)”的争议时最好的办法是直接打点统计。一个简单的思路用一个包装类记录数组比较次数。import random class CountingList: def __init__(self, data): self.data data self.cmp_count 0 def __len__(self): return len(self.data) def __lt__(self, other): self.cmp_count 1 return self.data other.data然后分别对 n100、200、400、800 的随机数组运行标准 Cycle Sort记录比较次数。你会看到这样的趋势n 翻一倍比较次数大约翻四倍。这正是 O(n^2) 的特征。如果哪个变体在同样的 n 翻倍测试下比较次数只翻两倍多一些那它比较这一项才接近 O(n log n)。建议在验证时把 n 取到 2000 以上不然随机抖动会掩盖增长趋势。同时尽量多跑几轮取平均避免刚好遇到特殊顺序。3.4 二分优化版写一个能到 O(n log n) 比较的变体如果你真想和论坛帖子里的人一样把比较次数降到 O(n log n)思路可以改成这样1. 假设arr[0:start]已经有序。 2. 用二分查找在arr[0:start]中找到arr[start]应该插入的位置pos。 3. 把arr[pos:start1]循环右移一位让arr[start]落到arr[pos]。 4. start 1重复。这个步骤很像“二分插入排序”但它确实用到了循环移动所以有人把它也叫作“循环排序”。比较次数可以从 O(n^2) 降到 O(n log n)但数组移动次数依然是 O(n^2)。如果面试官问“这个排序最坏时间复杂度是多少”你需要回答 O(n^2)因为比较不是唯一开销。如果你用链表或块状数组来避免大段移动那写入和移动也可以优化但空间复杂度会从 O(1) 变成 O(n)这已经跳出循环排序原本的适用范围了。4. 循环排序真正适合的场景以及容易踩的坑4.1 什么时候该用循环排序循环排序最核心的价值不是快而是“少写”。所以以下场景值得优先考虑写入代价极高比如某些嵌入式 Flash 存储、EEPROM 磨损均衡场景每次写操作都有寿命损耗。循环排序能把写入次数压到理论最低哪怕比较次数多一点也可以接受。数组元素是很大的对象交换代价很高如果数组里存的是巨型结构体每次交换都要拷贝整个对象那么减少交换/写入次数往往比减少比较次数更划算。输入是 1 到 n 的排列这时用 Cyclic Sort本身就是 O(n)可以直接找缺失值、重复值是最好用的原地算法。在普通业务代码里如果你要排序一个 100 万元素的普通数组循环排序大概率不是首选。因为现代 CPU 上比较和访问的代价远比你以为的低而快速排序或内置排序已经在缓存、分支预测、并行度上优化到极限。4.2 什么时候别用循环排序需要明确写出边界避免读者把“少写”理解为“全场景最优”大规模随机数据排序标准 Cycle Sort 比较 O(n^2)即使比较开销不低在 n 大时也会明显变慢。要求稳定排序Cycle Sort 是不稳定的。如果数组里有大量相同键值的元素排序后它们的相对顺序不保证。重复元素很多虽然标准实现里跳过了重复元素但重复元素会让定位逻辑变复杂最坏情况下比较次数不会变少移动次数却可能增加。不需要原地排序、内存充裕归并排序稳定且 O(n log n)更实用。4.3 排查判断一个陌生排序算法复杂度的三问框架以后再看到有人说“某某排序是 O(n log n)”可以用下面这个框架快速判断核心操作是什么是元素比较是交换是写入是把某个元素挪到临时变量再放回去不同操作对应的复杂度可能完全不同。最坏输入是什么对普通排序算法最坏情况可能是逆序、顺序、大量重复元素。对循环排序类最坏情况通常和“需要形成多少个环”以及“每次定位要扫描多少元素”有关。复杂度口径是什么是说比较次数是说写入次数还是说包含了赋值、循环、函数调用的总运行时间讨论复杂度时先统一口径再谈结论。4.4 落地建议先跑通、再压测、后优化如果你想在一个真实项目里尝试循环排序我建议按这个顺序执行先用一个小数组跑通确认排序结果正确写入次数符合预期。再用边界测试空数组、单元素、逆序、大量重复元素、已排序数组。循环排序很容易在重复元素处理上出 bug尤其是跳过重复值的逻辑。最后做增长曲线验证取 n1000、2000、4000、8000分别记录排序耗时或核心操作次数。如果耗时增长速度接近 n^2那就说明当前实现对性能并不友好不适合无脑推广到生产环境。如果只是刷题或学习写一个标准 Cycle Sort 练手没问题。但真的进入生产代码之前多数时候直接调用标准库里的排序函数比自己造轮子更可靠。这不是否定循环排序而是知道它的价值到底在哪。回到那个论坛帖子楼主没有完全说错他只是没说完整。循环排序的“比较次数”确实可以做到 O(n log n)但当他把“比较次数”包装成“时间复杂度”时这就成了一个很容易误导人的表达。一次看似激烈的算法争论最后能留下的不是谁对谁错而是一个更底层的问题意识当人们谈论复杂度时他们到底在计量什么在省略什么又在为哪个场景做取舍。如果下次再看到类似标题我建议你先别急着站队。认真问一句“这里的 O(n log n)是在数比较还是在数写入还是在数墙钟时间”也许这比争论本身更有价值。