小叶-duck个人主页❄️个人专栏《Data-Structure-Learning》《C入门到进阶自我学习过程记录》《算法题讲解指南》--优选算法✨未择之路不须回头已择之路纵是荆棘遍野亦作花海遨游目录47.归并排序题目链接题目描述题目示例解法(归并排序)算法思路C算法代码算法总结及流程解析48.数组中的逆序对题目链接题目描述题目示例解法利用归并排序的过程——分治算法思路C算法代码算法总结及流程解析结束语47.归并排序题目链接215. 数组912. 排序数组 - 力扣LeetCode215. 数组题目描述题目示例解法(归并排序)算法思路归并排序的流程充分的体现了「分而治之」的思想大体过程分为两步分将数组一分为二为两部分一直分解到数组的长度为1使整个数组的排序过程被分为「左半部分排序」「右半部分排序」;治将两个较短的「有序数组合并成一个长的有序数组」一直合并到最初的长度。C算法代码class Solution { public: //归并排序的算法 vectorint tmp; //用于存放两个有序数组合并后的结果 void mergesort(vectorint 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的位置合并两个数组 } } vectorint sortArray(vectorint 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; vectorint tmp;//用于存放两个有序数组合并后的结果 int reversePairs(vectorint record) { tmp.resize(record.size()); mergesort(record, 0, record.size() - 1); return count; } void mergesort(vectorint 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; //(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)。希望大家能有所收获