我正在对没有相同数字的整数序列进行排序（不失一般性，假设该序列是的排列1,2,...,n）到其自然递增顺序（即1,2,...,n）。我正在考虑以最少的交换次数（以下可能是可行的解决方案）直接交换元素（无论元素的位置如何；换句话说，任何两个元素都有效）。
1,2,...,n
交换两个元素时，必须将其中一个或两个都交换到正确的位置上。直到每个元素都放置在正确的位置。
但是我不知道如何数学证明上述解决方案是否最佳。有人可以帮忙吗？
我能够用图论证明这一点。可能想在:)中添加该标签
创建带有n顶点的图形。如果位置上的元素应该以正确的顺序放置，则创建从节点n_i到的边缘。现在，您将获得一个由几个不相交的循环组成的图形。我认为正确排序图所需的最小交换次数为n_j``i``j
n
n_i
n_j``i``j
M = sum (c in cycles) size(c) - 1
花一点时间让自己相信…如果一个周期中有两个项目，那么一次交换就可以解决这些问题。如果一个周期中有三个项目，则可以交换一对以将一个放置在正确的位置，而保留两个n周期，n-1依此类推。如果项目处于一个周期中，则需要交换。（即使您不与直接邻居交换，也总是如此。）
n-1
鉴于此，您现在可以看到为什么算法是最佳的。如果进行交换并且至少有一个项目处于正确位置，则它将始终将值减小M1。对于任何长度的周期n，请考虑将一个元素交换到正确的位置，并由其相邻位置占据。现在，您有一个正确排序的元素和一个length的循环n-1。
M
由于M是交换的最小数量，并且您的算法M每次交换总是减少1，因此它必须是最佳的。
