分治-归并排序

1. 基本思想

"分治-归并排序"是一种经典的排序算法，利用分治法的思想将一个大的问题拆解成多个小问题，再合并求解的过程。具体过程如下：

分解：将待排序的数组不断分成两半，递归地对每个子数组进行归并排序，直到每个子数组只包含一个元素（即已经有序）。

合并：将两个有序的子数组合并成一个有序的大数组。合并过程是归并排序的核心，它确保在合并时保持数组的有序性。

递归：继续递归处理子数组，直到所有子数组都已排序并合并成一个完整的有序数组。

归并排序的时间复杂度为O(n log n)，由于需要额外的空间来存储临时数组，因此空间复杂度为O(n)。它是一种稳定的排序算法，适用于大规模数据的排序。

2. 排序数组（中等）

tmp：用于在合并阶段存储排序后的中间结果。

递归基：

 - if (l >= r)：当左边界 l 大于或等于右边界 r 时，说明区间长度为 1 或 0，此时区间本身有序，不需要进一步处理。

划分区间：

 - int mid = (l + r) >> 1：通过计算中间点 mid，将当前区间 [l, r] 分为两部分：

    - 左区间 [l, mid]

    - 右区间 [mid + 1, r]

合并两个有序区间：

 - int left = l, right = mid + 1, i = 0：初始化三个指针：

 - left 指向左区间的起始位置。

 - right 指向右区间的起始位置。

 - i 指向临时数组 tmp 的起始位置。

比较左右区间的元素：

    - 如果左区间的当前元素小于等于右区间的当前元素，将左区间的元素加入 tmp，并移动左指针。

    - 否则，将右区间的元素加入 tmp，并移动右指针。 

处理剩余元素：

    - 左区间或右区间可能有元素未处理完毕，需要将剩余的元素依次加入 tmp。

还原排序结果：

 - for(int i = l; i <= r; i++) nums[i] = tmp[i - l];

    - 将临时数组 tmp 中的排序结果还原到原数组的对应区间 [l, r]。

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 l, int r) { if(l >= r) return; //1.选取中间点划分区间 int mid = (l + r) >> 1; //2.把左右区间排序 mergeSort(nums, l, mid); mergeSort(nums, mid + 1, r); //3. 合并两个有序数组 int left = l, right = mid + 1, i = 0; while(left <= mid && right <= r) { if(nums[left] <= nums[right]) tmp[i++] = nums[left++]; else tmp[i++] = nums[right++]; } while(left <= mid) tmp[i++] = nums[left++]; while(right <= r) tmp[i++] = nums[right++]; //4. 还原 for(int i = l; i <= r; i++) nums[i] = tmp[i - l]; } };

912. 排序数组 - 力扣（LeetCode）

3. 交易逆序对的总数（困难）

基本思想和与上面相同，不同点在于需要在排序时记录逆序对的个数。该题使用归并排序，排序时使用降序和升序都可以解决问题，下面以升序为例。

 

由于我们使用归并排序，因此进入下面第三步时[left, mid], [mid + 1, right]左右两区间各自已经有序。当我们nums[cur1]和nums[cur2]来排序时，如果nums[cur1] > nums[cur2] ，说明[cur1, mid]之间的数（升序）都大于nums[cur2]，都构成逆序对。

class Solution { int tmp[50010]; public: int reversePairs(vector<int>& record) { return mergeSort(record, 0, record.size() - 1); } int mergeSort(vector<int>& record, int left, int right) { if(left >= right) return 0; //1. 找中间点将数组分成两部分 int mid = (left + right) >> 1; //2. 左区间逆序对 + 排序 + 右区间逆序对 + 排序 int ret = 0; ret += mergeSort(record, left, mid); ret += mergeSort(record, mid + 1, right); //3. 统计左右区间逆序个数 + 合并两个有序数组 int cur1 = left, cur2 = mid + 1, i = 0; while(cur1 <= mid && cur2 <= right) { if(record[cur1] <= record[cur2]) { tmp[i++] = record[cur1++]; } else { ret += mid - cur1 + 1; tmp[i++] = record[cur2++]; } } //4. 处理未完成排序 + 将已排序部分加入目标数组 while(cur1 <= mid) tmp[i++] = record[cur1++]; while(cur2 <= right) tmp[i++] = record[cur2++]; for(int j = left; j <= right; j++) record[j] = tmp[j - left]; return ret; } };

LCR 170. 交易逆序对的总数 - 力扣（LeetCode）

4, 计算右侧小于当前元素的个数（困难）

这一题与上面的不同点在于排序时要记录nums数组中元素原来的下标，用于在累加每次归并时符合题意的个数。

class Solution { vector<int> ret; int tmpr[100000]; vector<int> index; int tmpi[100000]; 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(nums, 0, n - 1); return ret; } void mergeSort(vector<int>& nums, int left, int right) { if(left >= right) return; //1. 找中间值，将数组划分成两部分 int mid = (left + right) >> 1; //2. 先处理左右两部分 mergeSort(nums, left, mid); mergeSort(nums, mid + 1, right); //3. 处理一左一右 + 降序 + 计算返回值 int cur1 = left, cur2 = mid + 1, i = 0; while(cur1 <= mid && cur2 <= right) { if(nums[cur1] <= nums[cur2]) { tmpi[i] = index[cur2]; tmpr[i++] = nums[cur2++]; } else { ret[index[cur1]] += right - cur2 + 1; tmpi[i] = index[cur1]; tmpr[i++] = nums[cur1++]; } } //4. 处理排序+还原 while(cur1 <= mid) { tmpi[i] = index[cur1]; tmpr[i++] = nums[cur1++]; } while(cur2 <= right) { tmpi[i] = index[cur2]; tmpr[i++] = nums[cur2++]; } for(int j = left; j <= right; ++j) { nums[j] = tmpr[j - left]; index[j] = tmpi[j - left]; } } };

315. 计算右侧小于当前元素的个数 - 力扣（LeetCode）

5. 翻转对

这题的不同点在于，排序和记录翻转对的条件不同。

例如在逆序对那题 排序和判断是否逆序对 的条件都是nums[cur1] <= nums[cur2]

而在本题中，排序的条件是nums[cur1] <= nums[cur2]，而判断是否是翻转对条件是nums[cur2] >= nums[cur1] / 2.0，需要分开处理。

class Solution { int tmp[50000]; 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 count = 0; //1. 找中间值将数组分成两个部分 int mid = (left + right) >> 1; //2. 处理左右区间 count += mergeSort(nums, left, mid); count += mergeSort(nums, mid + 1, right); //3. 处理一左一右 int cur1 = left, cur2 = mid + 1, i = 0; while(cur1 <= mid) { while(cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) cur2++; if(cur2 > right) break; count += right - cur2 + 1; cur1++; } //4. 降序 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++]; //5. 还原数组 for(int j = left; j <= right; ++j) nums[j] = tmp[j - left]; return count; } };

 493. 翻转对 - 力扣（LeetCode）