【每日算法】专题八_分治_归并排序

1. 算法思想

归并排序（Merge Sort）是一种采用分治思想的经典排序算法，由约翰・冯・诺伊曼在 1945 年提出。其核心思想是将一个大问题分解为多个小问题，分别解决后再将结果合并。

核心思想

1. 分治策略：

   • 分解：将待排序的数组从中间分成两部分，递归地对左右两部分分别进行排序。
   • 解决：当子数组长度为 1 或 0 时（已自然有序），递归终止。
   • 合并：将两个已排序的子数组合并为一个有序数组。

2. 合并操作：

   • 比较两个子数组的元素，按顺序放入临时数组。
   • 重复此过程直到所有元素合并完成。

算法步骤

1. 分解（Divide）：

   • 找到数组的中间点 mid，将数组分为左右两部分：left（索引从 0 到 mid）和 right（索引从 mid+1 到 n-1）。
   • 递归地对 left 和 right 继续分解，直到子数组长度为 1。

2. 解决（Conquer）：

   • 当子数组长度为 1 时，直接返回（已有序）。

3. 合并（Merge）：

   • 创建一个临时数组 temp。
   • 比较 cur1 和 cur2 的元素，将较小的元素依次放入 temp。
   • 将剩余元素（如果有）复制到 temp 的末尾。
   • 将 temp 的内容复制回原数组的对应位置。

示例代码（参考例题1）

算法复杂度

• 时间复杂度：始终为 O(n log n)，无论输入数据的分布如何。
• 空间复杂度：O(n)，主要用于临时数组。
• 稳定性：稳定排序（相等元素的相对顺序不变）。

2. 例题

2.1 排序数组

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

vector<int> tmp(50000);   // 在类外定义避免多次扩容vector<int> sortArray(vector<int>& nums) {mergeSort(nums, 0, nums.size() - 1);return nums;}// 归并排序void mergeSort(vector<int>& nums, int left, int right){if(left >= right) return;int mid = (right + left) >> 1;mergeSort(nums, left, mid);mergeSort(nums, mid + 1, right);// 合并vector<int> tmp(right - left + 1);int cur1 = 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++];for(int j = left; j <= right; ++j)nums[j] = tmp[j - left]; }

2.2 交易逆序对的总数

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

核心思路

1. 分治框架：

   • 利用归并排序将数组递归分解为左右两部分。
   • 在合并有序子数组的过程中统计逆序对。

2. 逆序对统计：

   • 当左子数组的元素 record[cur1] 大于右子数组的元素 record[cur2] 时，说明 record[cur1] 及其后续所有元素（共 right - cur2 + 1 个）都与 record[cur2] 构成逆序对。
   • 例如：左子数组 [3, 5]，右子数组 [1, 2]。当 cur1=0（值为 3），cur2=0（值为 1）时，3 > 1，因此 3 和 1 构成逆序对，且左子数组中 3 后面的所有元素（即 5）也与 1 构成逆序对，共 right - cur2 + 1 = 2 - 0 + 1 = 2 个逆序对。

3. 合并优化：

   • 合并时采用降序排列（从大到小），使得统计逆序对后可以直接按降序合并，避免额外操作。

关键点解析

