置换环可以得到数组排序（可以指定排序方式）所需交换的最小次数。其的思想是：将每个节点指向其排序后应该存放的位置，最终首位相接形成一个环，那么数组排序所需的最小交换次数为数组长度-环的数量。
包含自环
置换环-01.jpg
代码为：
public int template(int[] source, int[] target) {
int len = source.length;
Map<Integer, Integer> map = new HashMap<>(); // 存储目标排序每个元素的位置
boolean[] flag = new boolean[len]; // 标识当前字符串是否已经访问过
for (int i = 0; i < len; i++) map.put(target[i], i);
int loop = 0; // 环的数量
for (int i = 0; i < len; i++) {
if (flag[i]) continue;
int cur = source[i];
while (!flag[cur]) {
flag[cur] = true;
cur = source[map.get(cur)];
}
loop++;
}
return len - loop;
}
参考链接：
