排序算法之：循环不变式在最小交换次数排序（Minimum Swaps to Sort）的图论模型与环分解优化中的应用

字数 4280 2025-12-11 19:43:59

排序算法之：循环不变式在最小交换次数排序（Minimum Swaps to Sort）的图论模型与环分解优化中的应用

题目描述

给定一个包含 n 个不同整数的数组 arr，这些整数是 0 到 n-1 的一个排列。我们每次可以交换数组中的任意两个元素。问题要求计算将数组排成升序（即 arr[i] = i）所需的最少交换次数。

例如：
输入：arr = [2, 1, 0, 4, 3]
输出：2
解释：一种最少交换的方案是：先交换索引 0 和 2 的元素，得到 [0, 1, 2, 4, 3]；再交换索引 3 和 4 的元素，得到 [0, 1, 2, 3, 4]，共 2 次交换。

解题过程

我们将循序渐进地分析这个问题，并引入一种基于“循环不变式”和图论（环分解）的精妙解法。

第一步：理解问题本质与暴力解法的局限性

我们的目标是让每个索引 i 上的元素值等于 i。换句话说，我们需要将每个“错位”的元素放到它正确的位置上。

一个直观的想法是：从第一个位置 i=0 开始，如果这个位置上的元素不是 0，我们就把 0 找过来放上去。但这样可能导致其他元素被换走，需要继续调整。这个过程类似于“选择排序”的思想。在选择排序中，我们为每个位置 i 寻找应该放在这里的元素（即值等于 i 的元素），然后交换过来。选择排序的交换次数恰好是 (n - 循环数)，其中循环数我们稍后定义。但最坏情况下，选择排序需要 n-1 次交换。然而，选择排序的交换策略不一定是最优的，但在排列中，它确实给出了最少交换次数的一个候选方案。我们需要证明其最优性，并找到更清晰的计算方法。

第二步：建立图论模型——排列与循环分解

关键思路：将排列视为一个从索引集合到元素集合的映射。因为数组是 0 到 n-1 的一个排列，我们可以定义一个映射 f: 索引 i -> 元素 arr[i]。但我们更关心“元素应该去的位置”。我们定义另一个映射 p: 值 v -> 这个值 v 当前所在的索引。即 p[arr[i]] = i。由于值是 0 到 n-1 的排列，p 也是一个排列。

现在，考虑排列 p。排列可以被分解成若干个互不相交的循环（Cycle）。一个循环是指一组位置/值，沿着“这个值应该去的位置”这个关系形成一个环。

如何找到循环？从任意一个值 v 开始，看它应该在的位置：值 v 应该在索引 v 上。但它现在在索引 p[v] 上。我们看当前在索引 v 上的值是谁，假设是 u。那么值 u 应该在索引 u 上，但它现在在索引 p[u] 上…… 以此追踪，最终会回到起点 v，形成一个循环。

例子：arr = [2, 1, 0, 4, 3]

值 0 现在在索引 2 上 (p[0]=2)。值 2 现在在索引 0 上 (p[2]=0)。值 0 和 2 形成一个循环 (0 -> 2 -> 0)。
值 1 现在在索引 1 上 (p[1]=1)，这是一个自循环（长度为1的循环）。
值 3 现在在索引 4 上 (p[3]=4)。值 4 现在在索引 3 上 (p[4]=3)。值 3 和 4 形成一个循环 (3 -> 4 -> 3)。

所以排列 p 分解为三个循环：C1=(0,2)， C2=(1)， C3=(3,4)。长度为1的循环表示该元素已经在正确位置。

第三步：最少交换次数与循环的关系——核心定理

定理：对于一个长度为 L (L > 1) 的循环，将其所有元素放到正确位置所需的最少交换次数是 L-1。

为什么？