• 递归分解：将数组不断二分，直到每个子数组长度为 1。
• 合并统计：在合并两个有序子数组时，若发现左子数组的元素大于右子数组的元素，则统计逆序对数量，并继续合并。
• 时间复杂度：与归并排序相同，为 O(n log n)，比暴力枚举的 O (n²) 更高效。

    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;int mid = (right + left) >> 1;int ret = 0;ret += mergeSort(record, left, mid);ret += mergeSort(record, mid + 1, right);int cur1 = left, cur2 = mid + 1, i = 0;while(cur1 <= mid && cur2 <= right){if(record[cur1] <= record[cur2])// 降序版本tmp[i++] = record[cur2++];else{ret += right - cur2 + 1;//选取右边段所有小于cur2的数tmp[i++] = record[cur1++];}}while(cur1 <= mid) tmp[i++] = record[cur1++];while(cur2 <= right) tmp[i++] = record[cur2++];for(int i = left; i <= right; ++i)record[i] = tmp[i - left];return ret;}

2.3 计算右侧小于当前元素的个数

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

核心思路

1. 分治框架：

   • 利用归并排序将数组递归分解为左右两部分。
   • 在合并有序子数组的过程中统计每个元素的逆序对信息。

2. 索引数组维护：

   • 使用 index 数组记录每个元素在原始数组中的下标，确保在合并过程中能正确映射统计结果到原数组位置。

3. 逆序对统计：

   • 当左子数组的元素 nums[cur1] 大于右子数组的元素 nums[cur2] 时，说明右子数组中从 cur2 到末尾的所有元素都比 nums[cur1] 小。
   • 因此，nums[cur1] 对应的原始下标 index[cur1] 的统计值需增加 right - cur2 + 1。

4. 合并优化：

   • 合并时采用降序排列（从大到小），使得统计逆序对后可以直接按降序合并，同时维护 index 数组的正确性。

关键点解析

• 递归分解：将数组不断二分，直到每个子数组长度为 1。
• 合并统计：在合并两个有序子数组时，若发现左子数组的元素大于右子数组的元素，则统计逆序对数量，并继续合并。
• 双辅助数组：
  • tmp 存储合并后的元素值。
  • tmp2 存储合并后的元素原始下标，确保统计结果能正确映射回原数组。
• 时间复杂度：与归并排序相同，为 O(n log n)，比暴力枚举的 O (n²) 更高效。

 

    vector<int> countSmaller(vector<int>& nums) {vector<int> counts(nums.size());vector<int> index(nums.size());// 记录原始下标for(int i = 0; i < index.size(); ++i)index[i] = i;mergeSort(nums, index, counts, 0, nums.size() - 1);return counts;}void mergeSort(vector<int>& nums, vector<int>& index, vector<int>& counts, int left, int right){if(left >= right) return;int mid = (right + left) >> 1;int cur1 = left, cur2 = mid + 1, i = 0;mergeSort(nums, index, counts, left, mid);mergeSort(nums, index, counts, mid + 1, right);while(cur1 <= mid && cur2 <= right){if(nums[cur1] <= nums[cur2]){tmp2[i] = index[cur2];tmp[i++] = nums[cur2++];}else{counts[index[cur1]] += right - cur2 + 1;tmp2[i] = index[cur1];tmp[i++] = nums[cur1++];}}while(cur1 <= mid) tmp2[i] = index[cur1], tmp[i++] = nums[cur1++];while(cur2 <= right) tmp2[i] = index[cur2], tmp[i++] = nums[cur2++];for(int i = left; i <= right; ++i){nums[i] = tmp[i - left];index[i] = tmp2[i - left];}}

2.4 翻转对

493. 翻转对 - 力扣（LeetCode）

核心思路

1. 分治框架：

   • 利用归并排序将数组递归分解为左右两部分。
   • 在合并有序子数组的过程中统计重要逆序对。

2. 逆序对统计：

   • 双指针扫描：在合并前，使用两个指针 cur1 和 cur2 分别遍历左子数组和右子数组。对于每个 cur1，找到右子数组中第一个满足 nums[cur1] > 2*nums[cur2] 的位置，此时右子数组中从 cur2 到末尾的所有元素都与 nums[cur1] 构成重要逆序对。
   • 高效统计：由于左右子数组已排序，当 cur1 右移时，cur2 只需继续右移（无需回退），确保统计时间复杂度为 O (n)。

3. 合并操作：

   • 统计逆序对后，将左右子数组合并为一个有序数组（此处采用升序排列，与统计逆序对的代码分离）。

关键点解析

• 递归分解：将数组不断二分，直到每个子数组长度为 1。
• 统计与合并分离：
  1. 先统计：通过双指针扫描左右子数组，统计重要逆序对。
  2. 再合并：将左右子数组合并为一个有序数组，为上层递归提供条件。
• 类型转换：(long long)nums[cur2] * 2 避免整数溢出，确保计算正确性。
• 时间复杂度：O (n log n)，其中每次合并操作的统计和合并步骤均为 O (n)。

    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 mid = (right + left) >> 1;int ret = 0;ret += mergeSort(nums, left, mid);ret += mergeSort(nums, mid + 1, right);int cur1 = left, cur2 = mid + 1, i = 0;while(cur1 <= mid){while(cur2 <= right && nums[cur1] <= (long long)nums[cur2] * 2)++cur2;ret += right - cur2 + 1;++cur1;}cur1 = left, cur2 = mid + 1;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(i = left; i <= right; ++i)nums[i] = tmp[i - left];return ret;}