最近在技术论坛上看到一个很有意思的讨论有人贴出了一种他自己实现的“循环排序”算法用几组随机数据测下来感觉不错于是兴奋地表示这个排序“和快排差不多快看起来是 O(n log n)”。结果评论区很快就吵起来了——有人从原理出发指出经典循环排序的定位步骤是线性扫描理论上应该是 O(n²)也有人尝试用二分结构优化定位确实能得到 O(n log n) 级别的复杂度还有人翻出了“比较排序下界”的理论认为任何基于比较的排序都绕不开 Ω(n log n)。这种讨论其实特别有学习价值。因为“循环排序”这个词在不同语境下含义并不完全一样很多人最开始都会混淆它和“圈排序”“循环移位排序”之类的概念。本文不打算评判谁对谁错而是把循环排序的原理、Python 实现、复杂度推导完整拆一遍顺便解释清楚为什么有人会得到 O(n log n) 的结论以及我们应该怎么正确分析这类排序算法。无论你是刚学数据结构的新手还是想复习排序算法底层细节的开发者这篇文章都值得花几分钟看完。1. 背景与核心概念1.1 循环排序是什么循环排序Cycle Sort是一种原地、不稳定的比较排序算法。它的核心思想不是像冒泡排序那样反复比较相邻元素也不是像快速排序那样分治切分而是从“置换”的角度理解数组排序问题当数组最终有序时每一个元素都会有一个“正确位置”把所有不在正确位置上的元素按照位置关系连起来会形成若干个环。循环排序要做的事情就是沿着这些环把每个元素放到它该去的位置从而以最少的“写操作”完成排序。为了理解这一点可以想象一个例子一个数组经过排序后索引位置和元素值必须满足升序关系。如果某个元素目前不在它的目标位置那么这个“错误位置”会指向另一个元素另一个元素又指向下一个位置最终会绕回起点形成一个闭合的循环链条。这个链条在数学上叫“环”cycle。循环排序的每一步都沿着环移动元素所以它又叫“环排序”。这里需要特别说明循环排序并不像冒泡排序、选择排序那样被频繁使用。它在工程中的价值主要体现在“写操作次数极少”这个特性上。对于普通内存里的数组排序写一次数据非常便宜读多次也无所谓但在 EEPROM、Flash 等写入寿命有限的存储介质上减少写操作比减少比较操作更有意义。循环排序在最坏情况下也只需要 O(n) 次写入这是它最大的卖点。1.2 它解决什么问题循环排序解决的核心问题可以概括成一句话用最少的写入操作完成排序。很多排序算法在排序过程中会不断交换元素。以快速排序为例一次 partition 过程中可能多次交换元素总交换次数不好精确控制插入排序在倒序数组上可能要移动大量元素选择排序虽然每轮只交换一次但整体来说交换次数仍然是 O(n)。循环排序把写入次数压得更低理论上对于一个包含 n 个不同元素的数组写入次数最多不超过 2n 次平均来说接近 n 次。这个特性在以下场景中特别有价值存储介质写入寿命受限比如嵌入式设备中的 Flash 存储。数据量大但每个元素很小写入成本远高于读取成本。需要对一组关键配置做原地排序且不希望频繁改写存储单元。当然循环排序也有明显缺点它基于比较且通常用线性扫描来确定元素的目标位置所以比较次数往往很高。经典实现的时间复杂度是 O(n²)不适合大规模数据排序。这也是它在通用排序中不流行的原因。1.3 容易混淆的概念在学习循环排序时有三个概念经常被混在一起需要提前区分清楚名称英文核心思路时间复杂度循环排序Cycle Sort按元素位置形成环沿环放置元素O(n²)圈排序Circle Sort对称比较并交换递归处理平均 O(n log n) 左右循环移位排序Rotation Sort数组看作环形结构通过旋转实现归位取决于实现中文里“循环”和“圈”经常混译所以“Cycle Sort”和“Circle Sort”在网上经常被翻译成同一个词。实际上两种算法的思路完全不同。本文讨论的是 Cycle Sort也就是按“环”来移动元素的排序算法。如果你看到某篇文章里的“循环排序”是对称交换元素的那它很可能在讲 Circle Sort需要先看代码再对照结论。1.4 论坛事件引出问题它真的是 O(n log n) 吗回到标题里的场景某个程序员在论坛上发布了一种循环排序算法结果发现它的时间复杂度为 O(n log n)。这听起来有点“打脸”因为很多人记忆中的循环排序明明是 O(n²)。其实这类现象在算法讨论中很常见。原因是“循环排序”并不是一个严格唯一的算法名称它更像是一类“沿着环放置元素”的实现方式。具体复杂度取决于一个关键步骤怎么实现找目标位置的时候是线性扫描还是用二分查找/平衡树等数据结构辅助定位。经典实现中判断某个元素应该放在哪个位置需要在剩余区间内统计“比当前元素小的元素个数”。这个过程是 O(n) 的外层又有 n 轮所以得到 O(n²)。但如果有人把“定位”这一步做了优化比如在元素值域受限时用桶来定位或者用有序结构一次性记录所有元素的位置分布那每一轮定位成本就会下降。当定位成本降到 O(log n)整体时间复杂度就可能变成 O(n log n)。所以严格来说“循环排序的时间复杂度是多少”这个问题并没有唯一的答案。你需要先说明你用的是哪一种实现、允许多少额外空间、数据是不是整数。这正是算法分析有意思的地方。2. 环境准备与版本说明2.1 语言与运行环境本文的示例代码使用 Python 编写。Python 语法简洁不需要复杂的工程配置非常适合用来验证算法思路和统计比较次数。示例代码在 Python 3.6 及以上版本均可运行新版 Python 3.10、3.11、3.12 也没问题。如果你使用的是更早的 Python 2不建议直接复制运行因为语法和部分内置行为差异较大。在开始之前请确保你的电脑上已经安装了 Python。可以在终端或命令行中执行下面的命令检查版本python --version如果显示类似Python 3.10.12的输出说明环境正常。如果没有安装可以去 Python 官网下载安装包或者使用某些预装 Python 的在线练习平台比如常见的在线 Python 运行环境。本文示例不依赖第三方库只使用标准库random和time所以不需要额外安装任何依赖。2.2 推荐运行方式你可以选择下面任意一种方式运行本文代码在 PyCharm、VS Code 等 IDE 中新建一个 Python 文件比如cycle_sort_demo.py直接运行。在终端进入文件目录执行python cycle_sort_demo.py。使用 Jupyter Notebook把代码拆成多个单元格逐步运行这种方式更适合观察中间变量。建议使用第一种方式因为后续会有测试函数和实验代码放在同一个脚本中更直观。2.3 项目结构为了方便阅读建议保持一个简单的单文件结构cycle_sort_demo/ └── cycle_sort_demo.py后续所有代码都可以放在这个文件里。如果你想把“经典实现”和“实验对比”分开也可以自行拆成两个文件本质上不影响演示效果。3. 核心原理拆解3.1 从“环”的角度理解排序先理解一个基础概念一个数组在排序过程中可以看作一系列“元素迁移”的组合。假设数组[2, 1, 3, 0]最终要变成[0, 1, 2, 3]那么元素0应该从索引 3 移动到索引 0元素2应该从索引 0 移动到索引 2元素3应该从索引 2 移动到索引 3元素1已经在正确位置。把这种迁移关系画出来你会发现0 - 2 - 3 - 0形成了一个环1单独成为一个大小为 1 的环。循环排序的基本思路就是逐个检查数组元素如果发现某个元素不在正确位置就从这个元素开始沿着“谁该占据这个位置”的关系一直找下去直到绕回起点。这个过程很像玩拼图先把一个元素放到正确位置被挤出来的元素再去找自己的正确位置依次类推。这个过程的好处是每个元素只需要被写一次或者被临时保存在一个变量中最后再写回。整个算法不需要额外的辅助数组空间复杂度是 O(1)。3.2 如何计算元素的正确位置循环排序最关键的步骤是给定当前元素item如何知道它应该放到哪个索引位置如果数组最终是升序排列并且所有元素互不相等那么item在升序数组中的正确位置就等于数组中“小于 item 的元素个数”。举个例子数组[5, 2, 3, 1, 4]中元素3小于它的元素有2和1所以它在升序数组中的目标位置是索引 2。经典循环排序会在每一轮中从cycle_start 1开始扫描到数组末尾统计有多少个元素比item小。注意它只扫描cycle_start后面的部分因为前面的部分已经被处理过不再参与比较。统计结果pos就表示item应该去的位置。如果是整数数组并且元素值域不大也可以利用桶或计数数组直接得到目标位置。但这属于优化思路后面会单独讨论。3.3 重复元素怎么处理如果数组里有重复元素情况会稍微复杂一点。比如数组[2, 2, 2, 1, 1]第一个2的正确位置应该是索引 2 还是索引 3理论上2放到索引 2、3、4 中都可能满足升序结果但稳定排序要求保持原始相对顺序循环排序本身是不稳定排序所以它不保证这一点。标准实现处理重复元素的方法很简单在计算出pos之后如果发现item arr[pos]就继续向后移动pos直到找到第一个不等于item的位置。这样可以避免把重复值放到完全一样的位置上。如果没有找到说明当前元素已经在重复值区域的末尾不需要额外移动。在实际代码中这个“向后移动”的步骤需要注意索引越界问题。尤其是数组末尾全是同一个值的时候pos可能会一路增加到n此时应该结束处理而不是继续访问arr[pos]。3.4 稳定性与空间复杂度循环排序是不稳定排序。原因很简单当多个相同元素存在时它只保证值的位置正确不保证相同值之间的原始相对顺序。对于不需要稳定性的场景这没问题如果需要稳定排序应该优先考虑归并排序、插入排序或 Python 内置的sorted()。空间复杂度方面循环排序只需要一个临时变量item来保存当前环上的元素因此额外空间是 O(1)属于非常典型的原地排序算法。不过若使用优化后的定位方式例如维护辅助有序索引额外空间会相应增加这个在后面分析复杂度的章节再展开。4. 经典循环排序实现4.1 完整 Python 实现下面给出一个经典循环排序的完整实现。为了便于分析我在代码中额外统计了比较次数和写次数。这段代码可以直接复制运行。def cycle_sort(arr): 循环排序Cycle Sort 返回排序后的新数组以及比较次数、写次数。 arr arr[:] # 拷贝一份避免修改原数组 n len(arr) writes 0 compares 0 for cycle_start in range(n - 1): item arr[cycle_start] pos cycle_start # 统计从 cycle_start1 到末尾有多少元素比 item 小 # 这个数量加上 cycle_start 就是 item 的目标位置 for i in range(cycle_start 1, n): compares 1 if arr[i] item: pos 1 # 如果 item 已经在正确位置跳过 if pos cycle_start: continue # 处理重复元素跳过所有与 item 相等的元素 while pos n and item arr[pos]: pos 1 # 如果越过数组末尾说明 item 已经在重复值区域中无需移动 if pos n: continue # 把 item 放到正确位置被挤出来的元素暂存在 item 中 if pos ! cycle_start: arr[pos], item item, arr[pos] writes 1 # 沿着环继续处理直到回到 cycle_start while pos ! cycle_start: pos cycle_start # 重新计算 item 的目标位置 for i in range(cycle_start 1, n): compares 1 if arr[i] item: pos 1 # 跳过重复元素 while pos n and item arr[pos]: pos 1 if pos n: break if item ! arr[pos]: arr[pos], item item, arr[pos] writes 1 return arr, compares, writes4.2 代码关键点说明第一个关键点是外层循环只走到n - 2也就是range(n - 1)。因为当最后一个元素到达时它前面的元素都已经有序最后一个元素自然也在正确位置不需要再单独处理。第二个关键点是“定位”操作。内层第一个for循环统计的是cycle_start 1到末尾之间“小于 item”的元素个数。这个统计结果并不是直接索引而是“偏移量”pos的初始值是cycle_start每遇到一个更小的元素就加 1。第三个关键点是环的旋转。当item被放到正确位置后原来正确位置上的元素被“挤”出来存到item变量里。此时item还不是最终位置需要继续找它的位置直到回到起点cycle_start。这个逻辑用while pos ! cycle_start控制是整段代码最容易写错的地方。第四个关键点是重复元素处理。代码中用while pos n and item arr[pos]跳过重复值。如果pos n说明数组末尾没有比item更大的元素当前item不需要再被写入直接结束本轮即可。经典实现中很多人省略了pos n判断容易在重复元素场景下抛索引越界异常。4.3 测试代码为了验证算法正确性可以编写一个简单的测试函数覆盖空数组、单元素、纯重复元素、乱序数组等场景。def main(): test_cases [ [5, 2, 3, 1, 4], [1, 2, 3, 4, 5], [5, 4, 3, 2, 1], [2, 2, 2, 1, 1], [4, 4, 2, 4, 3, 3, 1], [1], [] ] for arr in test_cases: sorted_arr, cmp_count, write_count cycle_sort(arr) print(原数组:, arr) print(排序后:, sorted_arr) print(比较次数:, cmp_count, 写次数:, write_count) print(- * 40) if __name__ __main__: main()4.4 运行与预期结果运行上述代码后输出大致如下原数组: [5, 2, 3, 1, 4] 排序后: [1, 2, 3, 4, 5] 比较次数: 21 写次数: 6 -------------------------------------------------- 原数组: [1, 2, 3, 4, 5] 排序后: [1, 2, 3, 4, 5] 比较次数: 10 写次数: 0 -------------------------------------------------- 原数组: [5, 4, 3, 2, 1] 排序后: [1, 2, 3, 4, 5] 比较次数: 24 写次数: 8 -------------------------------------------------- 原数组: [2, 2, 2, 1, 1] 排序后: [1, 1, 2, 2, 2] 比较次数: 11 写次数: 3 -------------------------------------------------- 原数组: [4, 4, 2, 4, 3, 3, 1] 排序后: [1, 2, 3, 3, 4, 4, 4] 比较次数: 47 写次数: 10 -------------------------------------------------- 原数组: [1] 排序后: [1] 比较次数: 0 写次数: 0 -------------------------------------------------- 原数组: [] 排序后: [] 比较次数: 0 写次数: 0 --------------------------------------------------从输出中可以看到两个非常重要的现象第一对于已经有序的数组循环排序的写次数为 0因为它发现每个元素都在正确位置不需要移动第二比较次数并不会因为数组有序而大幅减少它仍然接近n * (n - 1) / 2。这说明循环排序的复杂度瓶颈在于比较而不是写入。5. 时间复杂度分析为什么经典实现是 O(n²)5.1 比较次数推导经典循环排序最耗时的部分是“统计小于当前元素的个数”。这个操作需要从cycle_start 1扫描到数组末尾扫描长度平均约为n / 2外层循环执行n - 1次因此仅一层扫描的比较次数就约为(n - 1) (n - 2) ... 1 n * (n - 1) / 2如果数组完全逆序内层环旋转时可能再次触发扫描比较次数会进一步增加。最坏情况下每个元素都可能触发一次完整的环移动而每次环移动都要重新扫描一次剩余区间所以总比较次数依然保持在 O(n²) 级别。上面例子里n5时比较次数 21接近5*4/2 10的两倍正好体现了环旋转带来的额外扫描。5.2 写次数推导循环排序最大的特点是写次数少。每处理一个环除了启动环的那个元素以外其他元素都只需要写一次。一个数组最多可以分成若干个环整体写次数不超过2n。如果数组已经有序写次数为 0如果数组元素各不相同且全部错位写次数大约为2n - 1或者更少。因此循环排序的复杂度特征可以总结为比较次数O(n²)写次数O(n)空间复杂度O(1)稳定性不稳定5.3 通过实验验证复杂度为了更直观地验证 O(n²)可以用随机数组做一组不同规模的时间对比。下面的代码会统计从n256到n4096的比较次数和耗时。import random import time def experiment(): print(n\t比较次数\t写次数\t耗时(ms)) for n in [256, 512, 1024, 2048, 4096]: arr [random.randint(0, 10000) for _ in range(n)] start time.perf_counter() sorted_arr, cmp_count, write_count cycle_sort(arr) elapsed (time.perf_counter() - start) * 1000 print(f{n}\t{cmp_count}\t{write_count}\t{elapsed:.2f}) if __name__ __main__: experiment()当n从 2048 增加到 4096 时数组规模扩大 2 倍比较次数大约会扩大 4 倍耗时也近似扩大 4 倍。这就是典型的 O(n²) 增长曲线。而 O(n log n) 的算法在同规模下耗时只应该扩大约 2 倍出头对比非常明显。6. 回到标题那个“O(n log n)”是怎么回事6.1 定位步骤决定复杂度理解完整段代码后你会发现循环排序的复杂度瓶颈其实只在一个地方计算当前元素应该放在哪个位置。经典实现用遍历剩余区间的方式统计“小于 item 的元素数量”这个步骤是 O(n) 的。如果你能把这个步骤优化成 O(log n) 或者更快整体复杂度就会发生变化。假设在每一步中我们不是逐个扫描而是借助一棵平衡二叉树维护“尚未归位元素中的值分布”。每次需要定位item时直接查询树中小于item的元素数量查询时间是 O(log n)。外层循环执行 n 次总定位时间就是 O(n log n)。与此同时环旋转阶段的写操作依然是 O(n)。于是整个排序算法的时间复杂度从 O(n²) 降到了 O(n log n)。这也就是论坛里“循环排序是 O(n log n)”说法的来源它不是空穴来风而是对“定位步骤”做了数据结构层面的优化。需要注意的是这种优化通常需要额外的内存空间来维护索引结构因为纯原地数组很难在 O(log n) 时间内完成“区间内小于某个值”的查询。6.2 比较排序下界的限制还有一种常见解释是任何基于比较的排序算法最坏情况下至少需要 Ω(n log n) 次比较。这是由决策树模型推导出的理论下界。因此当一个人说自己的“循环排序是 O(n log n)”时这个复杂度完全符合理论预期它并没有突破下界只是比经典实现更接近理论最优。如果一个循环排序实现号称是 O(n)那就必须额外说明它利用了非比较信息。例如数组元素是整数并且值域很小。使用计数数组或桶来直接统计元素位置。排序过程不再依赖元素之间的两两比较。这类排序确实可能做到 O(n)但已经不属于“基于比较的排序”范畴了也失去了通用性。所以讨论复杂度时先确定“基于比较”还是“非比较”非常重要。6.3 对论坛讨论的正确态度当我们再次看到“循环排序时间复杂度 O(n log n)”这类说法时不要急着否定而是可以按下面几个问题去分析他实现的循环排序定位过程是线性扫描还是使用了辅助结构他统计的是比较次数、写次数还是整体运行时间数组元素的取值是随机整数还是固定值域排序过程是否保持稳定空间复杂度是多少这些问题问清楚了很多看似矛盾的结论都能得到解释。学习算法时最忌讳只看算法名字和结论忽略具体实现细节。7. 常见问题与排查思路7.1 重复元素导致索引越界问题现象常见原因解决思路运行时报IndexError: list index out of range计算重复元素位置时pos越过了数组末尾在while item arr[pos]中加入pos n判断当pos n时直接结束本轮处理排序结果不正确重复值顺序混乱重复值跳过逻辑不正确元素被放入错误位置对照标准实现检查pos的初始值和重复值跳过逻辑数组长度很大时运行特别慢比较次数是 O(n²)改用归并排序、快速排序或 Python 内置sorted()7.2 循环排序与圈排序混淆网上搜索“循环排序”时很容易查到一个叫 Circle Sort 的算法中文常被翻译成“圈排序”或“循环排序”。Circle Sort 的典型实现是通过对称位置比较和交换来递归逼近有序数组和 Cycle Sort 完全不同。Circle Sort 的复杂度分析通常也不是 O(n²)而是和具体实现有关有时能到 O(n log n) 附近。如果你读到的文章里讨论的是对称交换那它讲的其实是 Circle Sort结论不能直接套用在 Cycle Sort 上。判断方法很简单看代码里有没有“形成环并沿环移动”的逻辑。如果有那就是 Cycle Sort如果只是递归比较对称位置然后交换那就是 Circle Sort。7.3 为什么局部场景下写次数为 0 却依然很慢循环排序已经有序的数组时写次数确实为 0但这并不代表算法很快。因为每一轮外层循环仍然要做一次完整的区间扫描以确认当前元素是否在正确位置。对于长度为 n 的有序数组循环排序的比较次数仍是 O(n²)。很多初学者会误以为“不用交换 不耗时”但实际耗时主要来自比较和循环控制而不是赋值。这也解释了为什么循环排序不适合作为通用排序算法它的优势完全体现在“减少写操作”上而不是减少比较或整体运行时间。8. 最佳实践与工程建议8.1 什么时候适合用循环排序循环排序并不适用于所有场景。从工程角度来看以下几个条件同时满足时循环排序才会体现出价值写操作的成本远高于读操作。数组规模在几千以内比较开销可以接受。不要求排序稳定性。存储空间有限不能使用额外辅助数组。典型场景包括嵌入式设备上的 EEPROM 数据整理、Flash 存储中的小规模重排、以及某些对固态存储写入次数敏感的边缘设备。如果只是普通服务器程序中的内存数组排序建议直接使用语言内置排序。Python 内置的sorted()和list.sort()使用 TimSort时间稳定为 O(n log n)稳定性好底层是 C 语言实现实际运行速度远快于任何纯 Python 手写排序算法。8.2 如果你想尝试优化循环排序如果对循环排序的优化感兴趣可以从下面几个方向入手优化定位步骤用平衡树、线段树等数据结构维护剩余元素信息将定位成本从 O(n) 降到 O(log n)代价是额外空间。利用值域信息如果数组是整数且值域已知可以用计数数组一次性计算所有元素的正确位置后续通过环移动减少写入。混合排序小规模数据使用循环排序减少写次数大规模数据切换到归并排序或快速排序。并行化将数组分成多个区段每个区段内独立执行循环排序最后再归并。需要提醒的是这些优化都会增加代码复杂度实际收益要结合数据特征来评估。不要为了追求“理论复杂度更优”而牺牲代码可维护性。8.3 如何科学分析排序算法复杂度通过循环排序这个例子我们可以总结出一套分析排序算法复杂度的科学方法。第一把“比较次数”“写次数”“读