归并排序基础

1.归并排序

2.小和问题

给一个数组[6,3,2,1,6,7]把每一个数左边比当前数小的和加起来

如[0,0,0,0,6,18]，所以和为24

• 采用归并排序，当拷贝左组时产生小和，右组拷贝不产生小和
• 原理是我们求的是当前数a右边比a大的数有几个，那么小和就有几个a

public static int smallSum(int[] arr){
        if (arr == null || arr.length < 2) return 0;
        return process(arr , 0 , arr.length - 1);
    }

    public static int process(int [] arr , int L , int R){
        if (L == R)  return 0;
        int mid = (L + R) / 2;
        return process(arr, L , mid) + process(arr , mid + 1 , R) + merge(arr , L , mid , R);
    }

    public static int merge(int[] arr , int L , int m , int R){
        int[] help = new int [R - L + 1];
        int i = 0;
        int p1 = L ;
        int p2 = m + 1;
        int res = 0;
        while(p1 <= m && p2 <= R) {
            res += arr[p1] < arr[p2] ? (R - p2 + 1)*arr[p1] : 0;
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= m){
            help[i++] = arr[p1++];
        }
        while(p2 <= R){
            help[i++] = arr[p2++];
        }
        for ( i = 0 ; i < help.length ; i++){ //覆盖到原数组当中
            arr[L + i] = help[i];
        }
        return res;
    }

3.逆序对

左边的数大于右边的数 形成一对

• 同理：从右往左拷贝，可以看到左边指针指到的数比右边的数
• [1,2,2,2,3,3,6,6] [1,1,1,1,6,6,7] -> [ 6,6,6,7]
• 左边倒数第二个六时，有四个1会比六小

public static int reverPairNumber(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        return process(arr, 0, arr.length - 1);
    }

    // arr[L..R]既要排好序，也要求逆序对数量返回
    // 所有merge时，产生的逆序对数量，累加，返回
    // 左 排序 merge并产生逆序对数量
    // 右 排序 merge并产生逆序对数量
    public static int process(int[] arr, int l, int r) {
        if (l == r) {
            return 0;
        }
        // l < r
        int mid = l + ((r - l) >> 1);
        return process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r);
    }

    //唯一不同就是在排序的时候是逆序的
    public static int merge(int[] arr, int L, int m, int r) {
        int[] help = new int[r - L + 1];
        int i = help.length - 1;
        int p1 = m;
        int p2 = r;
        int res = 0;
        while (p1 >= L && p2 > m) {
            res += arr[p1] > arr[p2] ? (p2 - m) : 0;
            help[i--] = arr[p1] > arr[p2] ? arr[p1--] : arr[p2--];
        }
        while (p1 >= L) {
            help[i--] = arr[p1--];
        }
        while (p2 > m) {
            help[i--] = arr[p2--];
        }
        for (i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }
        return res;
    }

4. BiggerThanRightTwice

一个数组，每个数的右边有多少个数*2都不如当前这个数

• [1,4,6,8,9] | [1,1,2,3,3,4]
• 当左指针为1时，右指针没有
• 当左指针指向4时，右指针指向1，此时有两个这样的数
• 指针不会回退，因为左组和右组是有序的

    public static int reversePairs(int[] arr){
        if (arr == null || arr.length < 2) return 0;
        return process(arr , 0 , arr.length - 1);
    }

    public static int process(int[] arr , int l , int r){
        if ( l == r){
            return 0;
        }
        int mid = l + ( (r - l) >> 1 );
        return process(arr , l , mid) + process(arr , mid + 1 ,  r) + merge(arr , l , mid ,r);
    }

    public static int merge(int[] arr , int L , int m , int r){
        int ans = 0;

        // 计算过程
        int windowR = m + 1;
        //左组的指针在后移时，右组的指针是不用回退的
        for (int i = L ; i <= m ; i++){
            while (windowR <= r && arr[i] > arr[windowR] * 2){
                windowR++;
            }
            ans += windowR - m - 1;
        }

        int [] help = new int[r - L + 1];
        int i = 0 ;
        int p1 = L;
        int p2 = m + 1;
        while (p1 <= m && p2 <= r){
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= m){
            help[i++] = arr[p1++];
        }
        while (p2 <= r){
            help[i++] = arr[p2++];
        }
        for (i = 0 ; i < help.length ; i++){
            arr[L + i] = help[i];
        }
        return ans;
    }