论坛上有人发帖说“循环排序”这个算法的时间复杂度是 O(n log n)理由听起来还挺有道理每个元素最多移动一次所以是 O(n)。乍一听好像没什么问题但真要这么讲快速排序、堆排序都得叫它一声大哥。可实际跑一下就会发现事情没那么简单。循环排序Cycle Sort是个真实存在的排序算法它的核心目标是“尽可能少地移动元素”。如果数组写入成本很高它可能是最优解之一。但它的时间复杂度尤其是比较次数远没有帖子里说的那么乐观。这篇文章会从算法原理开始拆解给出完整代码和复杂度分析最后回答一个很多人纠结的问题循环排序到底值不值得用以及“O(n log n)”这个说法到底错在哪。1. 循环排序是什么把“移动次数”压到最低的原地排序循环排序属于原地排序算法它和选择排序、冒泡排序最大的区别在于排序过程中对数组的写入次数非常少。一个大致的结论是对于 n 个元素的数组循环排序的总写入次数在最坏情况下是 O(n)严格来说不超过 2n 次。这个特性在普通开发里可能没什么感觉因为内存写入开销通常被忽视。但在嵌入式系统、Flash 存储器、EEPROM 这类写操作代价高的场景下减少写入次数往往比减少比较次数更重要。这也是为什么循环排序虽然冷门却始终没有从算法教材里消失。循环排序还有一个别名叫“循环置换排序”。它的核心思路是把数组看成若干个彼此独立的“循环链”每一条链上的元素按照“当前元素应该去的位置”依次移位。处理完一条链这条链上的所有元素就都回到了正确位置之后不会再被改动。从这个描述可以看出来循环排序的关键动作不是“交换两个元素”而是“沿循环链逐个把元素放到该去的位置”。这也是它写入次数少的根本原因。2. 核心原理一个循环链上的“搬家”过程先看一个直观的例子。假设有一个数组[3, 1, 2]循环排序从下标 0 开始处理。取出arr[0] 3然后统计下标 1 到末尾之间有几个元素比 3 小。这里有1和2一共两个所以元素 3 的正确位置应该是0 2 2。接下来做一次交换item 3 arr[2] 3 → 原来的 arr[0] 3 放到下标 2 item 2 → 被挤出来的 2 继续找位置再统计下标 1 到末尾之间有几个元素比 2 小。这里只有1一个所以 2 的正确位置是1。继续操作arr[1] 2 → 原来的 arr[1] 1 被挤出来 item 11 的正确位置是0也就是本轮循环链的起点。回到起点后这一条循环链处理完毕。最终数组变成[1, 2, 3]整个过程里每个元素只被写入一次。这个“沿链搬家回到起点终止”的思路就是循环排序的名字由来。循环排序的流程可以用下面几步概括从下标start开始取出元素item。在start1到n-1范围内统计比item小的元素个数得到pos。如果pos start说明item已经在正确位置跳过本轮。如果数组中有重复元素跳过所有与item相等的目标位置。把item放到pos把arr[pos]取出来作为新的item。重复步骤 2 到 5直到pos回到start。这里真正容易踩坑的地方是重复元素。如果数组中有大量重复值定位时必须跳过相等的位置否则相同元素会被错误地排到彼此的位置上导致排序结果不稳定甚至出现死循环。3. 时间复杂度分析为什么“O(n log n)”这个说法不成立现在回到最初的问题循环排序的时间复杂度到底是多少先说结论写入次数O(n)这是它最大的优点。比较次数最坏 O(n²)平均 O(n²)。额外空间O(1)。为什么比较次数是 O(n²)因为每一轮循环链的处理都需要从头开始统计“当前元素后面有几个比它小的元素”。如果有 n 个元素第一轮要比较 n-1 次第二轮比较 n-2 次直到最后一轮比较 1 次。累计起来就是(n-1) (n-2) ... 1 n(n-1)/2 O(n²)也就是说无论数组是否有序循环排序的比较成本都固定在 O(n²) 量级。这个结论对已经有序的数组也成立因为没有额外的提前终止机制。那论坛帖子里为什么会出现“O(n log n)”的说法常见原因有两个第一个原因是把“每个元素最多移动一次”理解成了“每个元素只处理一次”。实际上移动一次只代表写入次数少不代表比较次数少。为了确定每个元素的位置每一轮仍然需要对未排序区域做线性扫描这部分成本是隐性的却真实存在。第二个原因是混淆了“写入复杂度”和“时间复杂度”。循环排序的 O(n) 指的是 memory writes不是整体运行时间。有些资料在介绍循环排序时只强调“排序 n 个元素只需要 O(n) 次写操作”读者如果忽略“写操作”三个字很容易误以为整个算法是 O(n) 或 O(n log n)。如果只看表面很容易误以为循环排序比快速排序还要优秀。但实际上基于比较的排序有一个理论下界最坏和平均情况下至少需要 O(n log n) 次比较。循环排序的比较次数是 O(n²)说明它在“少比较”这个维度上并不占优。它的优势只在“少写入”这一个维度。4. 完整代码实现用 Python 和 Java 各写一遍下面给出循环排序的可运行实现。为了验证复杂度我会在代码里分别统计比较次数和写入次数。4.1 Python 实现def cycle_sort(arr): 循环排序原地排序写入次数 O(n)比较次数 O(n^2) 返回 (排序后的数组, 写入次数, 比较次数) n len(arr) writes 0 comparisons 0 for start in range(n - 1): item arr[start] pos start # 第 1 次定位统计 start1 到 n-1 中有多少个元素比 item 小 for i in range(start 1, n): comparisons 1 if arr[i] item: pos 1 # 如果 item 已经在正确位置跳过 if pos start: continue # 处理重复元素跳过所有与 item 相等的目标位置 while pos n and item arr[pos]: pos 1 if pos n: continue # 把 item 放到正确位置取出被挤出的元素继续处理 arr[pos], item item, arr[pos] writes 1 # 沿循环链继续处理 while pos ! start: pos start # 重新定位当前 item 的正确位置 for i in range(start 1, n): comparisons 1 if arr[i] item: pos 1 # 跳过重复元素 while pos n and item arr[pos]: pos 1 if pos n: break arr[pos], item item, arr[pos] writes 1 return arr, writes, comparisons if __name__ __main__: data [64, 25, 12, 22, 11] result, writes, comparisons cycle_sort(data[:]) print(排序结果:, result) print(写入次数:, writes) print(比较次数:, comparisons)4.2 Java 实现public class CycleSort { /** * 循环排序 * * param arr 待排序数组 * return 写入次数 */ public static int cycleSort(int[] arr) { int n arr.length; int writes 0; for (int start 0; start n - 2; start) { int item arr[start]; int pos start; // 第一次定位统计后面有多少元素比 item 小 for (int i start 1; i n; i) { if (arr[i] item) { pos; } } // 已经在正确位置 if (pos start) { continue; } // 跳过重复元素 while (pos n item arr[pos]) { pos; } if (pos n) { continue; } // 把 item 放到正确位置并取出被挤出的元素 int temp item; item arr[pos]; arr[pos] temp; writes; // 继续处理循环链 while (pos ! start) { pos start; for (int i start 1; i n; i) { if (arr[i] item) { pos; } } while (pos n item arr[pos]) { pos; } if (pos n) { break; } temp item; item arr[pos]; arr[pos] temp; writes; } } return writes; } public static void main(String[] args) { int[] arr {64, 25, 12, 22, 11}; int writes cycleSort(arr); System.out.print(排序结果: ); for (int value : arr) { System.out.print(value ); } System.out.println(); System.out.println(写入次数: writes); } }4.3 关键逻辑说明代码里有几个细节需要特别说明。第一arr[pos], item item, arr[pos]是一次交换也可以理解为“把当前元素放到它该去的位置同时把被挤出的元素保存到 item 中”。这一步是写入次数的主要来源。第二重复元素处理不能省。如果数组中存在大量重复值比如[2, 2, 2, 1]不跳过重复位置得到的排序结果可能是错误的因为多个相同元素会反复抢占同一个位置。第三比较次数的统计包含了两次 while 循环中的定位扫描。这也是复杂度分析里最容易被忽略的部分。循环链内部每处理一个元素就需要重新扫描一遍未排序区域所以总比较次数会累积到 O(n²)。5. 运行结果与复杂度验证运行上面的 Python 代码输入数组[64, 25, 12, 22, 11]输出为排序结果: [11, 12, 22, 25, 64] 写入次数: 4 比较次数: 18写入次数 4 远小于 n5符合 O(n) 的预期。比较次数是 18接近 n(n-1)/2 10但实际比这个值略高因为循环链内部还要重新定位。如果数组更长比较次数的增长会明显偏向 O(n²)。可以用下面这段代码验证不同规模下的表现import random for n in [100, 200, 400, 800]: arr [random.randint(0, 1000) for _ in range(n)] _, writes, comparisons cycle_sort(arr[:]) print(fn{n}, 写入次数{writes}, 比较次数{comparisons})运行后写入次数大致在 n 到 2n 之间而比较次数会从几千迅速增长到几万、十几万。这个对比很直观写入确实少但“找位置”的成本一点也不便宜。如果运行结果和预期不符第一步先检查重复元素处理部分。最常见的 bug 是while item arr[pos]时没有加pos n判断当后半段全是相同元素时pos 会越界。第二步检查循环链的退出条件确保pos回到start后会正常跳出不会出现死循环。6. 常见排序算法对比循环排序处在什么位置为了说清楚循环排序的定位我把常见排序算法的主要指标放在一张表里对比算法平均时间复杂度最坏时间复杂度额外空间稳定性写入次数冒泡排序O(n²)O(n²)O(1)稳定高大量交换选择排序O(n²)O(n²)O(1)不稳定中每轮最多一次交换插入排序O(n²)O(n²)O(1)稳定中快速排序O(n log n)O(n²)O(log n)不稳定中归并排序O(n log n)O(n log n)O(n)稳定高堆排序O(n log n)O(n log n)O(1)不稳定中循环排序O(n²)O(n²)O(1)不稳定低O(n)从表格可以看出循环排序在时间复杂度上和冒泡、选择排序处于同一档都不适合大规模数据排序。它的差异化优势只在一项写入次数是排序算法中最低之一。选择排序虽然也是每轮最多交换一次但交换两个元素意味着两次写入。循环排序在循环链上搬运时每个元素通常只写一次这条链上参与搬运的元素越多节省的写入量越明显。7. 循环排序适合哪些场景真实项目里的定位循环排序不该出现在通用排序模块里但它在特定场景下确实有价值。第一类场景是小型嵌入式系统。如果数组长度只有几十或几百同时使用的存储器写入寿命有限比如 EEPROM 或 Flash循环排序的“少写入”特性可以直接减少擦写次数延长器件寿命。这时比较次数的开销相对可以接受。第二类场景是对“稳定性”没有要求的小数组排序。循环排序是不稳定排序但如果业务不关心相同元素的相对顺序写入次数少反而能减少数据搬移带来的缓存失效。第三类场景是算法教学和面试讨论。循环排序是理解“排序成本有多维度”的好例子时间复杂度、空间复杂度、写入次数、比较次数这些指标可以独立优化而循环排序拿“比较次数”换“写入次数”。反过来循环排序不适合大规模排序不适合对稳定性有要求的场景也不适合数组元素已经近乎有序的场景。插入排序在近乎有序的数组上几乎不需要搬移数据而循环排序无论数组是否有序都要做完整的定位扫描。在实际项目中更推荐的做法是把循环排序封装成一个独立的小工具只在确认“写入成本远高于比较成本”的模块中使用。不要试图用它替代标准库的排序函数。8. 常见问题与误区排查很多初学者接触循环排序时容易出现下面这些问题问题现象可能原因排查方式解决方案认为循环排序是 O(n) 算法混淆写入次数与时间复杂度重读复杂度分析统计比较次数分别统计写入和比较次数后重新判断认为循环排序是 O(n log n) 算法忽略了定位阶段的线性扫描输出每轮定位的比较次数理解每一轮都需要扫描未排序区域数组有大量重复元素时排序错误重复元素定位时未跳过相等位置构造重复值测试用例在定位后增加while item arr[pos]跳过逻辑运行报下标越界跳过重复元素时 pos 超出数组范围检查 while 条件是否包含pos n在 while 条件和后续逻辑中都加边界判断循环链处理出现死循环退出条件写错pos 无法回到 start打印每轮的 pos 和 item核对 while 条件确保回到起点后终止还有一个容易忽略的点循环排序对数组元素的类型有要求。它依赖“小于”比较来定位所以对于浮点数中的 NaN、对象数组的自定义比较器需要额外确认比较逻辑是否与预期一致。9. 延伸思考如果真想要 O(n log n)应该选谁如果读者真正需要的是“时间复杂度和工程表现都稳定”的排序循环排序显然不是答案。基于比较的排序下界决定了平均情况下至少需要 O(n log n) 次比较。常见的 O(n log n) 排序算法各有取舍快速排序平均性能最好但最坏可能退化到 O(n²)。工程上通常配合随机化或三数取中规避最坏情况。归并排序最坏情况稳定 O(n log n)且稳定但需要 O(n) 额外空间。堆排序最坏情况 O(n log n)空间 O(1)但常数较大实际速度往往不如快排和归并。如果数据范围有限比如整数且范围不大可以考虑计数排序或基数排序它们能突破 O(n log n) 的比较排序下界。循环排序给开发者最大的启示不是“另一个排序算法”本身而是优化思路要区分指标。当你面对一个性能瓶颈时应该先想清楚瓶颈来自读取、写入、比较、空间占用还是缓存局部性。循环排序牺牲比较次数来换取写入次数这种“定向置换”的思路在写敏感场景里依然有参考价值。10. 总结与建议别再传“循环排序是 O(n log n)”了循环排序是一个特点极其鲜明的算法写入次数 O(n)是所有排序算法里最优级别。比较次数 O(n²)和冒泡排序、选择排序一个量级。额外空间 O(1)原地排序。不稳定不适合需要保持相同元素相对顺序的场景。论坛帖子里的“O(n log n)”说法本质是把写入次数 O(n) 与时间复杂度 O(n log n) 混淆后产生的误解。如果读者下次在技术讨论中看到类似说法完全可以指出循环排序的写入虽然少但为了确定每个元素的位置每一轮都需要线性扫描总比较次数是 O(n²)。如果要用一句话总结循环排序的价值那就是它不是一个“变快了”的排序算法而是一个“写得更少”的排序算法。你在实际项目里可以不用它但最好理解它背后的代价交换逻辑。想验证的话跑一篇带计数功能的实现把不同规模数组的比较次数和写入次数打印出来复杂度差异会非常直观。