整体是递归分治的思想：左边排好序 + 右边排好序 + merge让整体有序。一般我们会暴力破解O(N²)的算法，如果进一步优化：就是可以利用上次计算的结果，不重复计算，不回退 这样的方案。

归并排序算法

  1. package B2_lx.mytx.class04;
  3. import java.util.Arrays;
  5. /**
  6.  * @title: Algorithm
  7.  * @description: 递归
  8.  * @author: 
  9.  * @date: 2022/07/03 05:02
  10.  */
  11. public class Code01_MergeSort {
  12.     public static void mergeSort(int[] arr){
  13.         if (null ==arr || arr.length<2){
  14.             return;
  15.         }
  16.         process(arr,0, arr.length-1);
  17.     }
  18.     public static void process(int[] arr,int L, int R){
  19.         if (L == R){
  20.             return;
  21.         }
  22.         int mid = L + ((R - L) >>1);
  23.         process(arr,L,mid);
  24.         process(arr,mid+1,R);
  25.         merge(arr,L,R,mid);
  26.     }
  27.     public static void merge(int[] arr, int L, int R, int M){
  28.         int[] help = new int[R-L+1];
  29.         int i = 0;
  30.         int p1 = L;
  31.         int p2 = M + 1;
  32.         while (p1 <=M && p2 <= R){
  33.             if (arr[p1] <= arr[p2]){
  34.                 help[i] = arr[p1];
  35.                 i++;
  36.                 p1++;
  37.             }else {
  38.                 help[i] = arr[p2];
  39.                 i++;
  40.                 p2++;
  41.             }
  42.             //help[i++] = arr[p1] >= arr[p2] ? arr[p1++] : arr[p2++];
  43.         }
  44.         while (p1 <= M){
  45.             help[i] = arr[p1];
  46.             i++;
  47.             p1++;
  48.         }
  49.         while (p2 <= R){
  50.             help[i] = arr[p2];
  51.             i++;
  52.             p2++;
  53.         }
  54.         for (int j = 0; j < help.length; j++) {
  55.             arr[L + j] = help[j];
  56.         }
  57.         System.out.println(Arrays.toString(help));
  58.     }
  59.     public static void main(String[] args) {
  60.         int[] arr = new int[]{8,3,5,2,7,4,9,1,6};
  61.         mergeSort(arr);
  62.         System.out.println(Arrays.toString(arr));
  63.     }
  64. }

小和问题

在一个数组中，一个数左边比它小的数的总和，叫数的小和，所有数的小和累加起来，叫数组小和。求数组小和。 例子： [1,3,4,2,5] 1左边比1小的数：没有 3左边比3小的数：1 4左边比4小的数：1、3 2左边比2小的数：1 5左边比5小的数：1、3、4、 2 所以数组的小和为1+1+3+1+1+3+4+2=16 

  1. package B2_lx.mytx.class04;
  3. /**
  4.  * @title: Algorithm
  5.  * @description: 小和问题
  6.  * @author: 北京小桔汇金网络科技有限公司
  7.  * @date: 2022/07/06 23:23
  8.  */
  9. public class Code02_SmallSum {
  11.     public static Integer process(Integer[] arr,int L,int R){
  12.         if (L == R){
  13.             return 0;
  14.         }
  15.         int mid = L + ((R - L)>>1);
  16.         return process(arr,L,mid) + 
  17.                 process(arr,mid +1, R) +
  18.                 merge(arr,L,R,mid);
  19.     }
  20.     public static Integer merge(Integer[] arr,int L,int R,int mid){
  21.         Integer[] help = new Integer[R-L+1];
  22.         int i = 0;
  23.         int p1 = L;
  24.         int p2 = mid +1;
  25.         int result = 0;
  26.         while (p1 <= mid && p2 <=R){
  27.             result += arr[p1] < arr[p2] ? arr[p1] * (R-p2+1) :0;
  28.             help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
  29.             //if (arr[p1] <= arr[p2]){
  30.             //    help[i] = arr[p1];
  31.             //    i++;
  32.             //    p1++;
  33.             //}else {
  34.             //    help[i] = arr[p2];
  35.             //    i++;
  36.             //    p2++;
  37.             //}
  38.         }
  39.         while (p1 <=mid){
  40.             help[i++] = arr[p1++];
  41.         }
  42.         while ((p2 <=R)){
  43.             help[i++] = arr[p2++];
  44.         }
  45.         for (i = 0; i < help.length; i++) {
  46.             arr[L+i] = help[i];
  47.         }
  48.         return result;
  49.     }
  51.     public static void main(String[] args) {
  52.         Integer[] arr = new Integer[]{1,3,4,2,5};
  53.         System.out.println(process(arr,0,4));;
  54.     }
  55. }

