但比较为何是O(n^2)？)
循环排序Cycle Sort在算法题里并不算热门但每隔一段时间它就会因为一个复杂度争议出现在开发者社区里有程序员发布一段看起来每个元素只移动一次的排序代码宣称时间复杂度是 O(n log n)。评论区的讨论往往从“这个算法很巧妙”开始到“复杂度分析错了”结束。这里先给结论经典循环排序的比较次数是 O(n^2)整体时间复杂度也是 O(n^2)它真正特殊的地方不是时间而是写操作次数只有 O(n)。这篇文章用循环排序作为例子把复杂度分析过程完整走一遍并解释为什么“看起来很快”和“真的很快”是两回事。1. 先从循环排序的“复杂度悬案”说起1.1 论坛里的 O(n log n) 说法从哪来在算法交流帖子中循环排序经常以两种面孔出现。一种是比较书里的标准形象它是一种原地、不稳定、以“最少写操作”为目标的比较排序。另一种是社区里的误读有人贴出一段实现理由是“每个元素最多被移动一次所以复杂度接近 O(n)”为了和比较排序的理论下界 O(n log n) 拉平又改口称“实际上应该是 O(n log n)”。这个误判有它的来源。循环排序的交换次数确实很少每个环内的元素最终都会被移动到正确位置中间不会像冒泡排序那样反复交换同一个元素。如果只统计“数组元素被写入的次数”循环排序确实能达到 O(n) 量级。可惜的是排序算法的时间复杂度不只是看写操作次数。循环排序为了确定每个元素的目标位置需要反复扫描右侧子数组这一步的比较次数是 O(n^2)。很多帖子只看到了“移动少”却没有把“比较多”计入总账。还有一种更隐蔽的推导错误发帖者把代码中的两层循环分别看成 O(n) 和 O(log n)理由是“内层循环是在逐步逼近正确位置”。但实际上标准循环排序的内层 for 是线性扫描不是二分查找。它从当前位置一直扫到数组末尾逐个数一遍没有利用任何有序区间信息。没有额外辅助结构时内层循环不可能做到 O(log n)。1.2 循环排序到底是什么循环排序是一种基于“置换环”的排序算法。它不像插入排序那样逐步把新元素插入到已排序区间也不像冒泡排序那样通过相邻交换把大元素一步步送到尾部。它的做法是每次取一个待处理元素统计它右侧有多少个比它小的元素从而算出它应该落到哪个索引然后把该索引位置的旧元素替换出来继续处理这个旧元素。这个“替换新元素并继续处理”的过程会在若干个元素之间形成一条闭环因此叫循环排序。它最突出的特性是写操作次数少。在普通内存排序中读和写速度差距不大交换次数多一点少一点通常无所谓。但在 EEPROM、Flash 等写入成本高的存储设备上每一次写操作都意味着擦写损耗和时间开销。循环排序能把写次数压到 O(n) 量级因此在特殊场景中仍然有实用价值。理解循环排序的关键不是记住代码而是理解“定位元素”和“移动元素”是两件完全独立的事情。移动少不等于比较少这是整个复杂度误判的核心。1.3 这篇文章的分析路径下面会按“原理 - 实现 - 复杂度推导 - 实验验证 - 误区排查 - 选型建议”的顺序展开。目标是让读者能自己写出一个带计数器的循环排序能通过运行结果判断复杂度量级也能在社区讨论中快速识别类似 O(n log n) 的错误结论。最后还会给出一份可复用的复杂度分析自检清单用来排查其他算法中相似的坑。2. 循环排序的核心机制置换环2.1 从“把元素放到它该去的位置”开始排序的本质是让每个元素到达它的最终位置。对升序排序来说一个元素 x 的目标位置可以通过统计数组中有多少个元素小于 x 来计算如果有 k 个元素小于 xx 就应该落在下标 k从 0 开始。这是计数排序、桶排序等多种算法的基础思想循环排序也使用了这个规则。假设当前待处理元素是 item它对应的起点下标是 cs。算法会扫描 cs 右侧的所有元素数出有多少个元素小于 item。这个数量记为 lessCount那么 item 的目标位置 pos 就是 cs lessCount。道理很简单左侧的 cs 个位置已经属于前面的较小元素右侧又有 lessCount 个元素比 item 小所以 item 在整个有序序列中的排名就是 cs lessCount。只看这一步复杂度还不算高。麻烦在于item 被放到 pos 后原本占据 pos 的元素会被替换出来成为新的 item这个新 item 又需要重新扫描它右侧的所有元素来确定自己的目标位置。这个过程不断延伸直到回到起点 cs形成一个闭环。这个闭环就是排序中“置换”的环。2.2 环的识别与移动举一个具体例子。数组是[3, 5, 2, 1, 4]目标是升序排列。升序结果应该是[1, 2, 3, 4, 5]。下面用下标 0 作为起点下标 0 的元素是 3它应该落在下标 2。下标 2 的元素是 2它应该落在下标 1。下标 1 的元素是 5它应该落在下标 4。下标 4 的元素是 4它应该落在下标 3。下标 3 的元素是 1它应该落在下标 0。于是形成了闭环0 - 2 - 1 - 4 - 3 - 0循环排序要做的就是沿着这个环把每个元素送到它应该去的位置。这个环的长度是 5等于数组长度因此整个数组处于一个环中。有些数组会包含多个环每个环独立处理有些位置上的元素已经就位它们可以看作是长度为 1 的环不需要移动。2.3 一次完整排序的步骤演示仍以[3, 5, 2, 1, 4]为例从下标 0 开始令 item arr[0] 3计算目标位置 pos 2。交换 item 与 arr[2]得到 item 2arr[2] 3。item 的目标位置是下标 1交换 item 与 arr[1]得到 item 5arr[1] 2。item 的目标位置是下标 4交换 item 与 arr[4]得到 item 4arr[4] 5。item 的目标位置是下标 3交换 item 与 arr[3]得到 item 1arr[3] 4。item 的目标位置回到下标 0把 item 1 放回 arr[0]。完成后的数组是[1, 2, 3, 4, 5]。整个过程只涉及一次置换环元素移动次数不多但为了确定每个 item 的目标位置算法在每次循环中都扫描了右侧子数组。第一次扫描比较了 4 次第二次扫描比较了 3 次第三次 2 次第四次 1 次累计就是 4 3 2 1 10 次比较。这个数字正好等于n(n-1)/2也就是 O(n^2) 的来源。2.4 为什么说它是“写优化”排序循环排序的核心价值在于它把数组元素移动到最终位置的次数控制在线性级别。对于随机数组插入排序在最坏情况下可能进行 O(n^2) 次移动循环排序正常实现下最多移动 O(n) 次。因此当“写”比“读”和“比较”昂贵得多时循环排序会变得有吸引力。例如在 EEPROM 或某些 Flash 存储设备上擦写次数有寿命限制。排序一个较小的关键数据块时选择写次数更少的算法可以减少磨损。在普通内存里写和读的代价差异不大O(n^2) 的比较次数就会成为主要瓶颈所以它很少用于通用排序。这里需要记住一个原则写优化是循环排序的亮点但写优化不能直接等于时间复杂度更低。3. 严格推导循环排序的时间复杂度3.1 算法分析中要明确基本操作分析排序算法复杂度前首先要确定“基本操作”是什么。在基于比较的排序算法中通常把元素之间的比较次数作为基本操作。原因有两个一是比较直接决定排序逻辑二是元素交换、赋值等操作的数量可以与比较次数用一个常数因子联系起来。循环排序恰恰 循环排序复杂度解析：写操作O(n)但比较为何是O(n^2)？
循环排序Cycle Sort在算法题里并不算热门但每隔一段时间它就会因为一个复杂度争议出现在开发者社区里有程序员发布一段看起来每个元素只移动一次的排序代码宣称时间复杂度是 O(n log n)。评论区的讨论往往从“这个算法很巧妙”开始到“复杂度分析错了”结束。这里先给结论经典循环排序的比较次数是 O(n^2)整体时间复杂度也是 O(n^2)它真正特殊的地方不是时间而是写操作次数只有 O(n)。这篇文章用循环排序作为例子把复杂度分析过程完整走一遍并解释为什么“看起来很快”和“真的很快”是两回事。1. 先从循环排序的“复杂度悬案”说起1.1 论坛里的 O(n log n) 说法从哪来在算法交流帖子中循环排序经常以两种面孔出现。一种是比较书里的标准形象它是一种原地、不稳定、以“最少写操作”为目标的比较排序。另一种是社区里的误读有人贴出一段实现理由是“每个元素最多被移动一次所以复杂度接近 O(n)”为了和比较排序的理论下界 O(n log n) 拉平又改口称“实际上应该是 O(n log n)”。这个误判有它的来源。循环排序的交换次数确实很少每个环内的元素最终都会被移动到正确位置中间不会像冒泡排序那样反复交换同一个元素。如果只统计“数组元素被写入的次数”循环排序确实能达到 O(n) 量级。可惜的是排序算法的时间复杂度不只是看写操作次数。循环排序为了确定每个元素的目标位置需要反复扫描右侧子数组这一步的比较次数是 O(n^2)。很多帖子只看到了“移动少”却没有把“比较多”计入总账。还有一种更隐蔽的推导错误发帖者把代码中的两层循环分别看成 O(n) 和 O(log n)理由是“内层循环是在逐步逼近正确位置”。但实际上标准循环排序的内层 for 是线性扫描不是二分查找。它从当前位置一直扫到数组末尾逐个数一遍没有利用任何有序区间信息。没有额外辅助结构时内层循环不可能做到 O(log n)。1.2 循环排序到底是什么循环排序是一种基于“置换环”的排序算法。它不像插入排序那样逐步把新元素插入到已排序区间也不像冒泡排序那样通过相邻交换把大元素一步步送到尾部。它的做法是每次取一个待处理元素统计它右侧有多少个比它小的元素从而算出它应该落到哪个索引然后把该索引位置的旧元素替换出来继续处理这个旧元素。这个“替换新元素并继续处理”的过程会在若干个元素之间形成一条闭环因此叫循环排序。它最突出的特性是写操作次数少。在普通内存排序中读和写速度差距不大交换次数多一点少一点通常无所谓。但在 EEPROM、Flash 等写入成本高的存储设备上每一次写操作都意味着擦写损耗和时间开销。循环排序能把写次数压到 O(n) 量级因此在特殊场景中仍然有实用价值。理解循环排序的关键不是记住代码而是理解“定位元素”和“移动元素”是两件完全独立的事情。移动少不等于比较少这是整个复杂度误判的核心。1.3 这篇文章的分析路径下面会按“原理 - 实现 - 复杂度推导 - 实验验证 - 误区排查 - 选型建议”的顺序展开。目标是让读者能自己写出一个带计数器的循环排序能通过运行结果判断复杂度量级也能在社区讨论中快速识别类似 O(n log n) 的错误结论。最后还会给出一份可复用的复杂度分析自检清单用来排查其他算法中相似的坑。2. 循环排序的核心机制置换环2.1 从“把元素放到它该去的位置”开始排序的本质是让每个元素到达它的最终位置。对升序排序来说一个元素 x 的目标位置可以通过统计数组中有多少个元素小于 x 来计算如果有 k 个元素小于 xx 就应该落在下标 k从 0 开始。这是计数排序、桶排序等多种算法的基础思想循环排序也使用了这个规则。假设当前待处理元素是 item它对应的起点下标是 cs。算法会扫描 cs 右侧的所有元素数出有多少个元素小于 item。这个数量记为 lessCount那么 item 的目标位置 pos 就是 cs lessCount。道理很简单左侧的 cs 个位置已经属于前面的较小元素右侧又有 lessCount 个元素比 item 小所以 item 在整个有序序列中的排名就是 cs lessCount。只看这一步复杂度还不算高。麻烦在于item 被放到 pos 后原本占据 pos 的元素会被替换出来成为新的 item这个新 item 又需要重新扫描它右侧的所有元素来确定自己的目标位置。这个过程不断延伸直到回到起点 cs形成一个闭环。这个闭环就是排序中“置换”的环。2.2 环的识别与移动举一个具体例子。数组是[3, 5, 2, 1, 4]目标是升序排列。升序结果应该是[1, 2, 3, 4, 5]。下面用下标 0 作为起点下标 0 的元素是 3它应该落在下标 2。下标 2 的元素是 2它应该落在下标 1。下标 1 的元素是 5它应该落在下标 4。下标 4 的元素是 4它应该落在下标 3。下标 3 的元素是 1它应该落在下标 0。于是形成了闭环0 - 2 - 1 - 4 - 3 - 0循环排序要做的就是沿着这个环把每个元素送到它应该去的位置。这个环的长度是 5等于数组长度因此整个数组处于一个环中。有些数组会包含多个环每个环独立处理有些位置上的元素已经就位它们可以看作是长度为 1 的环不需要移动。2.3 一次完整排序的步骤演示仍以[3, 5, 2, 1, 4]为例从下标 0 开始令 item arr[0] 3计算目标位置 pos 2。交换 item 与 arr[2]得到 item 2arr[2] 3。item 的目标位置是下标 1交换 item 与 arr[1]得到 item 5arr[1] 2。item 的目标位置是下标 4交换 item 与 arr[4]得到 item 4arr[4] 5。item 的目标位置是下标 3交换 item 与 arr[3]得到 item 1arr[3] 4。item 的目标位置回到下标 0把 item 1 放回 arr[0]。完成后的数组是[1, 2, 3, 4, 5]。整个过程只涉及一次置换环元素移动次数不多但为了确定每个 item 的目标位置算法在每次循环中都扫描了右侧子数组。第一次扫描比较了 4 次第二次扫描比较了 3 次第三次 2 次第四次 1 次累计就是 4 3 2 1 10 次比较。这个数字正好等于n(n-1)/2也就是 O(n^2) 的来源。2.4 为什么说它是“写优化”排序循环排序的核心价值在于它把数组元素移动到最终位置的次数控制在线性级别。对于随机数组插入排序在最坏情况下可能进行 O(n^2) 次移动循环排序正常实现下最多移动 O(n) 次。因此当“写”比“读”和“比较”昂贵得多时循环排序会变得有吸引力。例如在 EEPROM 或某些 Flash 存储设备上擦写次数有寿命限制。排序一个较小的关键数据块时选择写次数更少的算法可以减少磨损。在普通内存里写和读的代价差异不大O(n^2) 的比较次数就会成为主要瓶颈所以它很少用于通用排序。这里需要记住一个原则写优化是循环排序的亮点但写优化不能直接等于时间复杂度更低。3. 严格推导循环排序的时间复杂度3.1 算法分析中要明确基本操作分析排序算法复杂度前首先要确定“基本操作”是什么。在基于比较的排序算法中通常把元素之间的比较次数作为基本操作。原因有两个一是比较直接决定排序逻辑二是元素交换、赋值等操作的数量可以与比较次数用一个常数因子联系起来。循环排序恰恰