但比较O(n²)，不是O(n log n))
先说结论经典循环排序不是 O(n log n)它的平均和最坏情况都是 O(n²)。那为什么最近有程序员在技术社区贴出一段循环排序实现后讨论中却出现了“时间复杂度 O(n log n)”这种说法因为这个讨论里至少混进了三个不同的问题经典循环排序到底怎么算复杂度、最小化写入次数意味着什么、加入辅助结构之后的改进版本又是什么复杂度。这篇文章把循环排序拆开讲清楚给出可运行的代码、统计脚本和实际验证方法并解释这个 O(n log n) 说法到底从哪来。如果你正在准备算法面试、要处理写入成本极高的存储场景或者只是对排序算法感兴趣这篇文章可以直接收藏。文章会覆盖循环排序的算法原理、经典实现、复杂度争议来源、测试验证、性能观察、常见误区和工程使用建议所有代码都可以直接复制运行。1. 循环排序核心特点与定位循环排序Cycle Sort是一种基于“数组可以拆成若干个独立循环”这一观察的原地排序算法。它不会像插入排序那样不断搬移元素也不会像快速排序那样做大量交换而是让每个元素尽量只被写入一次直接落到最终位置。它的核心优势不是快而是写入次数最少。写入次数在最坏情况下可以控制在 O(n) 级别这在普通内存排序中没什么吸引力但如果目标存储介质的写入代价远高于读取代价循环排序就是理论上的最优选择之一。特性说明算法类型原地比较排序时间复杂度平均 O(n²)最坏 O(n²)比较次数通常约 n²/2 级别写入次数最优 O(n)这是它的核心价值空间复杂度O(1)只使用常数额外空间稳定性不稳定重复元素顺序无法保证适用场景写入成本高、内存受限、不要求稳定性的场景如果你平时只用快速排序、归并排序和堆排序循环排序确实显得很“冷门”。但它理解起来并不难而且在嵌入式、存储磨损控制等场景里仍然是少数能用的排序思路之一。接下来先从原理入手。2. 循环排序的算法原理与流程循环排序的核心思想是一组元素构成一个或几个循环只要把每个循环里的元素依次放到正确位置数组就会有序。举个例子有一个数组[1, 8, 3, 2, 5]。循环排序会先看第 0 个元素1统计从第 1 个元素开始有多少个元素比1小结果是 0 个所以1的位置就是下标 0它已经在正确位置跳过。再看下标 1 的元素8。从下标 2 开始统计比8小的元素有3、2、5三个所以8应该放到下标1 3 4。把8放到下标 4原来下标 4 上的5被顶出来。接下来处理5从下标 2 开始找比5小的元素只有3、2两个所以5应该放到下标1 2 3。把5放到下标 3原来下标 3 上的2被顶出来。处理2从下标 2 开始找比2小的元素只有2之前的3不算因为只统计当前下标后面的所以2的位置还是下标 2。把2放回去循环结束数组变为[1, 2, 3, 5, 8]。这个过程的核心有两个确定目标位置遍历未排序部分统计有多少元素比当前值小起始下标加上统计数量就是目标位置。循环旋转把当前元素放到目标位置把被替换出来的元素作为下一个处理对象再找它的目标位置直到回到本轮循环的起点。如果遇到重复元素需要在定位时跳过已经占用的相同值否则会出现死循环。例如数组[2, 2, 3]处理第一个2时统计后面比2小的元素是 0 个目标位置是当前下标如果直接放不会出问题但处理第二个2时后面没有比它小的可它前面已经有一个2这时候就要检查目标位置是否已经被相同元素占用如果是就把目标位置继续后移一位。3. 时间复杂度争议为什么论坛里有人说 O(n log n)这个争议的来源值得仔细讨论。经典循环排序的比较次数在随机数据下约等于 n²/2写入次数则控制在 O(n)。有一些讨论帖子会把“写入次数 O(n)”误读为“整个算法 O(n)”也有人把“在最坏情况下每个元素最多移动一次”解释成“整体复杂度接近线性”这两种说法都不准确。至于“循环排序时间复杂度是 O(n log n)”这个说法通常有几种可能来源。第一种来源是测试数据太友好。如果输入数组近乎有序循环排序的内层扫描会在很早就发现“当前元素已经在正确位置”从而跳过大量循环。在小规模随机数据上跑几轮看到的耗时可能和快速排序差不多于是有人会误以为它是 O(n log n)。但把数据规模放大到几万、几十万O(n²) 的增长曲线会迅速暴露出来。第二种来源是混淆了比较次数和写入次数。循环排序确实可以在写入次数上做到 O(n)这是理论上的最优水平。但复杂度衡量的是整体计算量比较操作仍然是 O(n²) 量级。写入最优不代表整体最优。第三种来源是给循环排序加了辅助索引。如果在算法外部先通过哈希表、平衡树或者额外数组记录每个元素的最终位置那么定位这一步可以从线性扫描变成对数查找整体复杂度确实可以接近 O(n log n)。但这时空间开销就不再是 O(1)算法本质上也变成了“先索引再放置”与经典循环排序已经不是同一个东西。第四种来源是对“O”的理解偏差。算法分析里的 O 表示的是增长趋势的渐近上界不是“某一次运行时间”。循环排序里每个元素虽然只写一次但为了找到这个位置它需要反复扫描未排序部分比较次数是主导项。忽略比较次数、只盯写入次数是复杂度分析里最常见的误解。所以正确的结论是**经典循环排序时间复杂度是 O(n²)不是 O(n log n)。如果你看到 O(n log n)要去看它是不是加了额外索引、是不是用了不同实现或者是不是只测了特定输入。**这个判断对任何排序算法的复杂度讨论都适用。4. 循环排序代码实现经典版、统计版与优化参考版4.1 经典 Python 实现def cycle_sort(arr): arr arr[:] n len(arr) writes 0 for cycle_start in range(n - 1): item arr[cycle_start] pos cycle_start # 统计从 cycle_start1 开始有多少元素比 item 小 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 arr, writes这个实现可以在所有元素互不相同、存在重复值的场景下运行。外层循环负责枚举每个可能的循环起点内层循环负责把当前循环里的所有元素旋到正确位置。4.2 带比较次数的统计版本为了验证复杂度需要同时统计比较次数和写入次数。def cycle_sort_with_stats(arr): arr arr[:] n len(arr) writes 0 comparisons 0 for cycle_start in range(n - 1): item arr[cycle_start] pos cycle_start for i in range(cycle_start 1, n): comparisons 1 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): comparisons 1 if arr[i] item: pos 1 while item arr[pos]: pos 1 arr[pos], item item, arr[pos] writes 1 return arr, comparisons, writes这个版本运行时comparisons会显著大于writes。在一个长度为 10000 的随机数组上比较次数通常接近千万级而写入次数只有几千到一万多。这就是“写入 O(n)、整体 O(n²)”的直观证据。4.3 C 实现如果用在嵌入式或底层工具里C 实现更贴合实际。#include vector #include algorithm int cycle_sort(std::vectorint arr) { int writes 0; int n static_castint(arr.size()); for (int cycle_start 0; cycle_start n - 1; cycle_start) { int item arr[cycle_start]; int pos cycle_start; for (int i cycle_start 1; i n; i) { if (arr[i] item) { pos; } } if (pos cycle_start) continue; while (item arr[pos]) { pos; } std::swap(item, arr[pos]); writes; while (pos ! cycle_start) { pos cycle_start; for (int i cycle_start 1; i n; i) { if (arr[i] item) { pos; } } while (item arr[pos]) { pos; } std::swap(item, arr[pos]); writes; } } return writes; }4.4 O(n log n) 参考改进版本如果硬要把循环排序改进到 O(n log n) 量级通常需要破坏“原地”这个约束。比如用索引数组记录每个元素的最终目标位置然后通过二分查找或排序索引来快速定位。import bisect def cycle_sort_with_index(arr): 参考改进版本先建立有序索引用二分查找定位目标位置。 注意这不是经典循环排序额外空间为 O(n)只能算讨论改进方向。 arr arr[:] n len(arr) indexed sorted((val, i) for i, val in enumerate(arr)) target [0] * n # 记录每个位置的目标索引 seen [False] * n rank 0 for i in range(n): val, idx indexed[i] target[idx] i writes 0 for i in range(n): if seen[i] or target[i] i: continue item arr[i] cur i while not seen[cur]: nxt target[cur] arr[cur] arr[nxt] seen[cur] True cur nxt writes 1 return arr, writes这个版本只是“思路参考”它已经使用了额外数组稳定性也发生了变化。把它写在这里是为了说明如果看到循环排序的 O(n log n) 讨论大概率是这一类带有索引辅助的变体而不是教科书里的经典循环排序。5. 功能测试与效果验证5.1 正确性测试用几种典型输入验证排序结果import random test_cases { random: [random.randint(0, 100) for _ in range(20)], sorted: list(range(20)), reverse: list(range(20, 0, -1)), duplicates: [5, 3, 5, 2, 3, 1, 5, 4], single: [42], } for name, data in test_cases.items(): sorted_data, writes cycle_sort(data) assert sorted_data sorted(data), f{name} failed print(f{name}: ok, writes{writes})如果输出结果和 Python 内置sorted()一致说明逻辑正确。如果出现死循环优先检查重复元素处理是否完整。5.2 比较次数与写入次数验证用不同规模的数据统计for n in [100, 500, 1000, 2000]: data [random.randint(0, 10000) for _ in range(n)] _, comparisons, writes cycle_sort_with_stats(data) print(fn{n}: comparisons{comparisons}, writes{writes}, fratio_cmp_n2{comparisons / (n * n):.4f}, ratio_w_n{writes / n:.4f})运行结果会显示出两个规律comparisons大约按 n² 增长writes则按 n 线性增长。如果计算comparisons / n²会发现比值逐渐稳定在一个常数附近而writes / n同样会在某个常数附近波动不会随 n 变大而明显上升。5.3 与快速排序、归并排序的对比验证import time def quick_sort(arr): if len(arr) 1: return arr pivot arr[len(arr) // 2] left [x for x in arr if x pivot] mid [x for x in arr if x pivot] right [x for x in arr if x pivot] return quick_sort(left) mid quick_sort(right) for n in [1000, 2000, 4000]: data [random.randint(0, 100000) for _ in range(n)] start time.time() cycle_sort(data) cycle_time time.time() - start start time.time() sorted(data) builtin_time time.time() - start print(fn{n}: cycle_sort{cycle_time:.4f}s, sorted{builtin_time:.4f}s)这个对比不是为了证明“谁强谁弱”而是为了展示复杂度差异。当 n 翻倍时循环排序的耗时大约会翻 4 倍而内置排序大约只翻 2 倍多一点。这就是 O(n²) 和 O(n log n) 在运行时间上的典型表现。6. 性能观察比较次数、写入次数与空间占用6.1 比较次数是主导项循环排序在最坏情况下对每个cycle_start都要扫描一次数组因此比较次数接近n (n-1) ... 1也就是约 n²/2。这个数字与快速排序、归并排序的 n log n 相比随着 n 增大差距会越来越大。6.2 写入次数为什么是 O(n)循环排序的每个循环里每次只把当前位置的元素放到最终位置被替换出来的元素继续找下一个目标位置。整个数组最多形成 n/2 个循环每个循环内的元素都会在最终位置写入一次所以写入次数上限是 O(n)。这是循环排序最值得称道的地方也是它区别于其他 O(n²) 排序的关键指标。6.3 空间占用经典循环排序只需要常数级别的额外空间所有操作都在原数组内完成。相比归并排序需要 O(n) 额外空间它在内存受限场景下有明显优势。6.4 稳定性问题由于重复元素处理时采用了“跳过已有相同值”的策略相同元素的相对顺序无法保持因此循环排序是不稳定排序。如果业务要求相同关键字的元素保持原有相对顺序循环排序不适合。6.5 如何观察性能曲线建议在本地跑一个多规模测试记录 n 分别等于 1000、2000、4000、8000 时的耗时和比较次数。把数据画成折线图可以直观看到循环排序的耗时曲线是抛物线型增长而不是n log n的平滑上升。这个测试过程也是判断一个排序算法真实复杂度最可靠的方法。7. 常见误区与排查方法问题现象可能原因排查方式解决方案程序卡死或超时重复元素处理不当陷入死循环检查代码中while item arr[pos]是否越界确保跳过重复值后检查边界排序结果错误定位公式写错少算了重复元素打印每个元素的目标位置统计时从cycle_start1开始重复值跳过误以为循环排序是 O(n log n)测试数据量太小或近乎有序增加随机数据规模统计比较次数以比较次数统计为准不是以耗时感受为准写入次数偏大重复元素多循环结构被破坏检查每个元素是否只被写入一次确认循环旋转逻辑完整没有提前跳出在大数组上性能远差于快排这是正常的O(n²) 的特性对比理论比较次数换用快速排序或归并排序8. 最佳实践与使用建议循环排序适合特定场景不建议在普通业务排序中用。它真正有价值的地方在于“写入次数最少”所以适合以下场景Flash/EEPROM 等写寿命有限的存储减少写入次数能延缓介质损耗。嵌入式系统内存紧张O(1) 额外空间在资源受限环境里很重要。写入操作代价远高于读取比如通过极慢总线写入设备时减少写操作比减少读操作收益更大。教学和复杂度分析循环排序是理解“比较复杂度”和“移动复杂度”分离的最佳案例。使用时有几个建议第一先处理重复值。没有重复元素的数组可以直接定位有重复元素时必须跳过已占用位置否则死循环。第二用小数据验证逻辑再上大数据测性能。不要一上来就跑到百万级数组循环排序在百万级随机数据上的耗时可能达到几十秒甚至更长。第三详细记录比较次数和写入次数。如果你在写技术分析文章或面试讲解这两个指标比单纯“速度快不快”更有说服力。第四如果确实需要 O(n log n) 且写入次数较少可以考虑原地归并排序、堆排序或者给循环排序加索引辅助的改进版本。但要清楚这些都不是经典的 O(n²) 循环排序。第五面试中聊排序算法复杂度时要区分“比较次数”“交换次数”“移动次数”三个维度。很多人说“循环排序是 O(n)”说的是移动次数说“循环排序是 O(n²)”说的是比较次数说“改进成 O(n log n)”说的是加索引后的变体。三句话都没错但不能混在一起。9. 总结与下一步循环排序是一个被低估的算法但它的亮点不在速度而在“最小化写入”这个独特能力上。你只需要记住几个关键结论经典循环排序时间复杂度是 O(n²)空间复杂度是 O(1)写入次数是 O(n)是不稳定排序。如果你在论坛或技术讨论里看到“循环排序时间复杂度是 O(n log n)”先不要急着同意去看它是否加了辅助索引、是否只测了特殊数据、是否把写入次数当成了整体复杂度。这三种情况占了绝大多数。下一步建议先跑一遍文中的统计版本代码记录不同规模下的比较次数和写入次数用自己的数据验证 O(n²) 与 O(n) 的差异。然后再根据实际场景判断如果写操作成本极高循环排序值得纳入备选如果只是普通内存排序直接用内置的快速排序或归并排序即可。
