企业官网建设流程全解析

前一段时间，我在技术论坛上刷到一个帖子，标题大概是：“我写了一个循环排序，时间复杂度 O(n log n)，比快排还稳。”评论区很快吵起来。有人直接说：循环排序不是 O(n^2) 吗？也有人贴出 LeetCode 上的循环排序解法，说那明明是 O(n)。还有人分析半天，最后发现大家说的“循环排序”压根不是同一个算法。

我当时的第一反应是：又一个把“复杂度”挂在嘴边、但没看清定义的人。可等我认真看完楼主贴出的代码和后面的讨论，发现事情没那么简单。这个争议恰好暴露了算法分析里最容易被忽略的一个问题：当我们说一个排序算法的时间复杂度是 O(n log n) 时，到底在数什么操作？是元素比较次数，是数组写入次数，还是 CPU 上的墙钟时间？

这篇文章就借“循环排序”这个案例，把这笔账算清楚。顺便也会给出一个判断循环排序复杂度、验证复杂度结论的可执行路径。标题里那句“结果发现时间复杂度为 O(n log n)”，我会拆开讲：它可能对，也可能只是说了一半。

1. 先厘清：循环排序到底在排什么

1.1 两种都叫“循环排序”的算法

网上搜“循环排序”，至少能看到两种完全不同的东西。

第一种是 LeetCode 里经常出现的 Cyclic Sort，中文常译作“循环排序”。它解决的问题很特殊：给你一个长度为 n 的数组，里面是 1 到 n 的整数，让你原地排序。思路非常简单：每个元素都对应一个“正确索引”，值等于索引加一。如果当前元素不在正确位置，就把它换过去；换过来的元素如果也不对，就继续换，直到当前位置正确。这个算法的时间复杂度是 O(n)，空间复杂度 O(1)。

第二种是 Wiki 上收录的 Cycle Sort，中文同样被译作“循环排序”或“圈排序”。它适用于任意可比较元素的数组，核心思想是：遍历数组时，把每个元素放到它最终应该在的位置，但不会像选择排序那样每次交换两个元素，而是沿着一个“环”做旋转，尽可能少写入。

这两种算法都叫循环排序，但前提、流程、复杂度完全不同。论坛帖子的争论，很大程度就是从这里开始的。

1.2 核心思想：把数组看成若干个环

想理解循环排序，先理解“环”这个比喻。

假设有一个数组[3, 1, 2]，我们给每个元素标上它“最终应该去的位置”。值3在排序后应该去索引2，值1应该去索引0，值2应该去索引1。如果你把这些映射关系连起来，会得到一个环：索引0 -> 索引2 -> 索引1 -> 索引0。

Cycle Sort 的做法是：先选定一个起点位置，然后不断把合适元素搬进来，再把被挤出去的元素送到它该去的下一个位置，直到回到起点。一个包含 k 个元素的环，只需要 k+1 次写入，就能把整个环里所有元素放到正确位置。

如果你画过排序算法的流程图，会发现循环排序的流程图里最显眼的，就是这个环。这也是它名字的由来。

1.3 能减少写入，但代价是查找

为什么明明可以用选择排序解决，还要绕环旋转？因为选择排序每次交换都要赋两次值，很多情况下这些“写入”是不必要的。Cycle Sort 刻意把写入次数压到理论最低：最坏情况下，一个 n 元素的数组，写入次数约为 2n 次。

但省写入是有代价的。为了知道某个元素应去哪个位置，你需要比较它和后面所有元素的大小，从而数出“到底有几个元素比它小”。这是一个线性扫描的过程。标准 Cycle Sort 里，每个位置都要扫描一遍剩余数组，所以比较次数会达到 O(n^2)。

这就为后面那个“O(n log n)”的争议埋下了伏笔：写入次数是 O(n)，比较次数是 O(n^2)，那这个算法的“时间复杂度”到底该算哪个？

2. 为什么有人会说循环排序的时间复杂度是 O(n log n)

2.1 误读一：把循环排序当成快速排序家族

先排除一种最不值得争的情况。很多初学者看到“循环”两个字，会下意识觉得它和“递归”、“分治”有关系，然后联想到快速排序、归并排序的平均 O(n log n)。

但实际上，标准 Cycle Sort 并没有分治结构，它更像是选择排序的变体。选择排序无论最好最坏，比较次数都是 O(n^2)。Cycle Sort 在比较层面也一样，不会因为名字里有“循环”就自动变成 O(n log n)。

如果一个人只是说“循环排序是 O(n log n)”，没有任何实现细节，那这个结论大概率站不住脚。

2.2 误读二：只统计比较次数，忽略写入和移动

真正的争议出现在有人给了具体实现之后。论坛里的有些实现，看起来确实更像“二分插入排序”：假设数组的前半部分已经有序，每次拿一个新的元素，用二分查找找到它应该插入的位置，然后把一段元素循环移动，最后把新元素放到正确位置。

