剑指offer-35-逆序对

思路

• 排序算法
• 冒泡排序，每次交换，cnt++
• 归并排序，当[i,mid] [j,end],当i>j时，把j放入临时数组，这个时候，不仅i,j构成逆序，而且是[i,mid]与j都构成逆序对
  cnt=(cnt+(mid-i+1))%1000000007,这里不能用cnt+=(mid-i+1)%1000000007

代码

非递归实现

public class Solution {
    int cnt=0;
    public int InversePairs(int [] array) {
        if (array.length <= 1) {
            return 0;
        }
        int len = 1;
        while (len < array.length) {
            int start = 0;
            while (start + 2 * len - 1 < array.length) {
                int mid = start + len - 1;
                int end = start + 2 * len - 1;
                merge(array, start, mid, end);
                start = start + 2 * len;
            }
            //剩余无法构成完整的两组也要进行处理
            if (start + len - 1 < array.length)
                merge(array, start, start + len - 1, array.length - 1);
            len = len * 2;
        }
        return cnt;

    }

   public void merge(int[] arr, int start, int mid, int end) {
        int i = start;
        int j = mid + 1;
        int[] temp = new int[end - start + 1];
        int index = 0;
        while (i <= mid && j <= end) {
            if (arr[i] <= arr[j])
                temp[index++] = arr[i++];
            else{ 
                temp[index++] = arr[j++];
                cnt =(cnt+(mid-i+1)) %1000000007;
            }

        }
        while (i <= mid)
            temp[index++] = arr[i++];
        while (j <= end)
            temp[index++] = arr[j++];

        for (int k = start; k <= end; k++)
            arr[k] = temp[k - start];
    }

}