algorithm - Judgecode——用交换排序(2)

Question

我遇到的问题如下，有人对此有什么想法吗？ http://judgecode.com/problems/1011

给定从 0 到 n - 1 的整数排列，对它们进行排序很容易。但是如果每次只能交换一对整数怎么办？

请计算最少交换次数

Answer 1

一个经典算法似乎是排列循环 ( https://en.wikipedia.org/wiki/Cycle_notation#Cycle_notation )。所需的交换次数等于元素总数减去循环次数。

例如:

1 2 3 4 5
2 5 4 3 1

Start with 1 and follow the cycle:
1 down to 2, 2 down to 5, 5 down to 1.

1 -> 2 -> 5 -> 1
3 -> 4 -> 3

我们需要将索引 1 与 5 交换，然后将索引 5 与 2 交换；以及索引 3 与索引 4。总共 3 次交换或 n - 2。我们将 n 减去循环数，因为循环元素总共为 n，每个循环代表一个小于其中元素数量的交换。