下界：在一个长度为 L 的循环中，有 L 个错位的元素。每次交换最多能使一个元素归位（如果交换的两个元素都属于这个循环，交换后可能使其中一个归位）。为了让所有 L 个元素归位，至少需要 L-1 次交换（第一次交换使一个归位，剩下 L-1 个错位，每次交换最多解决一个，所以至少还要 L-1 次，总共至少 L-1 次？严谨论证：初始状态有 L 个错位，最终状态 0 个错位。每次交换最多减少 2 个错位（如果交换的两个元素都归位），但最少减少 0 个（交换两个都不在该循环的元素对循环内无效）。实际上，在一个循环内部交换，第一次交换可以使一个元素归位（错位减1），后续每次交换也可以使一个元素归位。所以 L 个元素归位至少需要 L-1 次交换）。
构造性上界：存在一种策略用 L-1 次交换解决一个长度为 L 的循环。策略如下：固定循环中的一个元素，例如循环 (a1, a2, ..., aL)。交换 a1 和 aL，这样 aL 就归位了。现在循环变成了 (a1, a2, ..., a{L-1})，长度为 L-1。重复这个过程，每次交换都将当前循环的最后一个元素归位。经过 L-1 次交换，所有元素归位。

因此，对于整个排列，最少交换次数等于所有循环的 (长度 - 1) 之和。即：
最少交换次数 = Σ (L_i - 1) = n - 循环数，其中 L_i 是第 i 个循环的长度，循环数是指所有循环（包括长度为1的循环）的个数。

在上例中：
循环数 = 3 (两个长度为2的循环和一个长度为1的循环)。
n = 5。
最少交换次数 = 5 - 3 = 2。验证通过。

第四步：算法实现与循环不变式

现在我们的任务是：计算循环数。我们可以通过遍历数组，追踪未访问的循环来实现。

算法步骤：

初始化一个长度为 n 的布尔数组 visited，记录每个索引是否已被包含在某个循环中。初始全为 false。
初始化循环计数 cycle_count = 0。
对于每个索引 i 从 0 到 n-1：
- 如果 visited[i] 为 false 且 arr[i] != i（这个条件可以简化，因为如果 arr[i]==i，它自成一个循环，但我们也要计数）：
  实际上，无论 arr[i] 是否等于 i，只要 visited[i] 为 false，我们都开始追踪一个循环。如果 arr[i]==i，这个循环长度为1。
- 令 j = i。
- 当 visited[j] 为 false 时：
  - 标记 visited[j] = true。
  - 将 j 更新为 arr[j]。为什么呢？因为当前在位置 j 上的值是 arr[j]，这个值应该去的正确位置是 arr[j] 这个索引。所以我们跳到那个索引去继续追踪。
- 循环计数 cycle_count 增加 1。
最少交换次数 = n - cycle_count。

循环不变式：在算法执行过程中，我们可以定义一个循环不变式来理解其正确性。

不变式：所有已经被标记为 visited 的索引，都已经被正确地归类到某个循环中。并且，对于当前正在追踪的循环，我们已经访问了从起始点 i 到当前点 j 路径上的所有节点，并将它们标记为已访问，它们属于同一个循环。
初始化：开始时，visited 全为 false，不变式平凡成立。
保持：当我们从一个未访问的索引 i 开始，我们沿着映射 j -> arr[j] 进行追踪。每次标记 visited[j]=true，并将 j 更新为 arr[j]。因为排列中每个索引的入度和出度都是1（在映射图中），这条路径必然是一个环，最终会回到某个已访问的点。如果回到 i，则我们完成了一个新循环的发现。由于我们每次跳转是跟随“值应该去的正确位置”，所以我们探索的正好是包含 i 的循环。在探索过程中标记的所有点都属于这个循环。因此，在完成一个内部 while 循环后，不变式得以保持：所有新标记的点都被归类到了这个新发现的循环中。
终止：当所有索引都被访问后，每个索引都恰好属于一个被计数的循环。循环计数 cycle_count 就是总循环数。根据定理，最少交换次数为 n - cycle_count。

