Question

将数组{3,7,1,6,2,4,8,5}中的元素从大到小的顺序排列,每次可以任意交换两个元素，求最少的交换次数。

请写出具体的交换过程

Answer 1

最少交换次数肯定是与8 7 6 5 4 3 2 1 不对应的数的个数再减可以形成的环的个数（因为每个环的最后一个数都不用排序的，前面都排好了，最后一个自然就序），此数组有两个环，所以是5次。
hint：环指的是例如上面数组中的1 6 5三个数虽然都不在自己应该在的位置，但他们占据了排好序后1,6,5应该占据的位置，所以可以抽象成一个环，环内换顺序就行了。同样3,2,4,8也是一个环，还有，对应好的7也可以看做是一个环，所以是8-1-1-1=5
交换过程有很多：
eg：
交换3 8 变成8 7 1 6 2 4 3 5
交换1 6 变成8 7 6 1 2 4 3 5
交换1 5 变成8 7 6 5 2 4 3 1
交换2 4 变成8 7 6 5 4 2 3 1
交换2 3 变成8 7 6 5 4 3 2 1
注意是环内交换