排序算法之：最小交换次数排序（Minimum Swaps to Sort）的图论模型与环分解优化

题目描述
给定一个包含 n 个不同元素的数组，每个元素均为整数。每次操作允许交换任意两个元素的位置。问题要求计算出将数组排序所需的最小交换次数。例如，数组 [7, 1, 3, 2, 4, 5, 6] 排序所需的最小交换次数为 5。

解题过程

1. 问题分析
   直接通过模拟交换过程求解最小交换次数较为困难。关键在于发现：若将数组视为一个置换（每个元素映射到其排序后应在的位置），那么该置换可以分解为若干个不相交的环（cycle）。每个环内的元素通过交换可以归位，且最小交换次数与环的大小密切相关。

2. 图论建模

   • 将数组索引及其对应的值构建成一个有向图：每个索引 i 指向其值在排序后应处的正确位置 j。
   • 例如，数组 [7, 1, 3, 2, 4, 5, 6] 排序后为 [1, 2, 3, 4, 5, 6, 7]。
     索引 0（值为 7）应指向排序后 7 的位置（索引 6），索引 1（值为 1）指向排序后 1 的位置（索引 0），依此类推，形成边：0→6, 1→0, 2→2, 3→1, 4→4, 5→5, 6→3。
   • 该图会分解为多个环：如 (0→6→3→1→0) 和 (2→2)、(4→4)、(5→5)。

3. 环分解与交换次数公式

   • 对于每个长度为 k 的环（即环中包含 k 个元素），只需进行 k-1 次交换即可将环内所有元素归位。
   • 总最小交换次数 = Σ(每个环的大小 - 1)。
   • 上例中，环 (0,6,3,1) 大小为 4，需 3 次交换；环 (2)、(4)、(5) 大小为 1，需 0 次交换。总次数 = 3。

4. 算法步骤

   • 步骤 1：创建数组的排序副本，记录每个值在排序后的正确位置（可通过哈希表存储值到索引的映射）。
   • 步骤 2：初始化一个访问标记数组，记录每个索引是否已被处理。
   • 步骤 3：遍历每个索引 i：
     • 若 i 已被访问或当前值已在正确位置（即 i 指向自身），跳过。
     • 否则，从 i 开始追踪环：沿着边 i → correct_pos[arr[i]] → ... 直到回到 i，记录环中节点数 count。
     • 将交换次数增加 count - 1。
   • 步骤 4：返回总交换次数。

5. 示例演算
   数组 arr = [7, 1, 3, 2, 4, 5, 6]：

   • 排序后为 [1, 2, 3, 4, 5, 6, 7]，建立值到位置的映射：{1:0, 2:1, 3:2, 4:3, 5:4, 6:5, 7:6}。
   • 从索引 0 开始：
     • 当前值 7 的正确位置是 6，从 0→6；
     • 索引 6 的值 6 的正确位置是 5，从 6→5；
     • 索引 5 的值 5 的正确位置是 4，从 5→4；
     • 索引 4 的值 4 的正确位置是 3，从 4→3；
     • 索引 3 的值 2 的正确位置是 1，从 3→1；
     • 索引 1 的值 1 的正确位置是 0，形成环 (0→6→5→4→3→1→0)，大小为 6，交换次数 += 5。
   • 剩余索引 2 已指向自身，无需交换。总次数 = 5。

6. 复杂度与优化

   • 时间复杂度 O(n)：每个索引仅被访问一次。
   • 空间复杂度 O(n)：用于存储位置映射和访问标记。
   • 优化点：可在追踪环时直接标记已访问节点，避免重复处理。

关键理解
最小交换次数问题通过图论建模转化为环分解问题，利用“环大小减一”的求和公式高效求解，避免了贪心交换的局部最优陷阱。