4.求逆序对的个数

思路：使用归并排序的方法

逆序对的个数可以看成三个部分组成

1.全部在分界点左边的逆序对的个数

2.全部在分界点右边逆序对的个数

3.分别在分界点左右的逆序对的个数

---

可以使用方法mergeSort (int l, int r)。

前两种情况的逆序对的总数为：ans = mergeSort(l, mid) + mergeSort(mid + 1, r)

第三种情况思路：

归并排序的思想使用双指针 i 指针指向左边的数组，j 指针指向右边的数组，当遇到 j 指向的大于 i 指向的时候，恰好i 左边的全部小于j 。此时就是第三种情况的逆序对的个数。

代码如下：

package cn.liyi.day02;

public class Demo788 {
    public static int[] p = {2, 3, 4, 5, 6, 1};
    public static int[] temp = new int[6];

    public static void main(String[] args) {
        for (int i = 0; i < 5; i++) {
            System.out.print(p[i]);
        }
        System.out.println();
        long ans = mergeSort(0, 5);
        System.out.println(ans);
    }

    
    public static long mergeSort(int l, int r) {
        if (l == r)
            return 0;
        int mid = (l + r) / 2;
        long ans = mergeSort(l, mid) + mergeSort(mid + 1, r);
        int k = 0, i = l, j = r;
        while (i <= mid && j <= r) {
            if (p[i] <= p[j])
                temp[k++] = p[i++];
            else {
                temp[k++] = p[j++];
                ans += mid - i + 1;
            }
        }
        while (i <= mid)
            temp[k++] = p[i++];
        while (j <= r)
            temp[k++] = p[j++];
        for (i = l, j = 0; i < r; i++, j++) {
            p[i] = temp[j];
        }
        return ans;
    }

}