循环排序这个说法最近在技术社区里引起过一阵讨论。起因是有程序员发布了一个被称为“循环排序”的排序方法并给出了一个结论时间复杂度为 O(n log n)。如果不仔细看实现这个结论很容易被接受但如果你真正把代码跑一遍、统计比较次数和交换次数就会发现事情没那么简单。这篇文章不评价那个帖子本身而是把“循环排序”当作一个完整的算法分析案例来拆解。我会先给出循环排序的典型实现再带着读者一起做时间复杂度推导然后用 Python 和 C 写实验脚本通过不同数据规模记录运行时间验证 O(n log n) 的结论到底在什么条件下成立。文章还会讲到为什么经典循环排序的最坏复杂度其实是 O(n²)以及在什么优化条件下才能逼近 O(n log n)。如果你正在学习排序算法、准备算法面试或者需要在真实项目中评估排序方案这篇文章值得收藏。读完你会明白一个算法的时间复杂度结论必须建立在对实现细节和数据分布的清晰认知上而不是只看名字。1. 核心信息速览在正式分析前先把循环排序的关键信息列出来。这里必须区分两个概念经典循环排序Cycle Sort和社区讨论中经过改写的“循环排序”实现。信息项说明算法名称循环排序Cycle Sort算法类型原地排序、基于比较的排序、交换排序经典实现时间复杂度最坏 O(n²)平均 O(n²)社区讨论中的优化实现特定条件下可达 O(n log n)空间复杂度O(1)原地排序稳定性不稳定核心特点写入次数少适合写入成本高的场景适合场景内存写入受限环境、教学演示、算法复杂度分析案例不适用场景大规模通用排序、要求稳定的排序场景需要说明的是关于“循环排序时间复杂度为 O(n log n)”这一结论并不是经典 Cycle Sort 的通用结论。它高度依赖实现方式如果循环排序里加入了“跳过有序段”“快速定位最终位置”等优化那么某些数据集上可以接近 O(n log n) 的表现但如果结构还是经典的逐个查找、循环交换那它的最坏情况仍然是 O(n²)。所以接下来这篇文章要做的核心事情就是把这个结论的成立条件和推导过程讲清楚。这也是算法分析中最重要的能力不是记住某个复杂度而是知道复杂度结论背后的假设。2. 循环排序的算法思想它到底在排什么循环排序的名字里带着“循环”它的核心思路不是像快速排序那样分治也不是像插入排序那样逐个插入而是通过“循环替换”的方式把每个元素直接放到它最终应该出现的位置上。基本逻辑可以这样描述从数组第一个位置开始。找到当前位置应该放置的元素。怎么找统计数组中有多少个元素比当前值小这个数量就是当前值在有序数组中的下标位置。如果当前位置已经正确就移动到下一个位置。如果当前位置不正确就把当前元素和位于它目标位置的元素交换。交换后目标位置正确了但换过来的新元素可能也不在正确位置于是继续重复这个“循环替换”过程直到回到本轮循环的起点。因为每个元素一旦被写入最终位置就不会再被移动所以循环排序的写入次数非常少。在经典实现中它的写入次数理论上是 O(n)这是它最大的价值点也是它在某些写入性能受限的存储设备上仍然有人使用的原因。但是“写入次数少”不等于“比较次数少”。为了找到每个元素的目标位置经典循环排序需要对无序部分重复计数这就导致了大量的重复比较。比较次数在最坏情况下接近 O(n²)。这里就出现了一个关键问题社区讨论中的“循环排序”到底做了什么改良让复杂度看起来变成了 O(n log n)从常见的几种改写着眼引入额外的指针数组或者排序位置表提前算出每个元素的最终位置那本质上已经不是纯循环排序而是类似桶思想或者索引排序代价是额外的空间。内层查找使用二分法定位目标区间这样比较次数可以降到 O(n log n)但前提是数组接近有序或者维护了额外的有序结构。对数组进行分段段内使用循环排序段间使用归并或者快速排序思路这时候整体复杂度可能由分段策略决定。这些改写的共同点是以空间换时间或者引入额外结构。真正意义上的经典循环排序不可能只在“循环替换”这个动作内部做到 O(n log n)。因此看到“循环排序 O(n log n)”这个结论时第一反应应该是去看具体实现而不是直接采信。3. 时间复杂度推导O(n²) 和 O(n log n) 的分界线这一节是整篇文章的核心。我会先用经典实现做完整推导再分析优化实现的理论空间。3.1 经典循环排序的实现与复杂度先看一段标准的循环排序代码。以 Python 为例def cycle_sort(arr): 经典循环排序实现。每轮循环先把一个元素放到最终位置 然后沿着替换链继续处理直到完成所有位置。 比较次数较多适合写入次数敏感的场景。 n len(arr) writes 0 for cycle_start in range(n - 1): item arr[cycle_start] pos cycle_start # 统计有多少个元素比当前 item 小 # 这个数量就是 item 在有序数组中的位置 for i in range(cycle_start 1, n): if arr[i] item: pos 1 # 如果 pos 没变说明当前元素已经在正确位置 if pos cycle_start: continue # 跳过重复元素避免相同值反复交换 while item arr[pos]: pos 1 # 把 item 放到最终位置 arr[pos], item item, arr[pos] writes 1 # 继续沿着替换链处理直到回到本轮起点 while pos ! cycle_start: pos cycle_start for i in range(cycle_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分析复杂度之前先数清楚两个操作比较和写入。外层循环最多执行 n 次每次进入内层统计时都会扫描cycle_start 1到n这一段平均扫描长度是 O(n)。所以仅“统计位置”这一块最坏复杂度就是T(n) n (n-1) (n-2) ... 1 n(n1)/2 O(n²)替换链部分的额外写入在重复元素较少的情况下是 O(n)不会突破上面的上界。所以经典循环排序的最坏时间复杂度准确说是 O(n²)平均情况也是 O(n²)。这是由“每次都要线性统计目标位置”这个设计决定的。空间复杂度是 O(1)因为所有操作都在原数组内完成。3.2 为什么经典实现无法天然达到 O(n log n)从信息论角度看基于比较的排序任何算法平均至少要 log₂(n!) ≈ n log₂ n 次比较才能确定唯一的有序排列。快速排序、归并排序之所以能做到 O(n log n)是因为它们每次比较都能同时排除大量候选排列比较信息利用率高。循环排序的问题在于每找到一个元素的目标位置它做的比较虽然是全局性的但这些比较结果没有被系统化复用。也就是说第一次扫描得到的信息在第二轮统计时没有保留下来。它每轮都在重复做类似的全量统计比较信息利用率很低。这种设计注定了平均复杂度要高。所以“循环排序 O(n log n)”要成立必须改变信息利用方式。比如维护一个已经排序好的索引数组然后用二分查找确定新元素的位置。这时的定位操作复杂度是 O(log n)整体就是 O(n log n)。但代价是额外空间 O(n)而且维护索引数组本身也需要排序成本。这个版本其实已经不是经典循环排序更像是“索引排序 循环写入”。3.3 O(n log n) 在什么条件下可以成立根据上面的分析我给出一个保守判断如果循环排序实现中包含“二分定位 有序索引表”那么时间复杂度确实可以做到 O(n log n)。如果保持纯交换、纯扫描的经典结构那么最坏仍然是 O(n²)。如果数组本身接近有序经典循环排序因为有“当前位置正确就跳过”的机制实际运行时间会明显低于最坏情况最好情况可以到 O(n)。所以论坛帖子里那个结论很可能是在一个特定优化实现下得到的。这个结论不具备普遍性但用来学习复杂度分析倒是很有价值。3.4 补充C 中异或的时间复杂度讨论算法复杂度时经常有人把“某一行代码的时间复杂度”和“整体算法复杂度”搞混。例如在 C 中写a ^ b;这一行的异或操作时间复杂度是 O(1)因为它只做一次位运算不随数组规模变化。有人会用异或交换两个数来优化循环排序的写入操作但这只能减少一个临时变量不会改变整体复杂度的量级。整体复杂度仍然取决于你做了多少次异或操作也就是取决于外层循环和定位逻辑的执行次数。这类细节在分析任何排序算法时都值得注意复杂度是看整体操作的规模增长不是看单个操作是否“更高效”。4. 分析环境与实验准备用数据说话理论推导完了接下来用实验验证。我们需要准备一个可运行的实验环境通过不同数据规模观察运行时间的增长趋势。4.1 环境清单环境项建议配置操作系统Windows / Linux / macOS 均可Python 版本3.8 及以上用于快速原型和计时测试C 编译器GCC 9 或 Clang 10用于高性能对比测试数据随机整数数组、接近有序数组、重复元素数组计时工具Pythontime.perf_counter()或 Cchrono不需要 GPU不需要大型依赖运行环境非常轻量。整个实验在同一台机器上跑完即可重点是观察不同 n 下的耗时比例。4.2 测试数据生成为了对比不同输入条件下的复杂度我准备了三类数据import random def generate_random_array(n, max_value100000): 生成完全随机数组 return [random.randint(0, max_value) for _ in range(n)] def generate_nearly_sorted_array(n, disorder_ratio0.05): 生成接近有序的数组大约 5% 的位置需要调整 arr list(range(n)) swap_count int(n * disorder_ratio / 2) for _ in range(swap_count): i random.randint(0, n - 1) j random.randint(0, n - 1) arr[i], arr[j] arr[j], arr[i] return arr def generate_duplicate_array(n, unique_count10): 生成重复元素很多的数组 return [random.randint(0, unique_count - 1) for _ in range(n)]这三类数据分别覆盖了平均情况、最好情况倾向和重复元素场景能比较全面地反映算法行为。5. 功能测试与效果验证运行时间是否真的接近 O(n log n)现在进入实测环节。为了避免 C 编译时间干扰测试先用 Python 做趋势验证。5.1 Python 实现与计时脚本先写一个完整可运行的测试脚本import random import time def cycle_sort(arr): n len(arr) writes 0 for cycle_start in range(n - 1): item arr[cycle_start] pos cycle_start for i in range(cycle_start 1, n): if arr[i] item: pos 1 if pos cycle_start: continue while item arr[pos]: pos 1 arr[pos], item item, arr[pos] writes 1 while pos ! cycle_start: pos cycle_start for i in range(cycle_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 def run_experiment(arr, name): # 拷贝数组避免排序影响原始数据 test_arr arr[:] start time.perf_counter() writes cycle_sort(test_arr) elapsed time.perf_counter() - start # 验证排序结果正确性 is_sorted all(test_arr[i] test_arr[i 1] for i in range(len(test_arr) - 1)) print(f[{name}] n{len(test_arr)}, 耗时{elapsed:.6f}s, 写入次数{writes}, 有序{is_sorted}) return elapsed if __name__ __main__: sizes [500, 1000, 2000, 4000, 8000] for n in sizes: data generate_random_array(n) run_experiment(data, 随机数组)这里我故意用比较小的 n 做测试。因为经典循环排序在 n8000 时已经可能接近 1 秒左右再往上跑会浪费时间。实际运行这个脚本你会看到耗时随着 n 翻倍而增加约 4 倍。这正是 O(n²) 的增长特征n 翻倍最坏耗时翻 4 倍。如果某个版本是 O(n log n)n 翻倍时耗时只应该增加约 2 倍多一点。这个差异只要连续跑几组不同规模的数据就能明显看出来。5.2 预期结果与判断标准数据规模 nO(n²) 预计耗时增长O(n log n) 预计耗时增长500基准基准1000约 4 倍约 2.2 倍2000约 16 倍约 4.8 倍4000约 64 倍约 10.6 倍8000约 256 倍约 23 倍如果你跑出来的结果明显接近左边一列说明这是经典循环排序。如果接近右边一列说明实现里很可能加入了额外数据结构或跳过了大量无效比较。从材料可以判断经典实现下 O(n log n) 的结论不成立。更稳妥的说法是这个结论可能来自某种经过改写的版本而不是纯循环替换版本。5.3 C 版本实现与对比Python 的结果已经足够看出趋势。如果要用 C 做更细粒度的对比可以这样写#include iostream #include vector #include chrono #include algorithm #include random using namespace std; using namespace chrono; int cycleSort(vectorint arr) { int n (int)arr.size(); int writes 0; for (int cycleStart 0; cycleStart n - 1; cycleStart) { int item arr[cycleStart]; int pos cycleStart; for (int i cycleStart 1; i n; i) { if (arr[i] item) { pos; } } if (pos cycleStart) { continue; } while (item arr[pos]) { pos; } swap(arr[pos], item); writes; while (pos ! cycleStart) { pos cycleStart; for (int i cycleStart 1; i n; i) { if (arr[i] item) { pos; } } while (item arr[pos]) { pos; } swap(arr[pos], item); writes; } } return writes; } int main() { vectorint sizes {10000, 20000, 40000, 80000}; for (int n : sizes) { vectorint arr(n); mt19937 rng(42); uniform_int_distributionint dist(0, 100000); for (int i 0; i n; i) { arr[i] dist(rng); } auto start high_resolution_clock::now(); int writes cycleSort(arr); auto end high_resolution_clock::now(); double elapsedMs duration_castmicroseconds(end - start).count() / 1000.0; bool sorted is_sorted(arr.begin(), arr.end()); cout n n , 耗时 elapsedMs ms , 写入次数 writes , 有序 (sorted ? true : false) endl; } return 0; }编译运行命令g -O2 -stdc17 cycle_sort_test.cpp -o cycle_sort_test ./cycle_sort_test这里用-O2开启优化否则计时结果会包含大量未优化的重复扫描成本。实际运行时n40000 时经典循环排序已经明显变慢而std::sort在同一数据规模下几乎是瞬间完成。这个对比可以直观看到 O(n²) 和 O(n log n) 的差距。5.4 写入次数统计的意义循环排序真正值得关注的是写入次数。测试脚本里输出的writes参数在随机数组下通常接近 n。这一点是其他排序算法做不到的快速排序和归并排序的写入次数远高于 n。如果应用场景是 SSD 写入寿命有限、或者某个远程存储写入成本极高那么循环排序的“写入次数少”特性可能比时间复杂度更重要。但要注意写入次数少的前提是重复元素处理正确。当数组中有大量重复元素时代码里的while item arr[pos]会跳过相同值避免不必要的交换但也会增加比较次数。所以在重复元素场景下循环排序的耗时可能比随机数据更高。6. 资源占用与性能观察时间和空间如何权衡算法层面的“资源占用”主要看两个维度时间和额外空间。6.1 时间维度经典循环排序的时间主要消耗在重复扫描上。观察运行过程可以发现它每次确定一个位置都需要扫描当前位置之后的所有元素。这个扫描操作是绝对的热点。性能瓶颈特征n 翻倍耗时近似变为 4 倍这是 O(n²) 最明显的信号。接近有序时由于pos cycle_start的提前跳出实际扫描次数大幅减少最好情况可降到 O(n)。大量重复元素时内部的while item arr[pos]可能连续多次推进 pos导致额外的比较。6.2 空间维度经典循环排序的空间复杂度是 O(1)它只使用了一个item临时变量没有额外的数组开销。这一点对嵌入式环境很有吸引力。但如果为了实现 O(n log n) 而加入索引表或位置数组空间复杂度就会变成 O(n)。这种空间换时间的取舍必须在实际项目中仔细评估。很多时候现代机器的内存已经不是瓶颈但如果数据量达到千万级额外的 O(n) 空间可能直接导致内存不足。6.3 如何降低耗时几个可行的方向对接近有序的数据可以在外层循环开始前先做一次遍历检查发现整体有序就直接返回。对重复元素多的数据可以先做一次计数或者压缩减少无效交换。如果必须处理大规模数据建议不要使用循环排序直接使用标准库的排序函数。如果一定要用循环排序可以把内层统计改为只扫描未排序部分或者用分段处理降低单次扫描量。7. 常见问题与排查方法我把算法实验和实际使用中可能遇到的问题整理出来。这些问题很多人在跑完代码后都会遇到尤其是复杂度分析和排序结果验证环节。问题现象可能原因排查方式解决方案排序结果不正确重复元素处理出错pos 越界打印每轮交换前后的数组状态检查while item arr[pos]是否越界耗时增长接近 n²使用的是经典循环排序对比不同 n 的耗时倍数确认优化实现或换其他排序大数组时程序卡顿数据规模太大O(n²) 扫描成本高用 n10000 开始逐步增加测试避免超大数组使用循环排序接近有序时耗时依然很高外层循环没有跳过已有序部分检查是否缺少pos cycle_start判断在确定位置后立即continue重复元素很多但交换次数异常高重复值跳过逻辑不完善打印交换前后的 pos 和 item增加while item arr[pos]跳过逻辑计数与理论不一致统计范围错误检查内层循环起点是否从cycle_start 1开始修正循环边界C 版本计时不稳定没有开启编译优化检查编译命令是否包含-O2编译时加上优化选项和std::sort对比差距悬殊基准测试没有使用相同数据用同一份数据分别跑两种排序保持测试数据一致还有一类常见问题在代码写成自测时容易忽略排序后结果正确但写入次数统计偏大。这通常是因为跳过重复元素的逻辑在实际交换后又发生了回环导致同一个元素被交换了多次。这类问题排查时需要把交换动作打点输出逐步跟踪替换链。8. 最佳实践与适用边界循环排序到底该怎么用到这里我们可以给出一个更明确的工程判断了。8.1 循环排序适合什么场景对写入次数极端敏感的场景。比如某些存储介质写入次数直接影响寿命循环排序的写入次数理论上接近 n这是它在工业界仍被关注的理由。教学和学习场景。它是理解“元素最终位置”“替换链”“原地排序”这些概念的经典案例。对内存占用要求极高的小型嵌入式环境。O(1) 额外空间是实打实的优势。8.2 循环排序不适合什么场景通用场景下的大规模数据排序。要求稳定排序的场景相同元素的相对顺序可能改变。对时间要求高、且数据规模会持续增长的服务端场景。8.3 工程实践建议第一次使用前先在数据规模 n10000 左右做一次基准测试确认耗时是否符合预期。不要直接在生产环境使用社区帖子的“优化实现”要弄清它额外消耗了什么资源。如果遇到复杂度结论和实际表现不一致优先检查实现细节而不是怀疑复杂度理论。在多线程环境下循环排序的原地特性虽然占用小但没有明显并发优势不建议用它做并行排序的基础。任何基于比较的排序算法平均复杂度下限都是 O(n log n)。如果看到一个明显优于这个下限的结论要么是算法用了非比较手段要么是结论的条件被限定得很窄。9. 总结与下一步循环排序这个案例最有意思的地方不是它本身有多优秀而是它引发了关于“时间复杂度结论如何成立”的讨论。经典循环排序是 O(n²)这个结论可以推导、可以被实验验证。社区里出现的 O(n log n) 说法背后一定是实现层面的改变而不是循环排序本身的普适结论。如果你现在准备动手验证我建议按这个顺序走跑一遍 Python 版经典循环排序记录不同 n 下的耗时。用 n 翻倍法估算耗时增长倍数确认复杂度趋势。把接近有序数组、重复数组分别加入测试观察差异。用 C 版本和std::sort做对比。尝试在经典实现中加入索引表或二分定位看复杂度能否降到 O(n log n)。下一步可以继续研究的方向包括循环排序在外部排序中的应用、稳定循环排序的构造方法、以及非比较排序计数排序、基数排序在不同约束下的选择逻辑。建议把这篇文章里的测试脚本保存下来以后分析任何排序算法时都能直接在本地跑一套基准数据。