逆序对问题

在一个数组中， 任何一个前面的数a，和任何一个后面的数b， 如果(a,b)是降序的，就称为逆序对 返回数组中所有的逆序对

  1. package B2_lx.mytx.class04;
  3. /**
  4.  * @title: Algorithm
  5.  * @description: 逆序对
  6.  * @author: 北京小桔汇金网络科技有限公司
  7.  * @date: 2022/07/07 15:44
  8.  */
  9. public class Code03_ReversePair {
  10.     public static int reversePair(int[] arr){
  11.         if (null == arr || arr.length <2){
  12.             return 0;
  13.         }      
  14.         return process(arr,0,arr.length -1);
  15.     }
  16.     public static int process(int[] arr, int L, int R){
  17.         if (L == R){
  18.             return 0;
  19.         }
  20.         int mid = L + ((R - L)>>1);
  22.         return process(arr,L,mid) + process(arr,mid+1, R) + merge(arr,L,mid,R);
  23.     }
  24.     public static int merge(int[] arr,int L, int mid, int R){
  25.         int[] help = new int[R -L +1];
  26.         int i = help.length -1;
  27.         int p1 = mid;
  28.         int p2 = R;
  29.         int result = 0;
  30.         while (p1 >=L && p2 > mid){
  31.             /*if (arr[p1] <= arr[p2]){
  32.                 help[i] = arr[p2];
  33.                 i--;
  34.                 p2 --;
  35.             } else {
  36.                 help[i] = arr[p1];
  37.                 i--;
  38.                 p1 --;
  39.                 result = result + (p2 - mid);
  40.             }*/
  41.             result += arr[p1] > arr[p2] ? (p2 - mid) : 0;
  42.             help[i--] = arr[p1] > arr[p2] ? arr[p1--] : arr[p2--];
  43.         }
  44.         while (p1>=L){
  45.             help[i--] = arr[p1--];
  46.         }
  47.         while (p2 >mid){
  48.             help[i--] = arr[p2--];
  49.         }
  50.         for ( i = 0; i < help.length; i++) {
  51.             arr[L+i] = help[i];
  52.         }
  53.         return result;
  54.     }
  55.     public static void main(String[] args) {
  56.         int[] arr = new int[]{3,5,1,2,6,4,9,7};
  57.         System.out.println(reversePair(arr));
  58.     }
  59. }

大于两倍问题

求任何一个位置上的子数组（可以利用前缀和） 在一个数组中， 对于每个数num，求有多少个后面的数 * 2 依然<num，求总个数 比如：[3,1,7,0,2] 3的后面有：1，0 1的后面有：0 7的后面有：0，2 0的后面没有 2的后面没有 所以总共有5个

package B2_lx.mytx.class04;

/**
 * @title: Algorithm
 * @description: 在一个数组中，对于每个数num，求有多少个后面的数 * 2 依然<num，求总个数
 * @author: 北京小桔汇金网络科技有限公司
 * @date: 2022/07/08 09:55
 */
public class Code04_BiggerThanRightTwice {
    public static Integer biggerThanRightTwice(int[] arr){
        if (null == arr || 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 m = l + ((r-l)>>1);
        return process(arr,l,m) + process(arr,m+1,r) + merge(arr,l,r,m);
    }
    public static int merge(int[] arr,int l,int r,int m){
        //分成2步，先merge计算出 右边有几个数，乘2后仍然小于 它。
        int winR = m+1;
        int result = 0;
        for (int i = l; i<=m; i++){
            while (winR <=r && arr[i] > (arr[winR] * 2)){
                winR ++;
            }
            result += winR - (m +1);
        }
        // 这里无需merge排序，不需要归并算法的排序操作
        /*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 (int j = 0; j< help.length; j++){
            arr[l+j] = help[j];
        }*/
        return result;
    }
    public static void main(String[] args) {
        int[] arr = new int[]{3,1,7,0,2};
        System.out.println(biggerThanRightTwice(arr));
    }
}