交换最少次数使数组有序

交换最少次数使数组有序

题目1：

给出一个序列，只交换相邻两数，使得序列升序排列，求出最少交换次数。

思路：
如果说只是交换相邻两个数字。那么就是这个序列的逆序数。

1.假设序列个数为n，我们先把最大的数换到最后，因为是相邻数字交换，所以把最大数交换到最后，需要交换的次数为最大数后的数字个数。

2.当完成最大数的交换后，可以将最大数从序列中划去不管了，即此时序列个数为n-1了，我们再在该序列中找到一个最大数，进行相同操作。

3.所以使整个序列有序的交换次数为,这个序列的所有逆序总数。

比如4，3，2，1。
(4,3) (4,2) (4,1)，有3个逆序，交换后 3，2，1，4
(3,2) (3,1)，有2个逆序，交换后2,1,3,4
(2,1)，有1个逆序，交换后1,2,3,4

故只需求逆序对的个数

题目2

给出一个序列，可交换任意两个数，使序列升序排列，求最少交换次数。

思路：
与之前不同，之前是只能交换相邻两数。
比如4，3，2，1，如果只交换相邻两数，最少交换次数为6。
但如果是交换任意两数，最少交换次数就为2。

有序列 5 4 3 2 1

按升序排列之后为 1 2 3 4 5

我们可以发现5，1虽然不在自己应该在的位置，但是如果把它们两个看成整体，对于整个序列来说它们占据了排好序后5，1应该在的位置，所以对于整个序列来说是有序的，它们只是自身内部无序而已。5应该到1处，1应该到5处，形成了一个循环，所以可以将它们抽象成一个环，环内换序就可以了。(下面把这种环称为循环节)
对于一个含有n个元素的循环节来说，要使其有序，要交换n-1次(前面都排好了，最后一个数自然有序就不用排了)。
上例中3在原本就在的位置，可以看成一个元素的循环节。
我们可以推断出有一个循环节，就可以少交换一次，因为n个元素的循环节，只需交换n-1次即可有序。
那么对于整个序列来说，最少交换次数为 元素总数-循环节个数。

5，4，3，2，1序列中有3个循环节，所以最少交换次数为2。

public class Main {
    public static void main(String[] args) {
        int[] nums = {5,4,3,2,1};
        System.out.println(getMinSwap(nums));
    }

    public static int getMinSwap(int[] nums){
        int len = nums.length;

        int[] sortNums = Arrays.copyOf(nums, len);
        Arrays.sort(sortNums);
        Map<Integer, Integer> map = new HashMap<>();
        //存储元素的最终位置和索引
        for(int i = 0; i < len; i++){
            map.put(sortNums[i], i);
        }
        int loops = 0;
        boolean[] flag = new boolean[len];
        for(int i = 0; i < len; i++){
            if(!flag[i]){
                int j = i;
                while (!flag[j]){
                    flag[j] = true;
                    j = map.get(nums[j]);
                }
                loops ++;
            }
        }
        return len - loops;
    }
}