我正在对一个没有相同数字的整数序列进行排序(不失一般性，我们假设该序列是 1,2,...,n 的排列)到它的自然数递增顺序(即 1,2,...,n)。我在考虑直接交换元素(不管元素的位置，换句话说，交换对任意两个元素有效)，交换次数最少(以下可能是一种可行的解决方案):
Swap two elements with the constraint that either one or both of them should be swapped into the correct position(s). Until every element is put in its correct position.
但我不知道如何从数学上证明上述解决方案是否是最优的。谁能帮忙？
最佳答案
我能够用 graph-theory 证明这一点.可能想在 :) 中添加该标记
创建一个有 n 个顶点的图。创建从节点 n_i 到 n_j 的边，如果位置 i 中的元素应该在正确的位置 j订购。您现在将拥有一个由几个不相交的循环组成的图形。我认为正确排序图形所需的最小交换次数是
M = sum (c in cycles) size(c) - 1
花点时间说服自己……如果两个项目在一个循环中，一次交换就可以解决它们。如果三个项目在一个循环中，你可以交换一对将一个放在正确的位置，并且两个循环仍然存在，等等。如果 n 项目在一个循环中，你需要 n-1 交换。 (即使您不与近邻交换也是如此。)
鉴于此，您现在可能会明白为什么您的算法是最优的。如果你进行交换并且至少有一个项目处于正确的位置，那么它将始终将 M 的值减 1。对于长度为 n 的任何循环，考虑将一个元素交换到正确的位置，由它的邻居占据。您现在有一个正确排序的元素和一个长度为 n-1 的循环。
由于 M 是最小交换次数，而您的算法每次交换总是将 M 减 1，因此它一定是最优的。
关于algorithm - 计算排序序列的最小交换次数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56665054/