Cyclic Sort 简明易懂：学习基础及工作原理
I’m happy to translate the article for you, but I’ll need the text you’d like translated. Could you please paste the content (or the portion you want translated) here? I’ll keep the source link, formatting, and any code blocks exactly as you provide them.
Source: …
循环排序
循环排序 是一种 原地（in‑place）且 不稳定（unstable）的排序算法，专门用于对元素取值在已知范围内的数组进行排序，例如从 1 到 N。
它是如何工作的？
考虑下面这个我们想要按升序排序的数组：
算法会反复选取一个元素并把它放到 正确的索引 上。
它从第一个元素（索引 0）开始。
-
选取第一个元素 – 5
它的正确索引是 4（因为数值 5 应该位于位置 4）。
-
将 5 与索引 4 处的元素（值 2）交换
-
检查索引 0 处的新元素 – 现在是 2
2 应该在索引 1，因而 不在 正确位置。控制变量 不前进。
-
将 2 与索引 1 处的元素（值 4）交换
-
现在索引 0 处的元素是 4
4 应该在索引 3 → 位置不对。
-
将 4 与索引 3 处的元素（值 3）交换
-
现在索引 0 处的元素是 3
3 应该在索引 2 → 仍然不对。
-
将 3 与索引 2 处的元素（值 1）交换
-
现在索引 0 处的元素是 1 – 已经在正确位置。
算法将控制变量递增到下一个索引（1），并重复同样的过程。(图片 URL 为简洁起见已截断)
该过程会持续进行，直至每个元素都位于其对应的索引，最终得到一个已排序的数组。
关键点
| 属性 | 描述 |
|---|---|
| 原地 | 不需要额外数组；交换在原数组内部进行。 |
| 不稳定 | 相等元素的相对顺序不保留（尽管经典用例中的值是不同的）。 |
| 时间复杂度 | O(N) – 每个元素最多被移动一次到其正确位置。 |
| 空间复杂度 | O(1) – 只使用少量辅助变量。 |
| 理想输入 | 包含整数 1 … N 的数组（或任何可以映射到索引的连续范围）。 |
何时使用循环排序
- 当你事先知道数值范围时（例如，
1..N的全排列）。 - 当你需要线性时间排序且额外空间为 O(1) 时。
- 适用于诸如“寻找缺失数字”“寻找重复项”或“将每个元素放置到其正确索引”之类的问题。
💡 元素的 正确索引 为其 值 − 1，前提是数组中的数字范围是 1 到 N。
空间复杂度
由于该算法是原地排序算法，它不需要任何辅助空间。因此，其空间复杂度为 O(1).
时间复杂度
我们有两种情况：最坏情况和最佳情况。
最坏情况
当数组中每个数字都在错误的位置（数组范围已知，例如 1 到 N）时，就会出现最坏情况。
上面使用的示例数组是 [5, 4, 1 (已截断).