手绘图解，带你了解归并排序。
归并排序
什么是归并排序？
“归并操作”（合并子序列）原理图解：
归并排序实现原理+图解
归并排序代码实现
算法分析
时间复杂度
空间复杂度
稳定性
归并排序在实际题目中的运用
题目一、排序数组
题目二、剑指Offer 51.数组中的逆序对
题目三、计算右侧小于当前元素的个数
归并排序
什么是归并排序？
归并排序，就是建立在“归并操作”基础上的一种排序方法。
归并操作：将两个有序的子序列合并成一个有序序列的过程。
我们可以把归并排序简单地理解成———将两个或两个以上已经排序好了的子序列“归并”为一个有序序列的过程。
“归并操作”（合并子序列）原理图解：
（文章中图解均由作者亲手绘制，诚意满满，请多多鼓励…）
1.首先需要申请额外的空间（L3）用来放置归并后结果，然后就是设置指针分别指向有序子序列的首位置元素：
2.比较指针指向元素的大小，较小的元素取出来，放置于提前申请好的空间当中，最后将指针向后挪动一格，之后重复操作即可：
3.当某一个指针指向了子序列的结尾，我们就可以将另一个子序列剩余的元素通通放到额外申请的空间（L3）中啦！（为了让效果更加明显，我将为L2提供增高服务( •̀ ω •́ )✧）
归并排序实现原理+图解
基本原理：将大小为N的序列分割成N个长度为1的子序列，将相邻的一对子序列进行“归并操作”，形成N/2（+1）个长度为2(或1)的有序子序列；不断重复相邻子序列的“归并操作”，直到剩下一个长度为N的有序序列。
图解：
当我们将图中一步步合并操作拆分开来单独看，不难发现这正是上文提到的“归并操作”，即将两个有序的子序列合并成一个有序序列。
在实现代码时，我们换个角度理解，使用分而治之的思想，
即将原序列分成两个等长的子序列，再使用递归排序，最后用“归并操作”合并成完整的有序序列。
归并排序代码实现
import java.util.Arrays; /** * @author .29. * @create 2022-09-07 7:25 * * L / l: 数组的第一个元素下标（left左边） * R： 数组的最后一个元素下标（right右边） * mid / M:数组中间位置下标 */ public class MergeSort { public static void main(String[] args) { int[] arr = {44,12,59,36,62,43,94,7,35,52,85};//初始数组 //调用递归函数排序数组：Msort(arr,0,arr.length-1) //使用toString方法将数组转化为字符串，方便打印： String arrayBefore = Arrays.toString(arr); String arrayAfter = Arrays.toString(Msort(arr,0,arr.length-1)); System.out.println("排序前数组："+arrayBefore); System.out.println("排序后数组："+arrayAfter); } //递归排序方法（函数） public static int[] Msort(int[] arr,int L,int R){ if(L == R) //判断，如果数组只有一个元素，直接返回 return arr; //当初始数组长度未知时，上面步骤不可或缺。 //中间下标：(L + R) / 2 相当于 L+((R-L)/2) 相当于 L+(R-L) >> 1 //mid = L + ((R-L) >> 1) 不易出错且运行速度更快 int mid = L + ((R-L) >> 1); //中间下标 //递归排序左半边子序列，使其有序 Msort(arr,L,mid); //递归排序右半边子序列 Msort(arr,mid + 1,R); //归并操作两个排序好的子序列（合并子序列） Merge(arr,L,mid,R); return arr; } //归并操作方法（函数） public static void Merge(int[] arr,int L,int M, int R){ //申请额外的空间（temp[]）来存放归并后的序列 int[] temp = new int[R-L+1]; //数组大小与初始数组一致 int index = 0; //记录temp[]的下标 int r = M + 1; //r代表右半子序列的首元素下标 int l = L; while(l <= M && r <= R) //比较大小，较小的元素放入申请的空间中，同时位置向后挪动一格 temp[index++] = arr[l]<=arr[r]?arr[l++]:arr[r++]; //左半子序列先抵达结尾，将右子序列剩余元素放入空间 while(r <= R) temp[index++] = arr[r++]; //右半子序列先抵达结尾，将左子序列剩余元素放入空间 while(l <= M) temp[index++] = arr[l++]; //将排序好的完整序列放入原数组中 for(int i = 0;i < R-L+1; i++){ arr[L+i] = temp[i]; } } }
控制台输出结果：
算法分析
时间复杂度
因为算法当中运用了递归，所以我们可以借助master公式。
master公式：也叫主定理。它提供了一种通过渐近符号表示递推关系式的方法。 应用Master定理可以很简便的求解递归方程。
master公式（ T [n] = a*T[n/b] + O (N^d) ）
master公式结论：
①当d<logb a时，时间复杂度为O(N^(logb a))
②当d=logb a时，时间复杂度为O((N^d)*logN)
③当d>logb a时，时间复杂度为O(N^d)
前文递归函数中有两个子问题：
//递归排序左半边子序列，使其有序 Msort(arr,L,mid); //递归排序右半边子序列 Msort(arr,mid + 1,R);
因为两个子序列由原始序列平等划分而来，所有两个子问题的规模一样都为n/2
有两个递归子问题，即a = 2 子问题规模为 n / 2，即b = 2
函数中剩下的过程：
//归并操作两个排序好的子序列（合并子序列） Merge(arr,L,mid,R);
即：
//归并操作方法（函数） public static void Merge(int[] arr,int L,int M, int R){ //申请额外的空间（temp[]）来存放归并后的序列 int[] temp = new int[R-L+1]; //数组大小与初始数组一致 int index = 0; //记录temp[]的下标 int r = M + 1; //r代表右半子序列的首元素下标 int l = L; while(l <= M && r <= R) //比较大小，较小的元素放入申请的空间中，同时位置向后挪动一格 temp[index++] = arr[l]<=arr[r]?arr[l++]:arr[r++]; //左半子序列先抵达结尾，将右子序列剩余元素放入空间 while(r <= R) temp[index++] = arr[r++]; //右半子序列先抵达结尾，将左子序列剩余元素放入空间 while(l <= M) temp[index++] = arr[l++]; //将排序好的完整序列放入原数组中 for(int i = 0;i < R-L+1; i++){ arr[L+i] = temp[i]; }
不难看出，剩下过程的时间复杂度为O(n).
这里n的指数为1，即：d = 1
也就满足条件：②d=logb a时，时间复杂度为O((N^d)*logN)
时间复杂度：O（nlogn）
空间复杂度
需要用到一个临时数组，单次归并操作开辟的最大空间是n
空间复杂度： O（n）
稳定性
归并排序是一种稳定的排序算法。
当遇到两个元素相等的情况时，优先将左半边子序列的元素放入额外申请空间中，保证相对位置不变即可。
归并排序在实际题目中的运用
题目一、排序数组
LeetCode原题链接：排序数组
题目描述：给你一个整数数组 nums，请你将该数组升序排列。
代码实现：
此题思路以及实现与上文提到的归并排序代码实现基本一致，我就再敲了一遍当作复习。
class Solution { public int[] sortArray(int[] nums) { if(nums == null || nums.length < 2) return nums; Msort(nums,0,nums.length-1); return nums; } public int[] Msort(int[] arr,int L,int R){ if(L == R)//数组只有一个元素，直接返回。 return arr; int mid = L + ((R - L) >> 1);//中间元素下标 //递归排序左子序列 Msort(arr,L,mid); //递归排序右子序列 Msort(arr,mid+1,R); //归并操作 Merge(arr,L,mid,R); return arr; } public void Merge(int[] arr,int L,int Mid,int R){ //创建临时数组 int[] temp = new int[R-L+1];//尾元素下标-头元素下标+1为数组长度 int index = 0;//表示临时数组下标 int l = L;//首元素下标 int r = Mid + 1;//右有序子序列首元素下标 while(l <= Mid && r <= R) temp[index++] = arr[l] < arr[r]?arr[l++]:arr[r++]; while(l <= Mid) temp[index++] = arr[l++]; while(r <= R) temp[index++] = arr[r++]; for(int i = 0;i < R-L+1; ++i){ arr[L+i] = temp[i]; } } }
LeetCode提交结果如下：
题目二、剑指Offer 51.数组中的逆序对
LeetCode原题链接：数组中的逆序对
题目描述：
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。 输入一个数组，求出这个数组中的逆序对的总数。
思路：
在“归并操作”比较两个子序列元素大小时，只需要在每次出现左子序列元素>右子序列元素情况时，即达成逆序对情况时，记录并累加出现的次数即可。
其余思路与上文提到的的归并排序代码实现基本一致。
注意：
如下图，当左子序列元素>右子序列元素时，因为两个子序列是有序的，所以应该记录的逆序对个数：
count = mid - l + 1;
class Solution { public int count = 0;//设置全局变量，记录逆序对个数 public int reversePairs(int[] nums) { if(nums == null || nums.length < 2) return 0; return Msort(nums,0,nums.length-1); } public int Msort(int[] arr,int L,int R){ if(L == R)//数组只有一个元素，直接返回。 return 0; int mid = L + ((R - L) >> 1);//中间元素下标 //递归排序左子序列 Msort(arr,L,mid); //递归排序右子序列 Msort(arr,mid+1,R); //归并操作,返回count return Merge(arr,L,mid,R); } public int Merge(int[] arr,int L,int Mid,int R){ //创建临时数组 int[] temp = new int[R-L+1];//尾元素下标-头元素下标+1为数组长度 int index = 0;//表示临时数组下标 int l = L;//首元素下标 int r = Mid + 1;//右有序子序列首元素下标 while(l <= Mid && r <= R){ if(arr[l] <= arr[r]){ temp[index++] = arr[l++]; }else if(arr[l] > arr[r]){ //左序列元素大于右序列元素，达成逆序对条件 temp[index++] = arr[r++]; //左子序列结尾下标-当前匀速下标+1即为达成逆序对的个数 count += Mid-l+1; } } while(l <= Mid)//右子序列抵达结尾，剩余元素存入临时数组 temp[index++] = arr[l++]; while(r <= R)//左子序列抵达结尾，剩余元素存入临时数组 temp[index++] = arr[r++]; //将归并排序好的完整有序序列覆盖原序列 for(int i = 0;i < R-L+1; ++i){ arr[L+i] = temp[i]; } //返回逆序对数量 return count; } }
提交结果：
题目三、计算右侧小于当前元素的个数
（更新于：2022.9.8）
LeetCode原题链接：计算右侧小于当前元素的个数
题目描述：给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例 输入：nums = [5,2,6,1] 输出：[2,1,1,0] 解释： 5 的右侧有 2 个更小的元素 (2 和 1) 2 的右侧仅有 1 个更小的元素 (1) 6 的右侧有 1 个更小的元素 (1) 1 的右侧有 0 个更小的元素
解题思路：
功能实现的思路与上一道逆序对的算法题相似，都是以归并排序为基础，在特定情况下记录符合条件的元素个数。
特定条件：当左序列元素需要放入临时空间时，就说明右序列元素前的元素都小于左序列当前元素，可画图辅助理解。
需要注意的细节是，count[i] 的值需要与初始序列相应元素下标保持一致，但实际上归并排序后初始序列元素的下标已经发生改变。
于是难点就在如何让记录下来的 count[i] 的值放置在对应位置。
为了解决这一难点，我们需要申请空间来存放初始数组的下标，让元素与下标同步移动，从而解决下标不匹配的问题。
代码：
class Solution { int[] index; //存放元素下标的数组 int[] counts; //用于记录右侧小于当前元素个数 int[] tempIndex; //临时存放排序后的下标 int[] temp; //临时存放归并排序后的完整序列 public List<Integer> countSmaller(int[] nums) { //数组的空间与初始序列长度保持一致 this.index = new int[nums.length]; this.counts = new int[nums.length]; this.tempIndex = new int[nums.length]; this.temp = new int[nums.length]; //记录初始序列各元素下标 for(int i = 0;i < nums.length; ++i){ index[i] = i; } Msort(nums,0,nums.length-1);//递归排序序列 //创建集合对象，用于存放counts数组元素 List<Integer> list = new ArrayList<Integer>(); //增强for循环，将counts数组的元素依次放入集合中 for(int num: counts){ list.add(num); } return list; } //递归函数 public void Msort(int[] arr,int L,int R){ if(L == R)//数组长度为1，直接返回 return; int mid = L + ((R-L) >> 1);//中间元素下标,相当于(R+L)/2 //递归排序左子序列 Msort(arr,L,mid); //递归排序右子序列 Msort(arr,mid+1,R); //归并排序函数 Merge(arr,L,mid,R); } public void Merge(int[] arr,int L,int Mid,int R){ int l = L;//左子序列起点 int r = Mid+1;//右子序列起点 int p = L;//临时空间起点 while(l <= Mid && r <= R){ if(arr[l] <= arr[r]){//当左序列元素小于等于右序列元素 temp[p] = arr[l];//复制入临时空间 tempIndex[p] = index[l];//对应下标也复制入临时空间 //右序列元素前面的元素满足条件，累加进临时空间内的对应位置 counts[index[l]] += (r-Mid-1); //指针向后挪动一格 l++;p++; }else{ temp[p] = arr[r]; tempIndex[p] = index[r]; ++p;++r; } } while(l <= Mid){ temp[p] = arr[l]; tempIndex[p] = index[l]; counts[index[l]] += (r-Mid-1); ++p;++l; } while(r <= R){ temp[p] = arr[r]; tempIndex[p] = index[r]; ++p;++r; } for(int j = L;j <= R;++j){ arr[j] = temp[j];//排序后序列覆盖初始序列 index[j] = tempIndex[j];//排序后下标顺序覆盖原始下标顺序 } } }
提交结果：
这是我人生中的第一篇技术博客，十分感谢能读到最后的你，你的认同与支持就是对我最大的鼓励。 我正行走在成长的道路上，希望能一直坚持下去，也希望这一路能有你的陪伴，共勉，屏幕前的友人。
