【算法】归并排序概念及例题运用

1. 明确我们的目的，是通过使用归并排序算法对给定的整数向量进行排序
2. 对左右两边的数组进行排序
3. 创建临时变量数组，通过双指针，使左右数组合并有序

class Solution {int tmp[50010];
public:vector<int> sortArray(vector<int>& nums) {int n = nums.size();mergesort(nums, 0, n-1);return nums;}void mergesort(vector<int>& nums, int l, int r){// 1.获取中间点坐标if(l >= r) return;int mid = l + ((r - l) >> 1);// 2. 利用归并排序自身对左右范围的数组进行，是左右两边都有序mergesort(nums, l, mid);mergesort(nums, mid + 1, r);// 3.创建临时变量数组，同时利用双指针，将左右有序数组合并int index = l;int cur1 = l, cur2 = mid + 1;while(cur1 <= mid && cur2 <= r){if(nums[cur1] < nums[cur2]) tmp[index++] = nums[cur1++];else tmp[index++] = nums[cur2++];}// 4.使左右两边的数组充分排序进入临时数组while(cur1 <= mid) tmp[index++] = nums[cur1++];while(cur2 <= r) tmp[index++] = nums[cur2++];// 5.将临时数组中的元素返回，使原数组有序for(int i = l; i <= r; ++i) nums[i] = tmp[i];}
};

因为归并排序具有较好的稳定性，所以我们利用归并排序排升序的同时，计算每次右边数组大于左边数组元素的个数，并返回

class Solution {
int tmp[50010];
public:int reversePairs(vector<int>& record) {return mergesort(record, 0, record.size() - 1);}   int mergesort(vector<int>& record, int l, int r){// 1.获取中间点坐标if (l >= r) return 0;int mid = l + ((r - l) >> 1);int cur1 = l, cur2 = mid + 1, ret = 0;// 2. 利用归并排序自身对左右范围的数组进行，是左右两边都有序ret += mergesort(record, l, mid);ret += mergesort(record, mid+1, r);// 3.利用双指针合并数组// 4.利用升序数组的特性，计算当前两组元素中符合前一天的股价高于后一天的股价的组合个数int index = 0;while(cur1 <= mid && cur2 <= r){if(record[cur1] > record[cur2]) ret += mid - cur1 + 1, tmp[index++] = record[cur2++];else tmp[index++] = record[cur1++];}while(cur1 <= mid) tmp[index++] = record[cur1++];while(cur2 <= r) tmp[index++] = record[cur2++];// 5.将临时数组中的元素返回，使原数组有序for(int i=0; i<index; ++i) record[l+i] = tmp[i];return ret;}
};

整体做法和上题如出一辙，不过这里需要返回对应的元素个数组成的vector，所以我们需要提前建立可以用来标记元素下标和记录满足元素个数数量的返回数组

class Solution {// 返回值vector<int> ret;// 记录原始下标vector<int> index;// 临时变量数组int tmpnums[100010];// 临时下标数组int tmpindex[100010];public:vector<int> countSmaller(vector<int>& nums) {int n = nums.size();ret.resize(n);index.resize(n);// 获取原始下标for (int i = 0; i < n; ++i)index[i] = i;mergesort(ret, index, nums, 0, n - 1);return ret;}void mergesort(vector<int>& ret, vector<int>& index, vector<int>& nums, int left, int right) {if (left >= right)return;int mid = left + ((right - left) >> 1);mergesort(ret, index, nums, left, mid);mergesort(ret, index, nums, mid + 1, right);int cur1 = left, cur2 = mid + 1, i = 0;while (cur1 <= mid && cur2 <= right) {if (nums[cur2] >= nums[cur1]) {tmpindex[i] = index[cur2];tmpnums[i++] = nums[cur2++];} else {ret[index[cur1]] += right - cur2 + 1;tmpindex[i] = index[cur1];tmpnums[i++] = nums[cur1++];}}while (cur1 <= mid)tmpindex[i] = index[cur1], tmpnums[i++] = nums[cur1++];while (cur2 <= right)tmpindex[i] = index[cur2], tmpnums[i++] = nums[cur2++];for (int j = left; j <= right; ++j)index[j] = tmpindex[j - left], nums[j] = tmpnums[j - left];}
};

大体规则相同，当这里用降序更容易实现

class Solution {int tmp[50010];public:int reversePairs(vector<int>& nums) {int n = nums.size();return mergesort(nums, 0, n - 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 = left;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 j = left; j <= right; ++j)nums[j] = tmp[j];return ret;}
};