第五步：示例演练

以 arr = [2, 1, 0, 4, 3] 为例：
n=5, visited = [f, f, f, f, f], cycle_count=0.

i=0: visited[0]=false.
j=0, 进入内循环：
visited[0]=true.
j = arr[0] = 2.
j=2, visited[2]=false，继续：
visited[2]=true.
j = arr[2] = 0.
j=0, visited[0]=true，内循环结束。
cycle_count 变成 1.
i=1: visited[1]=false.
j=1, 进入内循环：
visited[1]=true.
j = arr[1] = 1.
j=1, visited[1]=true，内循环结束。
cycle_count 变成 2. (这个循环长度为1)
i=2: visited[2]=true，跳过。
i=3: visited[3]=false.
j=3, 进入内循环：
visited[3]=true.
j = arr[3] = 4.
j=4, visited[4]=false，继续：
visited[4]=true.
j = arr[4] = 3.
j=3, visited[3]=true，内循环结束。
cycle_count 变成 3.
i=4: visited[4]=true，跳过。

循环结束。cycle_count=3。
最少交换次数 = 5 - 3 = 2。

第六步：时间复杂度与空间复杂度分析

时间复杂度：O(n)。我们只遍历了每个索引一次。内循环虽然嵌套，但每个索引最多被访问两次（一次作为外层循环的 i，一次在内循环中被标记），所以总操作是 O(n)。
空间复杂度：O(n)，用于 visited 数组。实际上，我们可以优化到 O(1) 额外空间，通过修改原数组来做标记（例如将访问过的位置的值设为它自己或其他标记），但这样会破坏原数组。在允许修改原数组的情况下，空间复杂度可以是 O(1)。

总结

这个问题的核心是将排列的排序问题转化为图论中的循环分解。最少交换次数的计算基于一个关键的组合数学定理，而算法的实现则巧妙地利用循环不变式保证了我们能够正确、不重不漏地找出所有循环。这种方法不仅高效，而且揭示了问题背后的数学结构。

