排序算法之：基于最小交换次数将数组排序的循环图模型及其扩展变体

题目描述

给定一个长度为 n 的整数数组 arr，你可以对数组中的任意两个元素进行交换。目标是通过最少的交换次数，使得数组变为非降序排列（即升序排序）。返回最小的交换次数。

示例 1：

输入: arr = [7, 1, 3, 2, 4, 5, 6]
输出: 5
解释：
一种最优交换顺序为：
(7,1) -> [1,7,3,2,4,5,6]
(7,3) -> [1,3,7,2,4,5,6]
(7,2) -> [1,3,2,7,4,5,6]
(2,4) -> [1,3,4,7,2,5,6]? 这里注意，实际上示例中的过程是将元素逐步归位，最终得到 [1,2,3,4,5,6,7] 共需 5 次交换。

示例 2：

输入: arr = [4, 3, 2, 1]
输出: 2
解释：
交换 (4,1) -> [1,3,2,4]
交换 (3,2) -> [1,2,3,4]

问题本质：这是一个经典的“最少交换次数排序”问题，我们可以借助循环图（Cycle Graph）模型将其转化为图论问题高效求解。

解题过程详解

步骤 1：理解“最少交换次数”与“元素最终位置”的关系

首先，我们将原数组升序排列，得到一个目标数组（即排序后的数组）。

关键观察：
对于每个元素，我们知道它在最终有序数组中的目标位置。
例如，数组 [7, 1, 3, 2, 4, 5, 6] 排序后为 [1, 2, 3, 4, 5, 6, 7]。
我们需要建立映射：原数组的每个值 → 它的目标索引。

但是，数组中可能存在重复元素吗？
原题通常假设数组元素是互不相同的（distinct）。这是本解法的重要前提。如果有重复元素，问题会更复杂，我们稍后会讨论扩展。

步骤 2：建立“索引-值”映射并构建循环

我们先明确一个重要的图模型概念：

• 将数组的下标（0 ~ n-1）看作图的节点。
• 对于每个下标 i，我们计算它的值 arr[i] 在排序后数组中应该位于哪个下标 j。我们建立一条有向边 i → j，表示“当前在位置 i 的元素应该被放到位置 j 去”。

因为排序后数组是原数组值的一个排列，且元素互不相同，所以：

1. 每个节点 i 的出度为 1（只有一个目标位置）。
2. 每个节点 j 的入度为 1（只有一个元素最终想来这里）。

因此，整个图是若干个不相交的有向环（cycle）的集合。

示例 1 的映射构建：
原数组 [7, 1, 3, 2, 4, 5, 6]
排序后 [1, 2, 3, 4, 5, 6, 7]

我们建立映射“原索引 → 目标索引”：

• 值 7 在排序后数组的索引是 6（因为升序后 7 在第 6 位，0-based），所以原索引 0 的目标索引是 6。
• 值 1 的目标索引是 0（原索引 1 的目标索引 0）
• 值 3 的目标索引是 2（原索引 2 的目标索引 2，已经在正确位置）
• 值 2 的目标索引是 1（原索引 3 的目标索引 1）
• 值 4 的目标索引是 3（原索引 4 的目标索引 3）
• 值 5 的目标索引是 4（原索引 5 的目标索引 4）
• 值 6 的目标索引是 5（原索引 6 的目标索引 5）

于是我们得到映射表（原索引 → 目标索引）：
[0→6, 1→0, 2→2, 3→1, 4→3, 5→4, 6→5]

画出有向边：

• 0 → 6 → 5 → 4 → 3 → 1 → 0 这是一个长度为 6 的环（节点 0,6,5,4,3,1）
• 2 → 2 这是一个自环（长度为 1）

步骤 3：最少交换次数与环的关系

重要定理：
对于一个长度为 k 的环（k > 1），将其内部的所有元素归位（即环上每个节点都指向自己）所需的最少交换次数是 k - 1。

证明思路：

