【归并排序应用】求数组中的逆序对

题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。
题目保证输入的数组中没有的相同的数字

public class Solution {
    int cnt;
 
    public int InversePairs(int[] array) {
        cnt = 0;
        if (array != null)
            mergeSort(array, 0, array.length - 1);
        return cnt;
    }

    /*
     * 归并排序
     */
    public void mergeSort(int[] a, int start, int end) {
        if (start >= end)
            return;
        int mid = (start + end) >> 1;
 
        mergeSort(a, start, mid);
        mergeSort(a, mid + 1, end);
 
        merge(a, start, mid, end);
    }
 
    /*
     * 将一个数组中的两个相邻有序区间合并成一个
     */
    public void merge(int[] a, int start, int mid, int end) {

        int[] tmp = new int[end - start + 1];
 
        int i = start, j = mid + 1, k = 0;

        while (i <= mid && j <= end) {
            if (a[i] <= a[j])
                tmp[k++] = a[i++];
            else {
                tmp[k++] = a[j++];
                cnt += mid - i + 1;            // 计算逆序对
            }
        }

        while (i <= mid)
            tmp[k++] = a[i++];
        while (j <= end)
            tmp[k++] = a[j++];

        for (k = 0; k < tmp.length; k++)
            a[start + k] = tmp[k];
    }
}