我能够用图论证明这一点。可能想在:)中添加该标签

创建带有n顶点的图形。如果位置上的元素应该以正确的顺序放置，则创建从节点n_i到的边缘。现在，您将获得一个由几个不相交的循环组成的图形。我认为正确排序图所需的最小交换次数为n_j``i``j

M = sum (c in cycles) size(c) - 1

花一点时间让自己相信…如果一个周期中有两个项目，那么一次交换就可以解决这些问题。如果一个周期中有三个项目，则可以交换一对以将一个放置在正确的位置，而保留两个n周期，n-1依此类推。如果项目处于一个周期中，则需要交换。（即使您不与直接邻居交换，也总是如此。）

鉴于此，您现在可以看到为什么算法是最佳的。如果进行交换并且至少有一个项目处于正确位置，则它将始终将值减小M1。对于任何长度的周期n，请考虑将一个元素交换到正确的位置，并由其相邻位置占据。现在，您有一个正确排序的元素和一个length的循环n-1。

由于M是交换的最小数量，并且您的算法M每次交换总是减少1，因此它必须是最佳的。