如果你今天在某论坛看到有人发布“循环排序”并且给它的时间复杂度标成了 O(n log n)先别急着把这个结论记到笔记里。标准循环排序Cycle Sort的通用实现时间复杂度是 O(n²)不是 O(n log n)。这类说法通常来自特殊场景、特化实现或者是在分析时漏算了某个内层循环。循环排序真正值得关注的点是它能把写入移动次数压到 O(n) 级别同时做到原地排序、空间复杂度 O(1)。本文不打算只背结论而是把循环排序从原理、代码、复杂度推导到实测验证完整过一遍顺便讲清楚为什么有人会把它误判成 O(n log n)。1. 先搞清楚循环排序在做什么再讨论复杂度1.1 循环排序的核心思想不是“每轮选最小”而是“把每个环转到位”排序算法的常见思路有很多冒泡靠相邻交换插入靠不断前插快速排序靠分治和划分。循环排序的思路完全不同它先认为数组可以拆成若干条“循环链”然后沿着链把元素搬到正确位置。什么叫循环链举个例子数组[3, 1, 5, 4, 2]要升序排序。先看位置 0 上的元素 3在完整的有序数组里3 应该排在 1 和 2 后面所以它的正确位置是下标 2。把 3 放到位置 2原来位置 2 上的 5 被挤出来。再看 5它应该排在 3、1、4、2 后面正确位置是下标 4。把 5 放到位置 4原来位置 4 上的 2 被挤出来。2 的正确位置是下标 1把 2 放过去1 被挤出来。1 应该回到下标 0但位置 0 上的元素已经被移走了这时一个“环”就转完了。这个过程中元素不是通过两两比较一个个“冒”上去而是一整条循环链上的元素依次归位。理解这一点很重要因为循环排序的复杂度分析关键就看这个环旋转过程到底做了多少次操作。1.2 标准实现的完整代码和逐行解释下面给一个标准实现使用 Python 描述。为了处理重复元素代码里加了跳过重复值的逻辑。def cycle_sort(arr): n len(arr) for start in range(n - 1): item arr[start] pos start # 统计剩余元素中比 item 小的数量确定 item 的正确位置 for i in range(start 1, n): if arr[i] item: pos 1 # 如果已经在正确位置直接跳过 if pos start: continue # 跳过重复元素避免把相同值放到错误位置 while pos n and item arr[pos]: pos 1 # 把 item 写入 pos并取出被替换的元素继续处理 arr[pos], item item, arr[pos] # 继续处理同一个环上的元素直到回到 start while pos ! start: pos start for i in range(start 1, n): if arr[i] item: pos 1 while pos n and item arr[pos]: pos 1 arr[pos], item item, arr[pos] return arr这段代码看起来不长但有几个细节值得注意。外层for start in range(n - 1)负责选择每个起点。最后一个元素不需要再处理因为前面 n-1 个元素归位后最后一个位置自动正确。内层第一次for是在数“当前元素后面有多少个比它小”。为什么要数而不是直接交换因为循环排序假设元素最终应该按从小到大的顺序落在某个位置而“小于当前元素的个数”就是它在有序数组中的排名。这样找位置不需要额外空间代价是要线性扫描。while pos ! start这段是环旋转的核心。很多人误判复杂度时就是把这部分忽略了以为每个元素只会被处理一次。实际上当一个元素被放到正确位置后被替换出来的元素还要继续找位置可能再触发一次完整扫描。C 代码也短关键逻辑一样#include vector #include algorithm void cycleSort(std::vectorint arr) { int n arr.size(); for (int start 0; start n - 1; start) { int item arr[start]; int pos start; for (int i start 1; i n; i) { if (arr[i] item) pos; } if (pos start) continue; while (item arr[pos]) pos; std::swap(item, arr[pos]); while (pos ! start) { pos start; for (int i start 1; i n; i) { if (arr[i] item) pos; } while (item arr[pos]) pos; std::swap(item, arr[pos]); } } }std::swap(item, arr[pos])的结果是item 变成原来在 pos 上的元素然后继续循环。交换操作也可以写成异或版本三个异或完成交换时间复杂度 O(1)。注意“异或交换”只是交换技巧不会改变排序本身的总复杂度。2. 标准循环排序的时间复杂度为什么是 O(n²)2.