数组中的逆序对

题目：

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

例如在数组{7, 5, 6, 4}中，一共存在5个逆序对，分别是（7，6）、（7，5）、（7，4）、（6、4）和（5，4）。

解决方法：
用递归排序思想：

import java.util.Arrays;

/**
 * @ClassName TestDemo51
 * @Description 面51
 * @Author lzq
 * @Date 2019/1/23 18:04
 * @Version 1.0
 **/
public class TestDemo51 {
    int count = 0;  //逆序对个数

    /**
     * 找逆序对个数的主方法
     * @param array
     */
    public void pair(int[] array) {
       if(array == null || array.length == 0) {
           return ;
       }
       for(int i = 1;i < array.length;i = i*2) {
           merger(array,i);
       }
    }


    /**
     * 利用递归排序思想找逆序对的核心方法
     * @param array
     * @param gap
     */
    private void merger(int[] array, int gap) {
        int s1 = 0;
        int e1 = s1+gap-1;
        int s2 = e1+1;
        int e2 = s2+gap-1 < array.length ? s2+gap-1 : array.length-1;
        int[] temp = new int[array.length];
        int index = 0;
        while(s2 < array.length) {
            while(s1 <= e1 && s2 <= e2) {
                if(array[s1] < array[s2]) {
                    temp[index++] = array[s1++];
                }else {
                    //只需要在递归排序的核心方法里面添加这一句代码就够了
                    if(array[s1] > array[s2]) {
                        count += e1-s1+1;
                    }
                    temp[index++] = array[s2++];
                }
            }

            while (s1 <= e1) {
                temp[index++] = array[s1++];
            }
            while (s2 <= e2){
                temp[index++] = array[s2++];
            }
            s1 = e2+1;
            e1 = s1+gap-1;
            s2 = e1+1;
            e2 = s2+gap-1 < array.length ? s2+gap-1 : array.length-1;
        }

        while (s1 < array.length) {
            temp[index++] = array[s1++];
        }
        System.arraycopy(temp,0,array,0,temp.length);
    }
}

测试代码：

public static void main(String[] args) {
        TestDemo51 testDemo51_1 = new TestDemo51();
        TestDemo51 testDemo51_2 = new TestDemo51();
        TestDemo51 testDemo51_3 = new TestDemo51();
        int[] x = {7,5,6,4};
        int[] y = {3,7,4,6};
        int[] z = {7,5,6,4,3};
        testDemo51_1.pair(x);
        System.out.println(Arrays.toString(x));
        System.out.println(testDemo51_1.count);
        testDemo51_2.pair(y);
        System.out.println(Arrays.toString(y));
        System.out.println(testDemo51_2.count);
        testDemo51_3.pair(z);
        System.out.println(Arrays.toString(z));
        System.out.println(testDemo51_3.count);
    }

运行结果：

[4, 5, 6, 7]
5
[3, 4, 6, 7]
2
[3, 4, 5, 6, 7]
9