交换元素使序列有序求最少交换次数的题有两类：
第一种是 只能交换相邻元素使序列有序 ，求最小交换次数，假如是是序列升序，只需要求逆序对数。比如
{5, 1, 3, 2, 4, 7, 6, 8}，逆序的有：(5, 1)，(5, 3)，(5, 2)，(5, 4)，(3, 2)，(7, 6)，一共 6 对，最小交换次数是 6 次。1
2
3
4
5
6
7
8
9
10
11public static void getMinSwapCount1(int[] arr) {
int count = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr [i] > arr [j]) {
count++;
}
}
}
System.out.println (count);
}第二种是 可以交换任意两个位置的元素，使之有序 ，求最小交换次数，答案是数字的个数减去交换数字形成的环 （置换环）的个数。比如
{5, 1, 3, 2, 4, 7, 6, 8}, 求将这个序列变成升序序列的最小交换次数，那么这个序列中的环有{5, 1, 2, 4},{7, 6},{3}, {8}, 那么最小交换次数就是8 - 4 = 4，求降序的最小交换次数，只需要将序列逆置，再进行求解。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27public static void getMinSwapCount2(int[] arr) {
int[] sorted = Arrays.copyOf (arr, arr.length);
Arrays.sort (sorted);
Map<Integer, Integer> map = new HashMap<>();
int len = arr.length;
for (int i = 0; i < len; i++) {
// 原数组的每个元素和其索引建立映射
map.put (arr [i], i);
}
// 记录环的个数
int loops = 0;
// 标志每个元素是否被访问过
boolean[] flags = new boolean[len];
for (int i = 0; i < len; i++) {
// 没被访问过
if (!flags [i]) {
int j = i;
// flags [i] 为 true 时，回到起点，找到一个环
while (!flags [i]) {
j = map.get (sorted [j]);
flags [j] = true;
}
loops++;
}
}
System.out.println (len - loops);
}