排序算法之：循环不变式在最小交换次数排序（Minimum Swaps to Sort）的图论模型与环分解优化中的应用题目描述给定一个包含 n 个不同整数的数组 arr ，这些整数是 0 到 n-1 的一个排列。我们每次可以交换数组中的任意两个元素。问题要求计算将数组排成升序（即 arr[i] = i ）所需的最少交换次数。例如：输入： arr = [2, 1, 0, 4, 3] 输出：2 解释：一种最少交换的方案是：先交换索引 0 和 2 的元素，得到 [0, 1, 2, 4, 3] ；再交换索引 3 和 4 的元素，得到 [0, 1, 2, 3, 4] ，共 2 次交换。解题过程我们将循序渐进地分析这个问题，并引入一种基于“循环不变式”和图论（环分解）的精妙解法。第一步：理解问题本质与暴力解法的局限性我们的目标是让每个索引 i 上的元素值等于 i。换句话说，我们需要将每个“错位”的元素放到它正确的位置上。一个直观的想法是：从第一个位置 i=0 开始，如果这个位置上的元素不是 0，我们就把 0 找过来放上去。但这样可能导致其他元素被换走，需要继续调整。这个过程类似于“选择排序”的思想。在选择排序中，我们为每个位置 i 寻找应该放在这里的元素（即值等于 i 的元素），然后交换过来。选择排序的交换次数恰好是 (n - 循环数)，其中循环数我们稍后定义。但最坏情况下，选择排序需要 n-1 次交换。然而，选择排序的交换策略不一定是最优的，但在排列中，它确实给出了最少交换次数的一个候选方案。我们需要证明其最优性，并找到更清晰的计算方法。第二步：建立图论模型——排列与循环分解关键思路：将排列视为一个从索引集合到元素集合的映射。因为数组是 0 到 n-1 的一个排列，我们可以定义一个映射 f: 索引 i -> 元素 arr[ i]。但我们更关心“元素应该去的位置”。我们定义另一个映射 p: 值 v -> 这个值 v 当前所在的索引。即 p[ arr[ i] ] = i。由于值是 0 到 n-1 的排列，p 也是一个排列。现在，考虑排列 p。排列可以被分解成若干个互不相交的循环（Cycle）。一个循环是指一组位置/值，沿着“这个值应该去的位置”这个关系形成一个环。如何找到循环？从任意一个值 v 开始，看它应该在的位置：值 v 应该在索引 v 上。但它现在在索引 p[ v] 上。我们看当前在索引 v 上的值是谁，假设是 u。那么值 u 应该在索引 u 上，但它现在在索引 p[ u ] 上…… 以此追踪，最终会回到起点 v，形成一个循环。例子： arr = [2, 1, 0, 4, 3] 值 0 现在在索引 2 上 (p[ 0]=2)。值 2 现在在索引 0 上 (p[ 2 ]=0)。值 0 和 2 形成一个循环 (0 -> 2 -> 0)。值 1 现在在索引 1 上 (p[ 1 ]=1)，这是一个自循环（长度为1的循环）。值 3 现在在索引 4 上 (p[ 3]=4)。值 4 现在在索引 3 上 (p[ 4 ]=3)。值 3 和 4 形成一个循环 (3 -> 4 -> 3)。所以排列 p 分解为三个循环：C1=(0,2)， C2=(1)， C3=(3,4)。长度为1的循环表示该元素已经在正确位置。第三步：最少交换次数与循环的关系——核心定理定理：对于一个长度为 L (L > 1) 的循环，将其所有元素放到正确位置所需的最少交换次数是 L-1。为什么？下界：在一个长度为 L 的循环中，有 L 个错位的元素。每次交换最多能使一个元素归位（如果交换的两个元素都属于这个循环，交换后可能使其中一个归位）。为了让所有 L 个元素归位，至少需要 L-1 次交换（第一次交换使一个归位，剩下 L-1 个错位，每次交换最多解决一个，所以至少还要 L-1 次，总共至少 L-1 次？严谨论证：初始状态有 L 个错位，最终状态 0 个错位。每次交换最多减少 2 个错位（如果交换的两个元素都归位），但最少减少 0 个（交换两个都不在该循环的元素对循环内无效）。实际上，在一个循环内部交换，第一次交换可以使一个元素归位（错位减1），后续每次交换也可以使一个元素归位。所以 L 个元素归位至少需要 L-1 次交换）。构造性上界：存在一种策略用 L-1 次交换解决一个长度为 L 的循环。策略如下：固定循环中的一个元素，例如循环 (a1, a2, ..., aL)。交换 a1 和 aL，这样 aL 就归位了。现在循环变成了 (a1, a2, ..., a{L-1})，长度为 L-1。重复这个过程，每次交换都将当前循环的最后一个元素归位。经过 L-1 次交换，所有元素归位。因此，对于整个排列，最少交换次数等于所有循环的 (长度 - 1) 之和。即：最少交换次数 = Σ (L_i - 1) = n - 循环数，其中 L_ i 是第 i 个循环的长度，循环数是指所有循环（包括长度为1的循环）的个数。在上例中：循环数 = 3 (两个长度为2的循环和一个长度为1的循环)。 n = 5。最少交换次数 = 5 - 3 = 2。验证通过。第四步：算法实现与循环不变式现在我们的任务是：计算循环数。我们可以通过遍历数组，追踪未访问的循环来实现。算法步骤：初始化一个长度为 n 的布尔数组 visited ，记录每个索引是否已被包含在某个循环中。初始全为 false 。初始化循环计数 cycle_count = 0 。对于每个索引 i 从 0 到 n-1：如果 visited[i] 为 false 且 arr[i] != i （这个条件可以简化，因为如果 arr[i]==i ，它自成一个循环，但我们也要计数）：实际上，无论 arr[i] 是否等于 i，只要 visited[i] 为 false，我们都开始追踪一个循环。如果 arr[i]==i ，这个循环长度为1。令 j = i 。当 visited[j] 为 false 时：标记 visited[j] = true 。将 j 更新为 arr[j] 。为什么呢？因为当前在位置 j 上的值是 arr[j] ，这个值应该去的正确位置是 arr[j] 这个索引。所以我们跳到那个索引去继续追踪。循环计数 cycle_count 增加 1。最少交换次数 = n - cycle_ count。循环不变式：在算法执行过程中，我们可以定义一个循环不变式来理解其正确性。不变式：所有已经被标记为 visited 的索引，都已经被正确地归类到某个循环中。并且，对于当前正在追踪的循环，我们已经访问了从起始点 i 到当前点 j 路径上的所有节点，并将它们标记为已访问，它们属于同一个循环。初始化：开始时， visited 全为 false，不变式平凡成立。保持：当我们从一个未访问的索引 i 开始，我们沿着映射 j -> arr[ j] 进行追踪。每次标记 visited[j]=true ，并将 j 更新为 arr[ j ]。因为排列中每个索引的入度和出度都是1（在映射图中），这条路径必然是一个环，最终会回到某个已访问的点。如果回到 i，则我们完成了一个新循环的发现。由于我们每次跳转是跟随“值应该去的正确位置”，所以我们探索的正好是包含 i 的循环。在探索过程中标记的所有点都属于这个循环。因此，在完成一个内部 while 循环后，不变式得以保持：所有新标记的点都被归类到了这个新发现的循环中。终止：当所有索引都被访问后，每个索引都恰好属于一个被计数的循环。循环计数 cycle_count 就是总循环数。根据定理，最少交换次数为 n - cycle_ count。第五步：示例演练以 arr = [2, 1, 0, 4, 3] 为例： n=5, visited = [ f, f, f, f, f], cycle_ count=0. i=0: visited[ 0 ]=false. j=0, 进入内循环： visited[ 0 ]=true. j = arr[ 0 ] = 2. j=2, visited[ 2 ]=false，继续： visited[ 2 ]=true. j = arr[ 2 ] = 0. j=0, visited[ 0 ]=true，内循环结束。 cycle_ count 变成 1. i=1: visited[ 1 ]=false. j=1, 进入内循环： visited[ 1 ]=true. j = arr[ 1 ] = 1. j=1, visited[ 1 ]=true，内循环结束。 cycle_ count 变成 2. (这个循环长度为1) i=2: visited[ 2 ]=true，跳过。 i=3: visited[ 3 ]=false. j=3, 进入内循环： visited[ 3 ]=true. j = arr[ 3 ] = 4. j=4, visited[ 4 ]=false，继续： visited[ 4 ]=true. j = arr[ 4 ] = 3. j=3, visited[ 3 ]=true，内循环结束。 cycle_ count 变成 3. i=4: visited[ 4 ]=true，跳过。循环结束。cycle_ count=3。最少交换次数 = 5 - 3 = 2。第六步：时间复杂度与空间复杂度分析时间复杂度：O(n)。我们只遍历了每个索引一次。内循环虽然嵌套，但每个索引最多被访问两次（一次作为外层循环的 i，一次在内循环中被标记），所以总操作是 O(n)。空间复杂度：O(n)，用于 visited 数组。实际上，我们可以优化到 O(1) 额外空间，通过修改原数组来做标记（例如将访问过的位置的值设为它自己或其他标记），但这样会破坏原数组。在允许修改原数组的情况下，空间复杂度可以是 O(1)。总结这个问题的核心是将排列的排序问题转化为图论中的循环分解。最少交换次数的计算基于一个关键的组合数学定理，而算法的实现则巧妙地利用循环不变式保证了我们能够正确、不重不漏地找出所有循环。这种方法不仅高效，而且揭示了问题背后的数学结构。