[游戏开发]归并排序 + java + 数据结构 + 小和逆序对问题

归并排序

整体就是一个简单递归，左边排好序、右边排好序、让其整体有序

代码

package test3;

public class Test {
  public static void main(String[] args) {

    int[] arr= {3,2,1,5,6,2};
    mergeSort(arr);

    for (int i: arr){
      System.out.printf("%d ", i);
    }
  }

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

  public static void process(int[] arr, int L, int R) {
    if (L == R) {
      return;
    }
    int mid = L + ((R - L) >> 1); // 求中点
    process(arr, L, mid);
    process(arr, mid + 1, R);
    merge(arr, L ,mid ,R);
  }

  public static void 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;

    //移动p1/p2，谁小，将其填充到 help数组中，直到其中一个发生越界
    while (p1 <= M && p2 <= R){
      help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2 ++];
    }

    //p1未越界
    while (p1 <= M){
      help[i++] = arr[p1++];
    }
    //p2未越界
    while (p2 <= R){
      help[i++] = arr[p2++];
    }

    //将help中内容 拷贝会 原来arr中
    for (i = 0; i < help.length; i++){
      arr[L + i] = help[i];
    }
  }
}

思路

首先是理解 归并的上半部分 拆解

  public static void process(int[] arr, int L, int R) {
    if (L == R) {
      return;
    }
    int mid = L + ((R - L) >> 1); // 求中点
    process(arr, L, mid);
    process(arr, mid + 1, R);

拆分数组

紫色是执行顺序

merge合并数组

时间复杂度

提升点

相对于 选择排序，冒泡，插入等排序

没有浪费每次比较后的信息，因此缩减了时间复杂度。

但是需要O（N）的空间复杂度。

小和问题

在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组
的小和。求一个数组 的小和。
例子：[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

阅读世界，共赴山海

423全民读书节，邀你共读