数组中的逆序对

问题陈述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

思路详解

1、很显然，此题可以双循环列举比较，复杂度为O(n^2)，有没有更好的解法呢？有的，利用归并排序的思想。

/**
 * 首先你要知道归并排序的流程：
 *
 * 先将数组分成两部分，然后分别将这两部分排好序；
 * 然后开一个 helper 数组，指针 a 和 b 分别指向这两个部分的第一个元素；
 * 比较指针 a 所指元素与指针 b 所指元素的大小，将小的元素放进 helper 数组中；
 * 如果某个指针遍历到对应部分的末尾的话，则需要将另一个指针所指元素以及它后面的元素直接添加到 helper 数组中；
 *
 * 最后再将 helper 数组中的数据拷贝到原数组中即可。
 * 重点在于在两个指针比较的过程中，如果第一个子数组中的数字大于第二个子数组中的数字，则可以构成逆序对，并且逆序对的数目就是第二个子数组中剩余数字的个数。
 */
public class CountReversePairs {
    int count=0;
    public int reversePairs(int[] nums){
        if(nums==null||nums.length==1) return 0;
        mergeSort(nums,0,nums.length-1);
        return count;
    }
    //归并排序整体逻辑
    public void mergeSort(int[] nums,int start,int end){
        if(start==end) return; //如果两个指针相遇，则说明已经排好序
        int mid=start+((end-start)>>1);
        mergeSort(nums,start,mid);  // 对数组的左半部分进行归并
        mergeSort(nums,mid+1,end);  // 对数组的右半部分进行归并
        merge(nums,start,mid,end);
    }
    //合并
    public void merge(int[] nums,int start,int mid,int end){
        int[] helper=new int[end-start+1];
        int k=0,pos1=start,pos2=mid+1;
        while (pos1<=mid&&pos2<=end){
            //运算符 <= 是为了去除元素相等的情况
            // 例如在 [1, 3, 2, 3, 1] 中，排除 [1, 1] 和 [3, 3] 的情况
            if(nums[pos1]<=nums[pos2]){
                helper[k++]=nums[pos1++];
            }else{
                // 本题核心：由于 nums[pos1] > nums[pos2]，
                // 则从 nums[pos1] 到 nums[middle] 必定都是大于 nums[pos2] 的，
                // 因为两部分的子数组已经是各自有序的
                helper[k++]=nums[pos2++];
                count+=(mid-pos1+1);
            }
        }
        // 下面这两个 while 是当其中一个子数组中的指针如果已经遍历完了，
        // 那么另一个子数组肯定会有剩余元素，所以将剩余部分直接放到 help 中
        while (pos1<mid){
            helper[k++]=nums[pos1++];
        }
        while (pos2<end){
            helper[k++]=nums[pos2++];
        }
        // 将 helper 中的元素拷贝到原数组
        for (int j = 0; j < helper.length; j++) {
            nums[start + j] = helper[j];
        }
    }