《算法题讲解指南：优选算法-分治-归并》--47.归并排序，48.数组中的逆序对
🔥小叶-duck：个人主页
❄️个人专栏：《Data-Structure-Learning》
《C++入门到进阶&自我学习过程记录》《算法题讲解指南》--优选算法
✨未择之路，不须回头
已择之路，纵是荆棘遍野，亦作花海遨游
目录
47.归并排序
题目链接：
215. 数组912. 排序数组 - 力扣（LeetCode）215. 数组
题目描述：
题目示例：
解法(归并排序)：
算法思路：
归并排序的流程充分的体现了「分而治之」的思想，大体过程分为两步：
分：将数组一分为二为两部分，一直分解到数组的长度为1，使整个数组的排序过程被分为「左半部分排序」+「右半部分排序」;
治：将两个较短的「有序数组合并成一个长的有序数组」，一直合并到最初的长度。
C++算法代码：
class Solution { public: //归并排序的算法 vector<int> tmp; //用于存放两个有序数组合并后的结果 void mergesort(vector<int>& nums, int left, int right) { if(left == right) { return; } //1、选择中间点划分区间 int mid = (right - left) / 2 + left; //将数组分成两块：[left, mid] [mid + 1, right] //2、把左右区间排序 mergesort(nums, left, mid); mergesort(nums, mid + 1, right); //3、将两个数组合并成一个有序数组 int cur1 = left, cur2 = mid + 1, i = 0; while(cur1 <= mid && cur2 <= right) { tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++]; } //还有一边数组没有合并完 while(cur1 <= mid) { tmp[i++] = nums[cur1++]; } while(cur2 <= right) { tmp[i++] = nums[cur2++]; }//只会进其中一个循环 //将两个数组有序合并到tmp中后，再还原给原数组nums对应部分位置 for(int i = left; i <= right; i++) { nums[i] = tmp[i - left]; //tmp数组每次都是以开头下标0的位置合并两个数组 } } vector<int> sortArray(vector<int>& nums) { //归并实现： tmp.resize(nums.size()); mergesort(nums, 0, nums.size() - 1); return nums; } };算法总结及流程解析：
48.数组中的逆序对
题目链接：
LCR 170. 交易逆序对的总数 - 力扣（LeetCode）
题目描述：
题目示例：
解法（利用归并排序的过程——分治）：
算法思路：
⽤归并排序求逆序数是很经典的⽅法，主要就是在归并排序的合并过程中统计出逆序对的数量，也就是在合并两个有序序列的过程中，能够快速求出逆序对的数量。
我们将这个问题分解成⼏个⼩问题，逐⼀破解这道题。
(注意：默认都是升序，如果掌握升序的话，降序的归并过程也是可以解决问题的。)
先解决第⼀个问题，为什么可以利⽤归并排序？
如果我们将数组从中间划分成两个部分，那么我们可以将逆序对产⽣的⽅式划分成三组：
逆序对中两个元素：全部从左数组中选择
逆序对中两个元素：全部从右数组中选择
逆序对中两个元素：⼀个选左数组另⼀个选右数组
根据排列组合的分类相加原理，三种种情况下产⽣的逆序对的总和，正好等于总的逆序对数量。
⽽这个思路正好匹配归并排序的过程：
先排序左数组；
再排序右数组；
左数组和右数组合⼆为⼀。
因此，我们可以利⽤归并排序的过程，先求出左半数组中逆序对的数量，再求出右半数组中逆序对的数量，最后求出⼀个选择左边，另⼀个选择右边情况下逆序对的数量，三者相加即可。
解决第⼆个问题，为什么要这么做？
在归并排序合并的过程中，我们得到的是两个有序的数组。我们是可以利⽤数组的有序性，快速统计出逆序对的数量，⽽不是将所有情况都枚举出来。• 最核⼼的问题，如何在合并两个有序数组的过程中，统计出逆序对的数量？合并两个有序序列时求逆序对的⽅法有两种：
1. 快速统计出某个数前⾯有多少个数⽐它⼤；
2. 快速统计出某个数后⾯有多少个数⽐它⼩；
C++算法代码：
class Solution { public: int count = 0; vector<int> tmp;//用于存放两个有序数组合并后的结果 int reversePairs(vector<int>& record) { tmp.resize(record.size()); mergesort(record, 0, record.size() - 1); return count; } void mergesort(vector<int>& nums, int left, int right) { if(left >= right)//正常归并排序递归的结束条件不用包含left>right //因为归并是分两块，最小的情况就是两个数分成各一个，不存在越界的情况 //但是此题有空数组的案例，所以一开始left=0，right=-1，要考虑在内 { return; } //1、选择中间点划分区间 int mid = (right - left) / 2 + left; //将数组分成两块：[left, mid] [mid + 1, right] //2、把左右区间排序 mergesort(nums, left, mid); mergesort(nums, mid + 1, right); //3、判断两个有序数组一左一右的逆序对个数，并且将两个数组合并成一个有序数组 int cur1 = left, cur2 = mid + 1, i = 0; //(1)将数组排成升序的思路： while(cur1 <= mid && cur2 <= right) { if(nums[cur1] <= nums[cur2]) { tmp[i++] = nums[cur1++]; } else { //当第一次遇见nums[cur1] > nums[cur2],说明[cur1, mid]区间所有值都大于nums[cur2] //计算当前nums[cur2]的逆序对个数 count += mid - cur1 + 1; tmp[i++] = nums[cur2++]; } } //(2)将数组排成降序的思路： // while(cur1 <= mid && cur2 <= right) // { // if(nums[cur1] > nums[cur2]) // { // count += right - cur2 + 1; // tmp[i++] = nums[cur1++]; // } // else // { // tmp[i++] = nums[cur2++]; // } // } //处理还没有排序的剩余部分 while(cur1 <= mid) { tmp[i++] = nums[cur1++]; } while(cur2 <= right) { tmp[i++] = nums[cur2++]; } //将两个数组有序合并到tmp中后，再还原给原数组nums对应部分位置 for(int i = left; i <= right; i++) { nums[i] = tmp[i - left]; //tmp数组每次都是以开头下标0的位置合并两个数组 } } };算法总结及流程解析：
结束语
到此，47.归并排序，48.数组中的逆序对 这两道算法题就讲解完了。 归并排序采用分治思想，先将数组不断二分至单个元素，再通过有序合并操作完成排序，时间复杂度为O(nlogn)。希望大家能有所收获！
