这篇文章来讲分治中的归并排序，与前面的分治专题类似，需要用到之前学过的排序的思想

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仓库,账号上文章的代码都会发到仓库里，有兴趣可以看一下