前言

本文为本小白🤯学习数据结构的笔记，将以算法题为导向，向大家更清晰的介绍数据结构相关知识（算法题都出自🙌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;
}