前言

本文为本小白🤯学习数据结构的笔记，将以算法题为导向，向大家更清晰的介绍数据结构相关知识（算法题都出自🙌B站马士兵教育——左老师的课程，讲的很好，对于想入门刷题的人很有帮助👍）

上面讲了归并排序，这个思想非常好✌️（用了递归来降低时间复杂度），这里我想再写写归并排序的实质，以及用这个思想来解决一些问题。

✌️首先来看看归并排序是怎么实现排序的

package DiGui;

public class hhhguibing {

    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 mid,int R){
        int[] help=new int[R-L+1];
        int i=0,p1=L,p2=mid+1;
        while(p1<=mid&&p2<=R){
            help[i++]=arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
        }
        while(p1<=mid){
            help[i++]=arr[p1++];
        }
        while(p2<=R){
            help[i++]=arr[p2++];
        }
        for (i=0; i < help.length; i++) {
            arr[L+i]=help[i];
        }
    }
}

1.🧩先来解析一下代码结构

public static void process(int[] arr, int L, int R)

这是递归函数，负责“分”的过程。

• L 和 R 表示当前处理的区间 [L, R]。

  • 递归处理左半部分：process(arr, L, mid)
  • 递归处理右半部分：process(arr, mid+1, R)

最后调用 merge(arr, L, mid, R) 把左右两部分合并成有序的

public static void merge(int[] arr, int L, int mid, int R)

• 合并两个有序数组

  • 因为有前面的递归过程，到merge时， [L, mid] 是有序的，[mid+1, R] 也是有序的
  • 创建一个辅助数组 help，用来暂存合并后的结果
  • 用两个指针 p1 和 p2 分别指向左右两个有序区的开头
  • 比较 arr[p1] 和 arr[p2]，把较小的放进 help，对应指针后移
  • 一方遍历完后，把另一方剩下的元素全部复制过去
    最后把 help 中排好序的内容写回原数组 arr[L…R]

💡三、举个例子说明过程

假设数组是：[4, 1, 3, 2]

初始：[4, 1, 3, 2]
        ↓ 分
    [4, 1]     [3, 2]
     ↓           ↓
   [4] [1]     [3] [2]   ← 到底了，开始合并

     ↓           ↓
    [1,4]       [2,3]   ← 合并两个有序对

        ↓ 合并
      [1,2,3,4]         ← 排序完成

🤔那为什么归并排序比普通的排序时间复杂度更低呢？

🌟 核心思想：避免重复的无效比较

一、来看看传统排序（O(n²)）的“时间浪费”在哪？
插入排序为例子：

数组: [5, 4, 3, 2, 1]

插入 4：要和 5 比较一次，移动 5
插入 3：要和 4、5 比较，移动 4、5
插入 2：要和 3、4、5 比较，移动 3、4、5
插入 1：要和 2、3、4、5 比较，移动全部

👉 每个新元素都要从后往前逐个比较，平均要比较 O(n) 次，总共 n 个元素 → 总时间 O(n²)

• 插入排序…等：每一步只“推进”一个元素的位置，过程中做了大量重复且低效的比较和移动。
• 归并排序：通过 分治 + 合并有序数组 的方式，让每一次比较都“更有价值”。

🌏归并排序扩展问题：

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

为了更直观的来看，用递归方法解小和问题更高效，我先写（O(n²)）的暴力解法：

public static int smallSum (int[] arr) {
    int sum = 0;
    for (int i = 1; i < arr.length; i++) {
        for (int j = 0;j < i;j++) {
            if (arr[j] < arr[i]) {
                sum += arr[j];
             }
         }
     }
     return sum;
}        

🚀 高效解法：利用 归并排序 → O(n log n)

先解释一下 ：

这个是把小和问题先转化了一下，将原问题（每一个数左边比当前数小的数累加起来），转化为每个数右边有几个比它大，就说明这个数本身，被累加了几次。
例子：[1,3.4.2.5]1右边比1大的数，有4个：3右边比3大的数，有2个；4右边比4大的数，有1个; 2右边比2大的数，有1个；5右边比5大的数，没有；所以小和为1 * 4+3 * 2+4 * 1+2 * 1+5 * 0=16；

那么我们只需要统计每个数右边有几个比它大，就可以了

public static void 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 mid,int R){
    int help=new int [R-L+1];
    int i=0,p1=L,p2=mid+1;
    int res=0;//记录小和数
    while(p1<=mid&&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<=mid) {
       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;
}

逆序对问题：
逆序对问题在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，请打印所有逆序对数。

这道题一样的，刚才小和问题是求每个数右边有几个比它大，这个是求每个数右边有几个比它小

public static void 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 mid,int R){
    int help=new int [R-L+1];
    int i=0,p1=L,p2=mid+1;
    int res=0;//记录小和数
    while(p1<=mid&&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<=mid) {
       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;
}

小白啊！！！写的不好轻喷啊🤯如果觉得写的不好，点个赞吧🤪（批评是我写作的动力）

…。。。。。。。。。。。…

…。。。。。。。。。。。…