NOIP 提高组初赛 · NOIP 2008 提高组初赛试题 第 5 题

将数组 $\{8, 23, 4, 16, 77, -5, 53, 100\}$ 中的元素按从大到小的顺序排列，每次可以交换任意两个元素，最少需要交换（ ）次。

拿到题先别急着写代码，脑子里过一遍排序后的样子，然后像玩连连看一样，把每个数在目标位置找一圈，数数看形成了几个闭环，这就是解题的钥匙。

最容易栽跟头的就是死记硬背‘最少交换次数等于 n 减环数’这个公式，却忘了去验证环到底是怎么形成的。比如这道题，如果不按从大到小排好序，随便找个参照系，环的划分就会全错，算出来的次数自然也就离谱。还有同学会把负数和正数混在一起乱套，或者在追踪环的时候，把已经归位的数又重复算进下一个环，导致环数虚低，次数虚高。记住，每一步都得对着‘目标序列’来，不能凭感觉。

考点直击：这道题考的是排序基础中的“置换环分解”思想，属于信息学竞赛里那种看似简单、实则容易掉进陷阱的经典题型。命题人故意给了一个包含负数的数组，还要求“从大到小”排，就是想看看你是不是真的在按规则找环，而不是机械套公式。在历年 NOIP 和 CSP 初赛中，这类“最少交换次数”的题目每年都有，从普及组到提高组都不少见，是考察逻辑推理和细心程度的好素材。

怎么想：首先，目标很明确——把原数组变成降序：[100, 77, 53, 23, 16, 8, 4, -5]。接下来，咱们用“循环分解法”。想象每个位置上的数都想去它应该在的“家”（目标位置），如果它不在家，就去找那个“家”里本该是谁，那个人再去他的家……这样一圈下来，要么回到起点，要么形成一个大环。每一个环，只要长度是 k，最少就需要 k-1 次交换才能把环里所有数归位。总交换次数就是所有环的 (k-1) 相加，也就是“元素总数减去环的个数”。

一步步推： 1. 从第一个位置（值 8）开始，它在目标序列里应该在第 6 位（值 8 的位置）。第 6 位现在是谁？是 -5。-5 在目标序列里应该在最后一位（第 8 位）。第 8 位是谁？是 100。100 在目标序列里应该在第一位。第一位现在是谁？是 8。 2. 看！8 → -5 → 100 → 8，这三个数形成了一个闭环。环长 3，需要 3-1=2 次交换。 3. 接着看还没动的数。第二个位置是 23，它在目标序列里应该在第 4 位。第 4 位现在是谁？是 77。77 应该在第 1 位，但第 1 位已经被 8 占着（属于上一环），所以 77 只能去找它该去的位置……等等，我们得按目标序列的索引来追踪。23 的目标索引是 3（从 0 开始计数），位置 3 现在是 77；77 的目标索引是 0，位置 0 现在是 8（已归位）；8 的目标索引是 5，位置 5 现在是 16；16 的目标索引是 4，位置 4 现在是 53；53 的目标索引是 2，位置 2 现在是 4；4 的目标索引是 6，位置 6 现在是 -5（已归位）。 4. 重新梳理：23 → 77 → 16 → 4 → 23，这四个数形成了一个闭环。环长 4，需要 4-1=3 次交换。 5. 剩下的数：53 和 100 已经在各自的位置上了（53 在目标第 2 位，100 在目标第 0 位），它们各自构成长度为 1 的环，不需要交换。

计算结果：两个非平凡环，长度分别为 3 和 4，交换次数 = (3-1) + (4-1) = 2 + 3 = 5 次。

避坑指南：千万别只数“有几个数没在正确位置”，然后简单除以 2 或者减个常数，那样绝对会错。这道题如果不小心把负数 -5 和 100 搞混，或者在追踪环时把已经归位的数又拉进来，很容易算出 6 或 7 次，正好对应选项 C 和 D，这是命题人埋下的两个大坑。记住，环的划分必须严格基于“目标序列的索引”，一步步追，不能跳步。

考频与趋势：从题库数据看，“排序基础”是绝对的高频考点，249 题覆盖 9 个级别，其中 NOIP 提高组初赛就考了 12 次，CSP 提高级 9 次，普及组 6 次。近年趋势非常明显：2023 年突然爆发式增长到 22 题，2024 年更是飙到 51 题，2025 年继续增加到 57 题，2026 年维持在 50 题的高位。这说明这类题目已经从“偶尔出现”变成“必考常客”，而且出题人越来越喜欢用稍微复杂一点的数组（比如带负数、乱序严重）来增加区分度。

预测：基于这种逐年递增且高位震荡的趋势，未来几年（2027-2030）这类“最少交换次数”或“排序置换环”的题目大概率会继续保持高频，甚至可能出现在 CSP-J/S 的复赛模拟或 GESP 八级以上的考题中。命题人可能会进一步增加干扰项，比如问“如果允许交换相邻元素，最少需要多少次？”或者“给定一个序列，判断是否能通过有限次交换变成升序？”总之，核心思路不变，但包装形式会更花哨。现在就把这个环分解法练熟，以后遇到再复杂的排序题，都能一眼看穿本质。