1. 归并排序
题目链接：912. 排序数组 - 力扣（LeetCode）
题目展示：
题目分析：这里我们直接来实现归并排序即可；
代码实现：
class Solution
{
vector<int> tmp;//在全局创建辅助数组，提高效率
public:
vector<int> sortArray(vector<int>& nums)
{
tmp.resize(nums.size());
mergesort(nums,0,nums.size()-1);
return nums;
}
void mergesort(vector<int>& nums,int left,int right)
{
if(left>=right)
{
return;
}
//选中间点划分数组
int mid=(left+right)>>1;
//[left,mid][mid+1,right]
//把左右区间进行排序
mergesort(nums,left,mid);
mergesort(nums,mid+1,right);
//合并两个有序数组
int cur1=left;
int cur2=mid+1;
int 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++];
}
//还原
for(int i=left;i<=right;i++)
{
nums[i]=tmp[i-left];
}
}
};2. 交易逆序对的总数
题目链接：LCR 170. 交易逆序对的总数 - 力扣（LeetCode）
题目展示：
题目分析：本题要求我们找出逆序对的数目，暴力解法肯定会超时的，所以我们需要利用归并排序的思想来解决。
大家可以看上图，其实就是归并排序的一个总过程，我们先去左区间找找，再去右区间找找，最后一左一右去找逆序对；上面有两种策略，其实本质是一样的。
代码实现：
class Solution
{
int tmp[50010];
public:
int reversePairs(vector<int>& record)
{
return mergesort(record,0,record.size()-1);
}
int mergesort(vector<int>& nums,int left,int right)
{
if(left>=right)
{
return 0;
}
int ret=0;
//1.找中间点
int mid=(left+right)>>1;
//2.左边的个数+排序+右边的个数+排序
ret+=mergesort(nums,left,mid);
ret+=mergesort(nums,mid+1,right);
//3.一左一右的个数
int cur1=left;
int cur2=mid+1;
int i=0;
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++];
}
for(int j=left;j<=right;j++)
{
nums[j]=tmp[j-left];
}
return ret;
}
};3. 计算右侧小于当前元素的个数
题目链接：315. 计算右侧小于当前元素的个数 - 力扣（LeetCode）
题目展示：
题目分析：本题与上一题类似，需要用到上面提到的“策略二”来解决，具体大家来看下图。
本题的关键在于我们需要记录原始下标，最终返回的是数组，在操作nums数组的时候，同时操作index数组，让他们“绑定”起来，这样我们就可以找到正确的位置。
代码实现：
class Solution
{
vector<int> ret;
vector<int> index;//记录nums中当前元素的原始下标
int tmpNums[500010];
int tmpIndex[500010];
public:
vector<int> countSmaller(vector<int>& nums)
{
int n=nums.size();
ret.resize(n);
index.resize(n);
//初始化Index数组
for(int i=0;i<n;i++)
{
index[i]=i;
}
mergesort(nums,0,n-1);
return ret;
}
void mergesort(vector<int>& nums,int left,int right)
{
if(left>=right)
{
return;
}
int mid=(left+right)>>1;
mergesort(nums,left,mid);
mergesort(nums,mid+1,right);
int cur1=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(int i=left;i<=right;i++)
{
nums[i]=tmpNums[i-left];
index[i]=tmpIndex[i-left];
}
}
};4. 翻转对
题目链接：493. 翻转对 - 力扣（LeetCode）
题目展示：
题目分析：本题其实和第二题类似，但是有一些变化；
大家可以看到，我们要在合并两个有序数组前，要先计算翻转对的数量，大家一定要结合上面的图来理解。
代码实现：
class Solution
{
int tmp[50010];
public:
int reversePairs(vector<int>& nums)
{
return mergesort(nums,0,nums.size()-1);
}
int mergesort(vector<int>& nums,int left,int right)
{
if(left>=right)
{
return 0;
}
int ret=0;
int mid=(left+right)>>1;
//计算左右两侧翻转对
ret+=mergesort(nums,left,mid);
ret+=mergesort(nums,mid+1,right);
//先计算翻转对的数量
int cur1=left;
int cur2=mid+1;
int i=0;
while(cur1<=mid)
{
while(cur2<=right&&nums[cur2]>=(nums[cur1]/2.0))
{
cur2++;
}
if(cur2>right)
{
break;
}
ret+=right-cur2+1;
cur1++;
}
//合并两个有序数组
cur1=left;
cur2=mid+1;
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(int i=left;i<=right;i++)
{
nums[i]=tmp[i-left];
}
return ret;
}
};5. 总结
本篇博客为大家介绍了分治专题的另一部分内容——归并，大家不仅需要掌握归并排序的写法，还要会利用归并排序的思想去解决一些问题，最后，希望本文可以为大家带来帮助，感谢阅读！
