【算法题】归并排序

归并排序是基于分治思想的经典排序算法，核心逻辑是“拆分→排序→合并”：将数组递归拆分为子数组，分别排序后再合并为有序数组。它是稳定排序（相同元素相对位置不变），时间复杂度稳定为O(nlog⁡n)O(n\log n)O(nlogn)，不仅能解决排序问题，更能高效处理“逆序对统计”“右侧元素计数”等衍生问题。本文通过4道经典题目，拆解归并排序在不同场景下的解题思路与代码实现。

一、排序数组

题目描述：
实现归并排序，将整数数组升序排列（不能使用内置排序函数，要求时间复杂度O(nlog⁡n)O(n\log n)O(nlogn)）。

示例：

• 输入：nums = [5,2,3,1]，输出：[1,2,3,5]

解题思路：
标准归并排序的三步流程：

1. 拆分：将数组从中间拆分为左右两个子数组，递归排序子数组。
2. 合并：用临时数组tmp合并两个有序子数组（双指针遍历左右子数组，取较小值存入临时数组）。
3. 还原：将临时数组的有序元素写回原数组的对应区间。

完整代码：

classSolution{vector<int>tmp;public:vector<int>sortArray(vector<int>&nums){tmp.resize(nums.size());mergeSort(nums,0,nums.size()-1);returnnums;}voidmergeSort(vector<int>&nums,intleft,intright){if(left>=right)return;// 1. 取中间点intmid=(left+right)>>1;// 2. 分区间排序mergeSort(nums,left,mid);mergeSort(nums,mid+1,right);// 3. 合并intcur1=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++];// 4. 还原for(inti=left;i<=right;i++){nums[i]=tmp[i-left];}}};

复杂度分析：

• 时间复杂度：O(nlog⁡n)O(n\log n)O(nlogn)，拆分的递归深度为O(log⁡n)O(\log n)O(logn)，每层合并的时间为O(n)O(n)O(n)。
• 空间复杂度：O(n)O(n)O(n)，临时数组tmp存储合并结果（递归栈深度为O(log⁡n)O(\log n)O(logn)，可忽略）。

二、交易逆序对的总数（经典逆序对）

题目描述：
给定股票交易记录数组record，若前一天股价高于后一天股价，视为一个“交易逆序对”，返回逆序对总数。

示例：

• 输入：record = [9,7,5,4,6]，输出：8（逆序对包括(9,7)、(9,5)等）

解题思路：
在归并排序的合并阶段统计逆序对：

1. 拆分并递归排序左右子数组，同时统计子数组内部的逆序对。
2. 合并时，若左子数组的当前元素nums[cur1] > nums[cur2]，说明左子数组中cur1~mid的所有元素都与nums[cur2]构成逆序对，逆序对数量增加mid - cur1 + 1。
3. 合并完成后，将有序元素写回原数组。

完整代码：

classSolution{vector<int>tmp;public:intreversePairs(vector<int>&record){tmp.resize(record.size());returnmergeSort(record,0,record.size()-1);}intmergeSort(vector<int>&nums,intleft,intright){if(left>=right)return0;intret=0;// 1. 找中点划分区间intmid=(left+right)>>1;// 2. 找左/右区间个数并排序ret+=mergeSort(nums,left,mid);ret+=mergeSort(nums,mid+1,right);inti=0,cur1=left,cur2=mid+1;// 3. 一左一右找并合并排序while(cur1<=mid&&cur2<=right){if(nums[cur1]<=nums[cur2])tmp[i++]=nums[cur1++];else{ret+=mid-cur1+1;tmp[i++]=nums[cur2++];}}// 4. 处理剩余元素while(cur1<=mid)tmp[i++]=nums[cur1++];while(cur2<=right)tmp[i++]=nums[cur2++];// 5. 还原for(inti=left;i<=right;i++)nums[i]=tmp[i-left];returnret;}};

复杂度分析：

• 时间复杂度：O(nlog⁡n)O(n\log n)O(nlogn)，排序与统计逆序对的时间均为O(nlog⁡n)O(n\log n)O(nlogn)。
• 空间复杂度：O(n)O(n)O(n)，临时数组tmp存储合并结果。

三、计算右侧小于当前元素的个数（带索引的逆序统计）

题目描述：
返回数组counts，其中counts[i]是nums[i]右侧小于nums[i]的元素数量。

示例：

• 输入：nums = [5,2,6,1]，输出：[2,1,1,0]

解题思路：
在归并排序中维护元素的原始索引，从而统计每个元素右侧更小的元素数量：

1. 用index数组记录元素的原始索引，合并时同步维护索引的顺序。
2. 合并阶段，若左子数组的当前元素nums[cur1] > nums[cur2]，说明nums[cur1]右侧存在right - cur2 + 1个更小的元素，将该值累加到ret[index[cur1]]。
3. 合并完成后，同步还原nums和index数组的顺序。

完整代码：

classSolution{vector<int>ret;vector<int>index;inttmpNums[500010];inttmpIndex[500010];public:vector<int>countSmaller(vector<int>&nums){intn=nums.size();ret.resize(n);index.resize(n);for(inti=0;i<n;i++)index[i]=i;mergeSort(nums,0,n-1);returnret;}voidmergeSort(vector<int>&nums,intleft,intright){if(left>=right)return;intmid=(left+right)>>1;mergeSort(nums,left,mid);mergeSort(nums,mid+1,right);intcur1=left,cur2=mid+1,i=0;while(cur1<=mid&&cur2<=right){if(nums[cur1]<=nums[cur2]){tmpNums[i]=nums[cur2];tmpIndex[i++]=index[cur2++];}else{ret[index[cur1]]+=right-cur2+1;tmpNums[i]=nums[cur1];tmpIndex[i++]=index[cur1++];}}while(cur1<=mid){tmpNums[i]=nums[cur1];tmpIndex[i++]=index[cur1++];}while(cur2<=right){tmpNums[i]=nums[cur2];tmpIndex[i++]=index[cur2++];}for(inti=left;i<=right;i++){nums[i]=tmpNums[i-left];index[i]=tmpIndex[i-left];}}};

复杂度分析：

• 时间复杂度：O(nlog⁡n)O(n\log n)O(nlogn)，排序与统计的时间均为O(nlog⁡n)O(n\log n)O(nlogn)。
• 空间复杂度：O(n)O(n)O(n)，存储临时数组和索引数组。

四、翻转对（扩展逆序对）

题目描述：
若i < j且nums[i] > 2 * nums[j]，则称(i,j)为“翻转对”，返回数组中的翻转对总数。

示例：

• 输入：nums = [1,3,2,3,1]，输出：2（翻转对为(3,1)、(3,1)）

解题思路：
在归并排序的合并前阶段统计翻转对：

1. 拆分并递归排序左右子数组，同时统计子数组内部的翻转对。
2. 合并前，用双指针遍历左右子数组：若nums[cur1] > 2 * nums[cur2]，则左子数组中cur1~mid的所有元素都与nums[cur2]构成翻转对，翻转对数量增加mid - cur1 + 1，并右移cur2；否则右移cur1。
3. 统计完成后，合并两个有序子数组并写回原数组。

完整代码：

classSolution{inttmp[50010];public:intreversePairs(vector<int>&nums){returnmergeSort(nums,0,nums.size()-1);}intmergeSort(vector<int>&nums,intleft,intright){if(left>=right)return0;intret=0;intmid=(left+right)>>1;ret+=mergeSort(nums,left,mid);ret+=mergeSort(nums,mid+1,right);// 合并前统计翻转对intcur1=left,cur2=mid+1;while(cur1<=mid){while(cur2<=right&&nums[cur1]/2.0<=nums[cur2])cur2++;if(cur2>right)break;ret+=right-cur2+1;cur1++;}// 合并两个有序子数组cur1=left,cur2=mid+1;inti=0;while(cur1<=mid&&cur2<=right)tmp[i++]=nums[cur1]<=nums[cur2]?nums[cur2++]:nums[cur1++];while(cur1<=mid)tmp[i++]=nums[cur1++];while(cur2<=right)tmp[i++]=nums[cur2++];for(inti=left;i<=right;i++)nums[i]=tmp[i-left];returnret;}};

复杂度分析：

• 时间复杂度：O(nlog⁡n)O(n\log n)O(nlogn)，统计翻转对与合并的时间均为O(nlog⁡n)O(n\log n)O(nlogn)。
• 空间复杂度：O(n)O(n)O(n)，临时数组tmp存储合并结果。