获取数组中逆序对的对数

package class04;

import java.util.Arrays;

/**
 * 获取数组中逆序对的对数
 * <p>
 * 在一个数组中，
 * 任何一个前面的数a，和任何一个后面的数b，
 * 如果(a,b)是降序的，就称为逆序对。
 * 返回数组中所有的逆序对的对数。
 */
public class Code03_reversePairNumber {
    public static int reversePairNumber(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        return process(arr, 0, arr.length - 1);
    }

    private static int process(int[] arr, int L, int R) {
        if (L == R) {
            return 0;
        }
        int M = L + ((R - L) >> 1);
        return process(arr, L, M) + process(arr, M + 1, R) + merge(arr, L, M, R);
    }

    private static int merge(int[] arr, int L, int M, int R) {
        int[] help = new int[R - L + 1];
        int ans = 0;//用于记录逆序对的对数
        int p1 = M;//定义p1先在左组的最右位置
        int p2 = R;//定义p2先在右组的最右位置
        int i = help.length - 1;//辅助数组help，从后往前逆序填值。
        while (p1 >= L && p2 >= M + 1) {
            //如果arr[p1]大于arr[p2]，那么右组中p2(不含)左侧的所有数，都是大于arr[p1]的，给ans累加上这个个数。
            ans += arr[p1] > arr[p2] ? p2 - (M + 1) + 1 : 0;
            //如果左组中的arr[p1]，大于右组中的arr[p2]，就给help[i]赋值arr[p1]，p1--，i--。
            //如果左组中的arr[p1]，小于等于右组中的arr[p2]，就给help[i]赋值arr[p2]，p2--，i--。
            //注意，如果是等于，一定是给help[i]赋值右组的arr[p2]，而不是左组的arr[p1]。否则，对于左组的arr[p1]，我们不知道右组中一共有几个数是小于arr[p1]的。
            help[i--] = arr[p1] > arr[p2] ? arr[p1--] : arr[p2--];
        }
        while (p1 >= L) {//只要p1大于等于左组的0位置
            help[i--] = arr[p1--];//就将arr[p1]赋值给help[i]，p1--，i--。
        }
        while (p2 >= M + 1) {//只要p2大于等于右组的0位置
            help[i--] = arr[p2--];//就将arr[p2]赋值给help[i]，p2--，i--。
        }
        for (i = 0; i < help.length; i++) {//将辅助数组help中的值，全部倒给原数组arr。仅仅是当前一个小组。
            arr[L + i] = help[i];
        }
        return ans;
    }

    //获取逆序对的对数，用于测试。
    public static int reversePairNumberForTest(int[] arr) {
        int ans = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[i]) {//数组中，当任意一个数大于它左侧的任意一个数时，ans就累加一。
                    ans++;
                }
            }
        }
        return ans;
    }

    public static int[] generatorRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) (Math.random() * maxSize) + 2];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * maxValue);
        }
        return arr;
    }

    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    public static void main(String[] args) {
        int maxSize = 100;
        int maxValue = 100;
        int testTimes = 100000;
        System.out.println("test start!");
        for (int i = 0; i < testTimes; i++) {
            int[] arr0 = generatorRandomArray(maxSize, maxValue);
            int[] arr1 = copyArray(arr0);
            int[] arr2 = copyArray(arr0);
            int num1 = reversePairNumber(arr1);
            int num2 = reversePairNumberForTest(arr2);
            if (num1 != num2) {
                System.out.println("oops!");
                System.out.println("arr0 = " + Arrays.toString(arr0));
                System.out.println("num1 = " + num1);
                System.out.println("num2 = " + num2);
                break;
            }
        }
        System.out.println("test end!");
    }

}