这个思路里，比较次数很好算。每插入一个元素，二分查找需要 O(log n) 次比较，插入 n 个元素，总比较次数是 O(n log n)。如果你只在代码里数“比较了多少次”，最终统计结果确实会呈现 n log n 的增长趋势。

问题出在“写入”和“移动”上。在普通数组里做循环插入，意味着插入位置后面的所有元素都要挪一位。每次插入最坏要移动 O(n) 个元素，n 次插入之后，移动次数是 O(n^2)。如果你把比较、写入、移动、循环变量更新全部算进“总操作数”，这个算法并没有跑到 O(n log n)。

所以“循环排序的时间复杂度是 O(n log n)”这个说法，只有在一种特定口径下才成立：只统计比较次数，并且使用二分查找来定位插入点。一旦把数组写入和元素移动算进来，它依然是 O(n^2)，或者说，至少不能简单地说它是 O(n log n)。

2.3 如果要求严格，O(n log n) 的说法成立吗

现在可以给出一个更严谨的判断了。

• 标准 Cycle Sort：比较 O(n^2)，写入 O(n)。如果你把所有操作合起来看，时间复杂度可以写成 O(n^2)。
• 基于二分插入的循环排序变体：比较 O(n log n)，但数组移动仍然 O(n^2)。严格说，总时间复杂度还是 O(n^2)。
• 如果额外使用链表、块状数组或平衡树来避免大规模移动，移动量可以优化，但空间复杂度会上升，而且它已经不是经典意义上的“原地循环排序”了。

标题里说的“结果发现它的时间复杂度为 O(n log n)”，更准确的理解是：这个实现里的元素比较次数达到了 O(n log n)。它没有打破比较排序 O(n log n) 的下界，也没有超过快速排序，只是把复杂度统计里最显眼的那一块优化掉了。

3. 手写一个循环排序，并验证复杂度

3.1 标准 Cycle Sort：先把流程跑通

下面给出一个标准 Cycle Sort 的 Python 实现。这段代码的用途是演示流程，而不是性能最优。它会在数组原地上操作，并返回总写入次数。

def cycle_sort(arr): writes = 0 n = len(arr) for start in range(n - 1): item = arr[start] # 找出 item 最终应该在的位置 pos = start for i in range(start + 1, n): if arr[i] < item: pos += 1 # 如果 item 已经在正确位置，跳过 if pos == start: continue # 跳过重复元素 while item == arr[pos]: pos += 1 # 把 item 放进去，并取出被替换的元素 arr[pos], item = item, arr[pos] writes += 1 # 继续处理被挤出来的元素，直到回到起点 while pos != start: pos = start for i in range(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

这段代码最内层的循环是“扫描start+1到n-1的元素，统计小于item的数量”。不管输入是什么，这个扫描都会执行。所以比较次数非常稳定地落在 O(n^2)。

3.2 Cyclic Sort：值域受限时的 O(n) 版本

如果你遇到的是[1, n]排列这种特殊输入，事情会简单很多。下面的版本才是刷题常见的“循环排序”：

def cyclic_sort(nums): i = 0 while i < len(nums): correct_index = nums[i] - 1 if nums[i] != nums[correct_index]: nums[i], nums[correct_index] = nums[correct_index], nums[i] else: i += 1 return nums

这个版本为什么能到 O(n)？因为每个元素最多被交换一次。它利用的是“值本身等于目标位置索引”这个强约束，而不是通用比较排序。如果你把这段代码也叫做循环排序，那它的复杂度确实是 O(n)。

这也是社区里最经典的认知冲突：两个人都在说循环排序，一个人说的是通用 Cycle Sort，一个人说的是值域受限的 Cyclic Sort，复杂度结论自然对不上。

3.3 用计数器验证比较次数

复杂度分析不能只靠直觉，尤其是遇到“看起来是 O(n log n)”的争议时，最好的办法是直接打点统计。

一个简单的思路：用一个包装类记录数组比较次数。

import random class CountingList: def __init__(self, data): self.data = data self.cmp_count = 0 def __len__(self): return len(self.data) def __lt__(self, other): self.cmp_count += 1 return self.data < other.data

然后分别对 n=100、200、400、800 的随机数组运行标准 Cycle Sort，记录比较次数。

你会看到这样的趋势：n 翻一倍，比较次数大约翻四倍。这正是 O(n^2) 的特征。如果哪个变体在同样的 n 翻倍测试下，比较次数只翻两倍多一些，那它比较这一项才接近 O(n log n)。

建议在验证时把 n 取到 2000 以上，不然随机抖动会掩盖增长趋势。同时，尽量多跑几轮取平均，避免刚好遇到特殊顺序。

3.4 二分优化版：写一个能到 O(n log n) 比较的变体

