前几天逛技术论坛看到一个很有趣的帖子。作者发了一套号称 O(n) 的“循环排序”代码核心理由是“每个元素最多只被移动一次所以时间复杂度是 O(n)。”没想到评论区很快反转有网友逐行分析后发现这个算法根本没有 O(n)即使是优化过的版本时间复杂度也只是 O(n log n) 而已。这个案例非常适合拿来做一次排序算法复杂度复盘。本文将完整拆解循环排序的原理、代码和复杂度推导重点说清楚“O(n log n)”到底是怎么被挖出来的。1. 事件回顾论坛上一个“O(n) 排序”引发的讨论1.1 原帖声称的结论帖子的标题大概意思是作者实现了自己的循环排序并声称时间复杂度是 O(n)。整篇帖子的论证逻辑是这样的每个元素在一次排序过程中最多被交换一次。因此写入次数是 O(n)。既然是 O(n) 的写入次数整个排序算法就应该是 O(n)。从表面看这个推理似乎合理。因为很多排序算法的时间复杂度都被“交换次数”或“比较次数”主导比如冒泡排序的交换次数是 O(n^2)插入排序的移动次数是 O(n^2)。如果一个算法能把移动次数压到 O(n)那确实值得兴奋。不过评论区马上就有人问了一句“定位环节呢”1.2 评论区为什么翻车在原帖给出的循环排序实现里每个元素要被放到“它最终应该在的位置”。问题是程序怎么知道某个元素最终应该在哪个位置答案是在剩余区间里做比较统计。也就是说对于每个待处理元素都要扫描一遍它之后的元素数一数有多少元素比它小。只要数清楚了这个数量就能知道当前位置应该排在剩余元素中的第几个位置。这个扫描过程本身就是一个内部循环复杂度是 O(n)。于是整个算法变成了外层循环遍历起点O(n)。内层循环线性扫描统计“有几个元素比我小”O(n)。每一轮都要做一次这样的扫描。两者相乘时间复杂度的数量级就是 O(n^2)而不是 O(n)。1.3 复杂度结论最终变成了 O(n log n)后来有网友提出既然线性扫描太慢能不能用二分查找来优化定位如果能在一开始拿到一个有序副本那么每个元素的目标位置就可以通过二分查找得到定位成本从 O(n) 降到 O(log n)。这样理论上总复杂度可以变成 O(n log n)。听完这个建议后发布者把代码改成了“排序副本 二分查找 环交换”的版本并再次测试。结果这次分析发现构造排序副本需要 O(n log n)。每个元素做一次二分查找定位需要 O(n log n)。所有元素的移动次数才是 O(n)。所以总时间复杂度不是发布者最初说的 O(n)而是 O(n log n)。帖子标题最后也被修改成“循环排序——结果发现它的时间复杂度为 O(n log n)”。这就是整个事件的来龙去脉。接下来我们回到算法本身把循环排序的实现和复杂度彻底讲清楚。2. 循环排序原理与标准实现2.1 循环排序的思想循环排序Cycle Sort是一种原地排序算法它最大的特点是把“写入次数”控制得非常少。理论上最优情况下只需要 O(n) 次写入。它特别适合那些“元素移动代价极高”的场景例如大对象数组的排序因为减少元素拷贝就是减少开销。它的核心思想是把数组看成若干个不相交的“环”。排序的过程就是沿着这些环把每个元素送到它最终应该在的位置。举个例子索引: 0 1 2 3 值: 2 1 4 3如果按照升序排序那么元素 2 最终应该在索引 1。元素 1 最终应该在索引 0。元素 4 最终应该在索引 3。元素 3 最终应该在索引 2。这时数组可以被拆成两个环环 A索引 0 - 索引 1 - 索引 0 环 B索引 2 - 索引 3 - 索引 2循环排序要做的就是沿着这些环逐个交换元素让每个元素一次到达最终位置。2.2 标准算法步骤标准的循环排序过程如下从 start 0 开始取出当前起点元素 item。在 start 之后的区间中统计有多少个元素比 item 小记为 pos。如果 pos 等于 start说明 item 已经在自己该在的位置跳过。如果 pos 不等于 start说明 item 应该被放到索引 pos于是把 item 放到 pos取出原来 pos 位置上的元素继续重复“统计位置、交换”。当取出的元素回到 start 位置时当前这个环就处理完毕。start 后移一位继续处理下一个环直到数组尾部。这个过程不需要额外数组空间所以空间复杂度是 O(1)。2.3 标准 Python 实现下面是一份完整的标准循环排序实现代码可以直接复制运行def cycle_sort(nums): n len(nums) writes 0 for start in range(n - 1): item nums[start] pos start # 统计 start 之后有多少元素比 item 小 for i in range(start 1, n): if nums[i] item: pos 1 # 如果已经在正确位置直接进入下一轮 if pos start: continue # 如果遇到重复元素跳过相同的值 while item nums[pos]: pos 1 # 把 item 放到 pos同时取出 pos 上的原值 nums[pos], item item, nums[pos] writes 1 # 继续处理同一环上的其他元素 while pos ! start: pos start for i in range(start 1, n): if nums[i] item: pos 1 while item nums[pos]: pos 1 nums[pos], item item, nums[pos] writes 1 return nums, writes # 测试 data [5, 2, 3, 1, 4] sorted_data, writes cycle_sort(data) print(排序结果:, sorted_data) print(写入次数:, writes)这段代码里有几个关键点pos表示当前元素最终应该去的位置。while item nums[pos]是为了处理重复元素。如果不做跳过处理两个相同值可能陷入无限交换。writes记录的是写入次数也是循环排序最重要的性能指标。标准循环排序的时间复杂度是 O(n^2)。虽然它的写入次数是 O(n)但定位过程需要反复扫描整体性能并不优秀。3. 复杂度分析移动 O(n) 不等于排序 O(n)3.1 被忽略的定位环节很多初学算法的人看到循环排序的“交换次数是 O(n)”之后会下意识认为整个算法是 O(n)。这就是原帖作者翻车的地方。时间复杂度衡量的是一整套算法中所有操作的执行次数而不只是某一个你关心的操作。循环排序里有两个核心操作定位操作确定一个元素最终应该在哪个位置。交换操作把元素移动到正确位置。标准循环排序里定位是通过线性扫描完成的。为了给一个元素找到正确位置需要扫描它后面的所有元素统计出比它小的元素个数。这个步骤消耗的时间往往比交换本身大得多。如果把算法比喻成“快递分拣”交换只是把包裹扔上车而定位是查找包裹应该送到哪个小区。查地址的时间可能比搬包裹的时间还长。3.2 线性扫描定位O(n^2)标准实现中外层循环遍历 start 位置内层循环从 start 1 扫描到数组末尾。总的比较次数大约是(n-1) (n-2) ... 1 n(n-1)/2这是一个典型的等差数列求和结果明显是 O(n^2)。就算某些元素已经就位、可以提前跳过最坏情况下仍然需要走完几乎全部扫描。因此标准循环排序的时间复杂度是 O(n^2)。3.3 二分查找定位O(n log n)既然线性扫描定位太慢能不能用更快的方式定位如果用二分查找需要先有一个有序数组来查询某个元素的位置。比如先复制一份原数组并排序得到 sorted_nums然后对每个元素执行import bisect pos bisect.bisect_left(sorted_nums, item)这样每次定位只需要 O(log n)。但是注意两部分开销构建有序副本 sorted_nums 本身需要 O(n log n)。n 个元素各自二分查找一次需要 O(n log n)。于是整体复杂度变成 O(n log n)。循环交换的部分 O(n) 在总复杂度里反而不重要了。所以在“二分查找 环交换”这种优化版本中循环排序的时间复杂度是 O(n log n)而不是 O(n)。4. 三版实现从 O(n^2) 到 O(n log n) 再到 O(n)4.1 版本一标准循环排序O(n^2)前面已经给出完整代码这里从复杂度角度再做一次拆解。def cycle_sort(nums): n len(nums) for start in range(n - 1): item nums[start] pos start # 线性扫描定位O(n) for i in range(start 1, n): if nums[i] item: pos 1 if pos start: continue # 交换沿着环进行 while pos ! start: # 这里又重新从头扫描也是 O(n) pos start for i in range(start 1, n): if nums[i] item: pos 1 # 交换 nums[pos], item item, nums[pos] return nums虽然代码看着不复杂但每一轮都伴随着完整的数组扫描。测试大数据时耗时增长非常明显。4.2 版本二二分定位优化O(n log n)下面是论坛讨论中出现的“二分查找定位”优化版本。代码适用于元素互不相同的情况用来演示复杂度变化非常直观import bisect def cycle_sort_with_bisect(nums): # 仅用于演示要求 nums 中所有元素互不相同 n len(nums) sorted_nums sorted(nums) for start in range(n - 1): item nums[start] pos bisect.bisect_left(sorted_nums, item) while pos ! start: nums[start], nums[pos] nums[pos], item item nums[start] pos bisect.bisect_left(sorted_nums, item) return nums data [3, 1, 4, 2, 0] print(cycle_sort_with_bisect(data))这个版本的核心变化是把原来“线性扫描统计比当前元素小的个数”改成了二分查找。每个元素的目标位置可以直接通过有序副本查出来。复杂度分析sorted(nums) 排序副本O(n log n)。每次二分查找O(log n)。n 个元素的定位总成本O(n log n)。交换次数O(n)。所以整体时间复杂度是 O(n log n)。这里要注意空间复杂度不再是 O(1)因为需要保存一份排序副本额外空间是 O(n)。4.3 版本三特殊输入下的 O(n) 映射法看到这里有人可能会问循环排序真的能做到 O(n) 吗在某些特殊输入下可以。如果数组元素恰好是 0 到 n-1 的一个排列那么每个元素最终应该放在哪个位置是直接确定的就是它本身的值。此时不需要扫描也不需要二分查找直接根据值映射下标即可def cycle_sort_permutation(nums): # 仅适用于数组元素是 0..n-1 的一个排列 n len(nums) for i in range(n): while nums[i] ! i: target nums[i] nums[i], nums[target] nums[target], nums[i] return nums data [3, 1, 0, 2] print(cycle_sort_permutation(data))这段代码的时间复杂度是 O(n)因为每个元素被交换一次后就会到达最终位置。这也是很多面试题“原地将数组按序排列”的标准解法。但它不是通用排序算法。它利用了输入数据的强约束元素必须是连续整数且互不重复。一旦换成普通数组这个方法就不成立。4.4 用运行时间验证复杂度为了直观感受不同版本的时间增长趋势可以写一个简单测试脚本。import random import time import bisect def cycle_sort(nums): # 标准版代码略直接使用前面实现的函数 pass def cycle_sort_with_bisect(nums): # 优化版代码略 pass def measure(sort_func, data): arr data.copy() start time.perf_counter() sort_func(arr) return time.perf_counter() - start for n in [500, 1000, 2000, 4000]: data random.sample(range(n * 2), n) t1 measure(cycle_sort, data) t2 measure(cycle_sort_with_bisect, data) print(fn{n:5d} 标准版{t1:.4f}s 二分优化版{t2:.4f}s)运行后你会发现标准版随着 n 翻倍耗时大约增长到原来的 4 倍左右这是典型的 O(n^2) 曲线而优化版耗时大约增长到原来的 2 倍多一点更接近 O(n log n) 曲线。用实验数据辅助判断复杂度是排查算法性能问题的常用手段。5. 我从中总结的复杂度分析经验5.1 分析每个循环都要算清执行次数很多算法被误判为更低复杂度都是因为只盯着最显眼的操作而忽略了隐藏循环。例如循环排序里人们容易只看到“交换次数 O(n)”但没去看“为了找到交换位置每次都要遍历一段数组”。这在二分查找优化版本里尤其容易混淆二分查找是 O(log n)。但是要做 n 次二分查找。所以总成本是 O(n log n)不是 O(log n)。判断复杂度时建议把代码中每一层循环都标出来写出每层的大约执行次数再做乘法。如果某一层循环内部还调用了耗时的函数还要继续展开分析。5.2 注意比较排序的下界如果面试中遇到“写一个通用排序算法”的题目并且要求时间复杂度低于 O(n log n)那一定要提高警惕。因为对于任意基于比较的排序算法都存在一个理论下界最坏情况下至少需要 O(n log n) 次比较这个结论来自决策树模型n 个元素的排列有 n! 种可能每次比较最多把可能性缩小一半因此至少需要 log2(n!) 次比较而 log2(n!) 约等于 n log2 n。所以任何通用比较排序算法想达到 O(n) 都是不可能的。除非排序对象有特殊约束例如元素是连续整数可以直接映射下标。元素范围有限可以使用计数排序。元素有固定位数可以使用基数排序。循环排序的优化版同样无法突破这个下界它的最终复杂度是 O(n log n) 是非常合理的。5.3 用不同规模实验验证数量级复杂度的数学推导可能出错实验验证是很好的补充手段。做法很简单取 n 1000、2000、4000、8000分别记录算法耗时。然后观察耗时随 n 的变化比例如果 n 翻倍耗时也翻倍接近 O(n)。如果 n 翻倍耗时约变为原来的 2 到 3 倍接近 O(n log n)。如果 n 翻倍耗时约变为原来的 4 倍接近 O(n^2)。这种验证方式特别适合排查“以为算法是 O(n)但实际跑起来慢得离谱”的情况。6. 循环排序的使用场景与工程建议6.1 循环排序的真正优势循环排序虽然时间复杂度不占优势但它有一个非常独特的优点写入次数少。在一些场景中写入和拷贝的代价远高于比较。例如数组元素是大型对象拷贝一次代价很高。数据要写入寿命有限的存储设备减少写入次数可以延长设备寿命。对内存带宽敏感的嵌入式环境。循环排序的写入次数是 O(n)这是很多 O(n log n) 排序算法做不到的。快速排序、归并排序的平均交换次数虽然也是 O(n log n)但常数通常比循环排序大。6.2 工程上什么时候不要自己造轮子大多数业务开发场景不建议手写循环排序。原因很直接内置排序经过大量优化稳定性、常数因子、内存占用都优于手写版本。循环排序最坏情况 O(n^2)数据量大时性能波动明显。标准循环排序不稳定无法保留相等元素的相对顺序。二分定位优化版需要额外 O(n) 空间代码复杂度也更高收益却很有限。所以在 Java、Python、Go、C 这些语言里直接使用标准库排序函数通常是更合理的选择。6.3 如果你真的想用循环排序如果经过性能测试确认写入次数是核心瓶颈可以考虑循环排序。但要注意以下几点确认输入数据规模不会触发 O(n^2) 的最坏情况。确认不要求排序稳定性。对重复元素做充分测试避免死循环。如果使用二分定位优化版要额外准备有序副本评估内存是否充足。生产环境使用前必须做好基准测试和压力测试而不是只看理论复杂度。7. 小结循环排序是一个很有教学意义的算法。它的移动次数可以做到 O(n)但整体时间复杂度却没有那么理想。标准实现的定位过程是线性扫描复杂度为 O(n^2)即使使用二分查找优化定位也需要构建有序副本并重复二分最终复杂度是 O(n log n)。回到论坛那个帖子真正的收获不在于“谁对谁错”而在于一个通用的算法分析原则时间复杂度要看所有操作的累计开销而不是单看某个操作的成本。如果你最近也在研究排序算法建议亲手敲一遍标准循环排序再用不同数据规模测一测运行时间体会一下“写入次数少”和“比较次数多”到底是怎么共存的。这一层理解打通之后再去看快速排序、堆排序、归并排序的复杂度分析会顺畅很多。