求数组中逆序对

求数组中的逆序对

变式

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

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

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

我们以数组{7,5,6,4}为例来分析统计逆序对的过程。每次扫描到一个数字的时候，我们不拿ta和后面的每一个数字作比较，否则时间复杂度就是O(n^2)，因此我们可以考虑先比较两个相邻的数字。

(a) 把长度为4的数组分解成两个长度为2的子数组；

(b) 把长度为2的数组分解成两个成都为1的子数组；

​ (c) 把长度为1的子数组 合并、排序并统计逆序对 ；

(d) 把长度为2的子数组合并、排序，并统计逆序对；

​ 在上图（a）和（b）中，我们先把数组分解成两个长度为2的子数组，再把这两个子数组分别拆成两个长度为1的子数组。接下来一边合并相邻的子数组，一边统计逆序对的数目。在第一对长度为1的子数组{7}、{5}中7大于5，因此（7,5）组成一个逆序对。同样在第二对长度为1的子数组{6}、{4}中也有逆序对（6,4）。由于我们已经统计了这两对子数组内部的逆序对，因此需要把这两对子数组 排序 如上图（c）所示， 以免在以后的统计过程中再重复统计。

​ 接下来我们统计两个长度为2的子数组子数组之间的逆序对。合并子数组并统计逆序对的过程如下图如下图所示。

​ 我们先用两个指针分别指向两个子数组的末尾，并每次比较两个指针指向的数字。如果第一个子数组中的数字大于第二个数组中的数字，则构成逆序对，并且逆序对的数目等于第二个子数组中剩余数字的个数，如下图（a）和（c）所示。如果第一个数组的数字小于或等于第二个数组中的数字，则不构成逆序对，如图b所示。每一次比较的时候，我们都把较大的数字从后面往前复制到一个辅助数组中，确保 辅助数组（记为copy） 中的数字是递增排序的。在把较大的数字复制到辅助数组之后，把对应的指针向前移动一位，接下来进行下一轮比较。

过程：先把数组分割成子数组，先统计出子数组内部的逆序对的数目，然后再统计出两个相邻子数组之间的逆序对的数目。在统计逆序对的过程中，还需要对数组进行排序。

分治算法

    public static int pairsCount(int[] nums, int left, int right){
        if(left < right){
            int mid = left + ((right - left) >> 1);
            int leftCount = pairsCount(nums, left, mid) %1000000007;
            int rightCount = pairsCount(nums, mid+1, right) %1000000007;
            int count = 0;
            int i = mid; //左边部分
            int j = right; //右边部分
            int k = right - left;//辅助数组
            int[] temp = new int[k+1];
            while (i >= left && j >= mid + 1){
                //左边的元素大于右边的元素，逆序对就是右边元素的数量，同时将该元素放入辅助数组进行排序
                if(nums[i] > nums[j]){
                    count += j - mid;
                    temp[k--] = nums[i--];
                }else{
                    temp[k--] = nums[j--];
                }
            }
            //剩余部分加入temp
            while(i >= left){
                temp[k--] = nums[i--];
            }
            while (j >= mid + 1){
                temp[k--] = nums[j--];
            }
            //将元素复制回nums
            System.arraycopy(temp,0, nums, left, right - left + 1);
            return (leftCount + rightCount + count) % 1000000007;
        }
        return 0;
    }
}