这篇文章来讲分治中的归并排序与前面的分治专题类似需要用到之前学过的排序的思想1.排序数组题目来源912. 排序数组 - 力扣LeetCode这道题是之前的题但是我们换成归并的思想来写归并同样需要用到递归的思想不同的是快排是一个一个进行排序归并则是一块一块进行排序并且归并还需要辅助数组来进行数据的更新因为思想之前排序专题已经讲过了所以这里就不多说了代码如下2.数组中的逆序对题目来源LCR 170. 交易逆序对的总数 - 力扣LeetCode以示例1来分析假如用枚举法将所有情况都枚举出来那时间复杂度为o(n^2)太慢了其实我们可以利用数组的有序性来进行优化在找逆序对的时候我们可以用归并排序来一遍边排一边统计因为左右都是有序的所以我们可以借助这个特性来统计逆序对不用一个一个地进行枚举具体代码如下其中tmp数组是用来暂时储存排好序的左右区间的3.计算右侧⼩于当前元素的个数题目来源315. 计算右侧小于当前元素的个数 - 力扣LeetCode这套题目同样可以用归并排序来进行优化利用归并排序的单调性可以快速地统计个数这道题和上一道题其实是一样的只是因为这道题要求返回的是一个数组因此我们需要多做一些处理代码如下因为我们需要记录某个位置的逆序对的个数但由于进行了归并排序原本的顺序会被打乱所以得用额外的数组来记录未进行排序前数组中元素各自的下标4.翻转对题目来源493. 翻转对 - 力扣LeetCode这道题目和第二道题基本上是一样的唯一的不同是比较的对象是nums[i]和2*num[j]因为这一个不同我们代码的书写也有所不同原本可以将排序和统计个数直接写在同一个循环里面但由于排序和统计的逻辑不同了所以要将这两个过程分开采用先统计再排序的方式又因为2*nums[j]可能超过了整形的最大值所以在这里我们需要做一下强制类型转换将其转换为long long类型代码如下以上就是本篇文章的全部内容了如果对你有帮助可以点个赞支持一下感谢各位的观看TA 关注的仓库 - 陌染青云 (mo-ran-qingyun) - Gitee.com这是我个人的gitee仓库,账号上文章的代码都会发到仓库里有兴趣可以看一下