企业官网建设流程全解析

论坛上有人发帖说“循环排序”这个算法的时间复杂度是 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 = 1

1 的正确位置是0，也就是本轮循环链的起点。回到起点后，这一条循环链处理完毕。最终数组变成：

[1, 2, 3]

整个过程里，每个元素只被写入一次。这个“沿链搬家，回到起点终止”的思路，就是循环排序的名字由来。

循环排序的流程可以用下面几步概括：

1. 从下标start开始，取出元素item。
2. 在start+1到n-1范围内统计比item小的元素个数，得到pos。
3. 如果pos == start，说明item已经在正确位置，跳过本轮。
4. 如果数组中有重复元素，跳过所有与item相等的目标位置。
5. 把item放到pos，把arr[pos]取出来作为新的item。
6. 重复步骤 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 次定位：统计 start+1 到 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 远小于 n=5，符合 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(f"n={n}, 写入次数={writes}, 比较次数={comparisons}")

运行后，写入次数大致在 n 到 2n 之间，而比较次数会从几千迅速增长到几万、十几万。这个对比很直观：写入确实少，但“找位置”的成本一点也不便宜。

如果运行结果和预期不符，第一步先检查重复元素处理部分。最常见的 bug 是while item == arr[pos]时没有加pos < n判断，当后半段全是相同元素时，pos 会越界。第二步检查循环链的退出条件，确保pos回到start后会正常跳出，不会出现死循环。

6. 常见排序算法对比：循环排序处在什么位置

为了说清楚循环排序的定位，我把常见排序算法的主要指标放在一张表里对比：

从表格可以看出，循环排序在时间复杂度上和冒泡、选择排序处于同一档，都不适合大规模数据排序。它的差异化优势只在一项：写入次数是排序算法中最低之一。

选择排序虽然也是每轮最多交换一次，但交换两个元素意味着两次写入。循环排序在循环链上搬运时，每个元素通常只写一次，这条链上参与搬运的元素越多，节省的写入量越明显。

7. 循环排序适合哪些场景：真实项目里的定位

循环排序不该出现在通用排序模块里，但它在特定场景下确实有价值。

第一类场景是小型嵌入式系统。如果数组长度只有几十或几百，同时使用的存储器写入寿命有限，比如 EEPROM 或 Flash，循环排序的“少写入”特性可以直接减少擦写次数，延长器件寿命。这时比较次数的开销相对可以接受。

第二类场景是对“稳定性”没有要求的小数组排序。循环排序是不稳定排序，但如果业务不关心相同元素的相对顺序，写入次数少反而能减少数据搬移带来的缓存失效。

第三类场景是算法教学和面试讨论。循环排序是理解“排序成本有多维度”的好例子：时间复杂度、空间复杂度、写入次数、比较次数，这些指标可以独立优化，而循环排序拿“比较次数”换“写入次数”。

反过来，循环排序不适合大规模排序，不适合对稳定性有要求的场景，也不适合数组元素已经近乎有序的场景。插入排序在近乎有序的数组上几乎不需要搬移数据，而循环排序无论数组是否有序，都要做完整的定位扫描。

在实际项目中，更推荐的做法是：把循环排序封装成一个独立的小工具，只在确认“写入成本远高于比较成本”的模块中使用。不要试图用它替代标准库的排序函数。

8. 常见问题与误区排查

很多初学者接触循环排序时，容易出现下面这些问题：

还有一个容易忽略的点：循环排序对数组元素的类型有要求。它依赖“小于”比较来定位，所以对于浮点数中的 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²)。

如果要用一句话总结循环排序的价值，那就是：它不是一个“变快了”的排序算法，而是一个“写得更少”的排序算法。你在实际项目里可以不用它，但最好理解它背后的代价交换逻辑。想验证的话，跑一篇带计数功能的实现，把不同规模数组的比较次数和写入次数打印出来，复杂度差异会非常直观。