• 每次交换可以归位至少一个元素（实际上，如果我们将不在正确位置的元素与它目标位置的元素交换，可以一次将一个元素归位，另一个可能归位也可能不归位）。
• 更优的方法是：在长度为 k 的环中，固定一个基准元素，用 k-1 次交换，将环上其他 k-1 个元素逐个放到正确位置，最后基准元素自动归位。
  例如，环 a→b→c→a：
  交换 a 和 b：b 归位，a 去了 b 原位置（即 c 的目标位置？这里需要具体演示）。实际上标准做法是：从环中任意节点开始，依次将其与它的目标位置交换，每次交换会让一个节点归位，重复 k-1 次，所有节点归位。

结论：
总最小交换次数 = Σ(每个环的长度 - 1) = n - 环的个数

在上例中：

• 环1 长度6 → 交换次数 5
• 环2 长度1 → 交换次数 0
  总交换次数 = 5，与示例一致。

步骤 4：算法实现步骤

1. 创建排序后数组的副本 sorted_arr = sorted(arr)。
2. 建立值到目标索引的映射字典（因为值互异）：value_to_index = {value: index for index, value in enumerate(sorted_arr)}。
3. 初始化 visited = [False]*n，用于标记下标是否已被访问。
4. 遍历每个下标 i：
   • 如果 visited[i] 为真，或 i == value_to_index[arr[i]]（自环），则跳过。
   • 否则，以 i 为起点，沿着“当前下标对应的目标下标”路径走，直到回到起点，记录路径上节点数 cycle_size。
     此过程将路径上所有节点标记为 visited。
   • 累加 cycle_size - 1 到总交换次数。
5. 返回总交换次数。

时间复杂度：O(n log n) 主要来自排序，构建环只需 O(n)。
空间复杂度：O(n) 用于存储排序数组和映射。

步骤 5：处理重复元素的扩展（变体问题）

如果数组中有重复元素，上述“值→目标索引”的映射就不唯一了。
我们需要将“最小交换次数”问题转化为将原数组通过交换变为指定目标数组的最少交换次数，且目标数组是排序后的数组。

关键思路：
我们可以将数组元素看作“带原始标记的对象”，即使值相同，也通过它们的原始索引来区分。
但交换次数只与索引的置换有关，我们可以用以下方法：

1. 对原数组排序得到目标数组。

2. 因为值可重复，同一个值可能对应多个目标位置。为了最小化交换次数，我们需要将原数组中每个值匹配到最近的可能的目标位置。
   一种贪心匹配：
   从最小元素开始，将原数组中该元素的每个出现位置，按顺序分配到目标数组中该元素的对应位置。
   这实际上等同于稳定排序的映射：排序后，保持相同元素的原始相对顺序。

3. 得到映射“原索引 i → 目标索引 j”后，此映射仍是排列（因为目标位置是原位置的一个排列），于是可以同样用环分解计算交换次数。

示例：[2, 1, 2, 1]
排序后目标数组：[1, 1, 2, 2]
稳定匹配（相同值的原始顺序不变）：

• 原索引 0 的值 2，是第一个 2，应放到目标数组的第一个 2 的位置（索引 2）
• 原索引 1 的值 1，是第一个 1，应放到目标数组的第一个 1 的位置（索引 0）
• 原索引 2 的值 2，是第二个 2，应放到目标数组的第二个 2 的位置（索引 3）
• 原索引 3 的值 1，是第二个 1，应放到目标数组的第二个 1 的位置（索引 1）

得到映射：0→2, 1→0, 2→3, 3→1
有向图：0→2→3→1→0 是一个长度为 4 的环。
最少交换次数 = 4 - 1 = 3。
验证：确实需要 3 次交换。

步骤 6：总结

• 当元素互异时，问题可转化为计算排列的环结构，最少交换次数 = n - 环数。
• 当元素有重复时，需通过稳定排序建立映射，再计算环结构，公式不变。
• 这个模型不仅适用于排序，也适用于“将任意排列 A 通过最少交换变成排列 B”的问题。

这就是基于循环图模型的“最少交换次数排序”问题的完整解法与扩展。