1. 排序数组
912. 排序数组 - 力扣(LeetCode)
今天我们使用归并排序来对数组进行排序,实际上,归并排序和快速排序是有一定相似之处的,都运用了分而治之的思想提升了排序效率。快速排序的实现思路是每次排序把区间划分为小于基准元素、等于基准元素、大于基准元素三个部分,直至数组整体有序为止;而归并排序的实现思路则是每次排序把区间平均划分为两个部分,分别对这两个部分再次排序,然后把这两个部分合并,重复这个过程直至子数组为一。
显然合并数组这个操作是需要一个数组进行辅助的,由于归并排序过程中两个相等的元素在数组中的位置不会发生改变,所以这是一个稳定的排序算法,虽然在不要求稳定的情况下,都是快速排序比归并排序更快,但归并排序也有自己的应用场景,这点我们在后面会提到。
class Solution {
public:
vector<int> temp;
vector<int> sortArray(vector<int>& nums)
{
temp.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;
mergesort(nums, left, mid);
mergesort(nums, mid + 1, right);
int cur1= left, cur2 = mid + 1, i = 0;
while(cur1 <= mid && cur2 <= right)
{
temp[i++] = (nums[cur1] <= nums[cur2]) ? nums[cur1++] : nums[cur2++];
}
while(cur1 <= mid) temp[i++] = nums[cur1++];
while(cur2 <= right) temp[i++] = nums[cur2++];
for(int j = left; j <= right; j++)
{
nums[j] = temp[j - left];
}
}
};
2. 交易逆序对的总数
LCR 170. 交易逆序对的总数 - 力扣(LeetCode)
依据题意,我们需要求出一个数组中的逆序对总数,逆序对的定义是前面的数大于后面的数时,这两个数可以组成逆序对。首先能想到的肯定是暴力枚举,两层for循环列举出所有符合条件的逆序对情况,但既然这是困难题,暴力枚举法肯定是通过不了的,所以我们要想办法对暴力法做出优化。
首先,如果我们把数组平均分为左右两个部分,那么要查找逆序对的步骤就是在左半部分找逆序对、在右半部分找逆序对、左右部分各取一个数,找逆序对。这样一来,就能找出所有满足条件的逆序对了,这时大家可能就会奇怪了,这不还是相当于枚举吗?确实是这样,但如果我们在找完左半部分逆序对后对左边进行排序、找完右半部分逆序对后对右边进行排序、在找完左右部分的逆序对后对数组整体进行排序,大家可能发现了,这样一来我们就能够用归并排序来对求逆序对的流程进行优化了。
为什么说排序能够优化查找逆序对的效率呢?我举个例子大家就明白了。
大家可以发现,当nums[cur1] > nums[cur2]时,我们就一次性找到了mid-cur1+1个符合条件的逆序对!和暴力枚举法比起来,大大提升了效率!
class Solution {
public:
vector<int> temp;
int reversePairs(vector<int>& record)
{
temp.resize(record.size());
return mergesort(record, 0, record.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, cur2 = mid + 1, i = 0;
while(cur1 <= mid && cur2 <= right)
{
if(nums[cur1] <= nums[cur2])
{
temp[i++] = nums[cur1++];
}
else
{
ret += mid - cur1 + 1;
temp[i++] = nums[cur2++];
}
}
while(cur1 <= mid) temp[i++] = nums[cur1++];
while(cur2 <= right) temp[i++] = nums[cur2++];
for(int j = left; j <= right; j++)
{
nums[j] = temp[j - left];
}
return ret;
}
};