如何计算排序无序数组所需的最小交换次数？求相关算法的严格证明

嘿，这个问题我太熟了！咱们先从核心逻辑入手，再一步步把证明给你讲透，保证你能彻底明白～

核心算法思路 #

要计算最小交换次数，关键是找出原数组元素在排序后的位置构成的循环节，公式很简单：

最小交换次数 = 数组长度 - 循环节的数量

举个直观的例子：比如数组 [3, 1, 2, 5, 4]，排序后是 [1,2,3,4,5]。我们给每个元素找它该去的位置：

• 位置0的元素3，排序后在位置2 → 0→2；位置2的元素2，排序后在位置1 →2→1；位置1的元素1，排序后在位置0 →1→0 → 这是一个长度为3的循环
• 位置3的元素5，排序后在位置4 →3→4；位置4的元素4，排序后在位置3 →4→3 → 这是一个长度为2的循环
  总循环数是2，数组长度是5，所以最小交换次数是5-2=3次，实际操作也确实只需要3次就能排好序。

严格证明：为什么这个公式是对的？ #

我们分两部分证明：一是每个循环需要的交换次数，二是为什么这是最小次数。

1. 单个循环的交换次数推导 #

对于一个长度为k的循环，我们需要k-1次交换就能让循环里的所有元素归位。这里用数学归纳法来证明：

• 基础情况：当k=1时，元素已经在正确位置，不需要交换，次数=1-1=0，成立。
• 归纳假设：假设长度为m的循环需要m-1次交换。
• 归纳步骤：考虑长度为m+1的循环 i₁→i₂→...→iₘ₊₁→i₁（意思是i₁位置的元素该去i₂，i₂的该去i₃，…，iₘ₊₁的该去i₁）。
  我们交换i₁和iₘ₊₁的元素：
  • 此时i₁位置的元素变成了原iₘ₊₁的元素，而这个元素本来就该去i₁位置，所以i₁的元素归位了，脱离循环。
  • 剩下的元素形成了一个长度为m的循环 i₂→i₃→...→iₘ₊₁→i₂，根据归纳假设，这个循环需要m-1次交换。
    总共需要1 + (m-1) = m次交换，也就是(m+1)-1次，符合假设。

所以所有循环的交换次数之和是 Σ(kᵢ - 1)（kᵢ是每个循环的长度），展开后就是 Σkᵢ - Σ1。因为所有循环的长度之和等于数组长度n，循环的数量是c，所以总和就是n - c，这就是总交换次数。

2. 为什么这是最小次数？ #

我们从下界来推导：

• 最终排序完成时，每个元素都是一个独立的循环（循环数为n）。
• 初始时循环数是c。
• 每次交换操作，最多只能让循环数增加1（只有交换同一个循环里的两个元素时，才会把一个循环拆成两个，循环数+1；如果交换不同循环的元素，循环数反而会减少）。

要从初始的c个循环变成n个循环，至少需要增加n - c个循环，而每次交换最多增加1个，所以最少需要n - c次交换。而我们前面的方法正好用了n - c次，所以这就是最小的交换次数。

内容的提问来源于stack exchange，提问作者voipp