如果你真想和论坛帖子里的人一样，把比较次数降到 O(n log n)，思路可以改成这样：

1. 假设arr[0:start]已经有序。 2. 用二分查找在arr[0:start]中找到arr[start]应该插入的位置pos。 3. 把arr[pos:start+1]循环右移一位，让arr[start]落到arr[pos]。 4. start += 1，重复。

这个步骤很像“二分插入排序”，但它确实用到了循环移动，所以有人把它也叫作“循环排序”。比较次数可以从 O(n^2) 降到 O(n log n)，但数组移动次数依然是 O(n^2)。如果面试官问“这个排序最坏时间复杂度是多少”，你需要回答 O(n^2)，因为比较不是唯一开销。

如果你用链表或块状数组来避免大段移动，那写入和移动也可以优化，但空间复杂度会从 O(1) 变成 O(n)，这已经跳出循环排序原本的适用范围了。

4. 循环排序真正适合的场景，以及容易踩的坑

4.1 什么时候该用循环排序

循环排序最核心的价值不是快，而是“少写”。所以以下场景值得优先考虑：

• 写入代价极高：比如某些嵌入式 Flash 存储、EEPROM 磨损均衡场景，每次写操作都有寿命损耗。循环排序能把写入次数压到理论最低，哪怕比较次数多一点也可以接受。
• 数组元素是很大的对象，交换代价很高：如果数组里存的是巨型结构体，每次交换都要拷贝整个对象，那么减少交换/写入次数往往比减少比较次数更划算。
• 输入是 1 到 n 的排列：这时用 Cyclic Sort，本身就是 O(n)，可以直接找缺失值、重复值，是最好用的原地算法。

在普通业务代码里，如果你要排序一个 100 万元素的普通数组，循环排序大概率不是首选。因为现代 CPU 上比较和访问的代价远比你以为的低，而快速排序或内置排序已经在缓存、分支预测、并行度上优化到极限。

4.2 什么时候别用循环排序

需要明确写出边界，避免读者把“少写”理解为“全场景最优”：

• 大规模随机数据排序：标准 Cycle Sort 比较 O(n^2)，即使比较开销不低，在 n 大时也会明显变慢。
• 要求稳定排序：Cycle Sort 是不稳定的。如果数组里有大量相同键值的元素，排序后它们的相对顺序不保证。
• 重复元素很多：虽然标准实现里跳过了重复元素，但重复元素会让定位逻辑变复杂，最坏情况下比较次数不会变少，移动次数却可能增加。
• 不需要原地排序、内存充裕：归并排序稳定且 O(n log n)，更实用。

4.3 排查：判断一个陌生排序算法复杂度的三问框架

以后再看到有人说“某某排序是 O(n log n)”，可以用下面这个框架快速判断：

1. 核心操作是什么？
   是元素比较，是交换，是写入，是把某个元素挪到临时变量再放回去？不同操作对应的复杂度可能完全不同。

2. 最坏输入是什么？
   对普通排序算法，最坏情况可能是逆序、顺序、大量重复元素。对循环排序类，最坏情况通常和“需要形成多少个环”以及“每次定位要扫描多少元素”有关。

3. 复杂度口径是什么？
   是说比较次数，是说写入次数，还是说包含了赋值、循环、函数调用的总运行时间？讨论复杂度时，先统一口径，再谈结论。

4.4 落地建议：先跑通、再压测、后优化

如果你想在一个真实项目里尝试循环排序，我建议按这个顺序执行：

1. 先用一个小数组跑通，确认排序结果正确，写入次数符合预期。
2. 再用边界测试：空数组、单元素、逆序、大量重复元素、已排序数组。循环排序很容易在重复元素处理上出 bug，尤其是跳过重复值的逻辑。
3. 最后做增长曲线验证：取 n=1000、2000、4000、8000，分别记录排序耗时或核心操作次数。如果耗时增长速度接近 n^2，那就说明当前实现对性能并不友好，不适合无脑推广到生产环境。

如果只是刷题或学习，写一个标准 Cycle Sort 练手没问题。但真的进入生产代码之前，多数时候直接调用标准库里的排序函数，比自己造轮子更可靠。这不是否定循环排序，而是知道它的价值到底在哪。

回到那个论坛帖子：楼主没有完全说错，他只是没说完整。循环排序的“比较次数”确实可以做到 O(n log n)，但当他把“比较次数”包装成“时间复杂度”时，这就成了一个很容易误导人的表达。一次看似激烈的算法争论，最后能留下的不是谁对谁错，而是一个更底层的问题意识：当人们谈论复杂度时，他们到底在计量什么，在省略什么，又在为哪个场景做取舍。

如果下次再看到类似标题，我建议你先别急着站队。认真问一句：“这里的 O(n log n)，是在数比较，还是在数写入，还是在数墙钟时间？”也许，这比争论本身更有价值。