排序算法之：最小交换次数排序（Minimum Swaps to Sort） 题目描述 给定一个包含 n 个不同整数的数组 arr ，计算将数组按升序排序所需的最小交换次数。数组中的元素是 0 到 n-1 的排列（即元素互异且范围在 [0, n-1] ）。要求时间复杂度低于 O(n²)，并尽可能高效。 示例 输入： arr = [2, 5, 4, 3, 1, 0] 输出： 4 解释：通过 4 次交换可将数组排序为 [0, 1, 2, 3, 4, 5] 。 解题过程 1. 问题分析 直接对数组排序并记录交换次数不可行（如冒泡排序交换次数可能非最小）。 关键观察：若元素已在其正确位置（即 arr[i] == i ），则无需交换；否则，可通过交换将元素放到正确位置。 最小交换次数的计算可转化为图论中的环检测问题：将数组视为置换，分解为循环环，每个环内的交换次数为环的大小减 1。 2. 图论建模 构建有向图：节点为数组索引 0 到 n-1 。对于每个索引 i ，添加一条从 i 到 arr[i] 的边（因为元素 arr[i] 应被放到索引 arr[i] 处）。 示例 arr = [2, 5, 4, 3, 1, 0] 的图： 边：0→2, 1→5, 2→4, 3→3, 4→1, 5→0。 环1：0→2→4→1→5→0（环大小为 5） 环2：3→3（环大小为 1，自环） 3. 环与交换次数的关系 一个大小为 k 的环需要 k-1 次交换才能将环内所有元素归位（例如，环内元素依次交换即可归位）。 总最小交换次数 = 所有环的 (环大小 - 1) 之和。 示例：环1大小=5，贡献 4 次交换；环2大小=1，贡献 0 次。总交换次数 = 4。 4. 算法步骤 创建访问数组 visited[] ，初始全为 false 。 遍历每个索引 i ： 若 visited[i] 为 true 或 arr[i] == i （自环），跳过。 否则，从 i 开始追踪环： 初始化环大小 cycleSize = 0 ，当前节点 current = i 。 循环直到 visited[current] 为 true ： 标记 visited[current] = true 。 更新 current = arr[current] 。 cycleSize++ 。 将 cycleSize - 1 加入总交换次数。 返回总交换次数。 5. 示例推导 arr = [2, 5, 4, 3, 1, 0] ， visited[] 初始全 false 。 i=0：未访问，追踪环 0→2→4→1→5→0， cycleSize=5 ，交换次数 += 4。 i=1：已访问（在环中），跳过。 i=2、4、5 同理跳过。 i=3： arr[3]==3 ，自环，跳过。 总交换次数 = 4。 6. 复杂度分析 时间复杂度：O(n)，每个节点仅被访问一次。 空间复杂度：O(n)，用于 visited[] 数组。 关键点总结 将排序问题转化为置换的环分解问题。 最小交换次数由环的结构决定，与具体交换顺序无关。 算法高效且适用于元素为 0 到 n-1 排列的场景。