数组中的逆序对

剑指 Offer 51. 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字

则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

public static int method(int[] nums) {
        if(0 == nums.length){
            return 0;
        }
        return proceed(nums, 0, nums.length - 1);
    }
    public static int proceed(int[] arr, int l, int r) {
        if (l == r) {
            return 0;
        }
        int m = l + ((r - l) >> 1);
        return proceed(arr, l, m)+proceed(arr, m + 1, r)+merage(arr, l, m, r);
    }

    public static int merage(int[] arr, int l, int m, int r) {
        int[] help = new int[r - l + 1];
        int lb = l;
        int rb = m + 1;
        int i = 0;
        int count = 0;
        while (lb <= m && rb <= r) {
            if (arr[lb] > arr[rb]) {
                help[i++] = arr[lb++];
                count += r - rb + 1;
            } else {
                help[i++] = arr[rb++];
            }
        }
        while (lb <= m) {
            help[i++] = arr[lb++];
        }
        while(rb <= r){
            help[i++] = arr[rb++];
        }
        for (int j = 0; j < help.length; j++) {
            arr[l + j] = help[j];
        }
        return count;
    }