归并排序的核心思想与进阶应用

易错点提示

1. 递归终止条件：
   • 在 mergeSort 函数中，left >= right 时停止递归，以防止无穷递归导致的栈溢出。
2. 合并逻辑：
   • cur1 和 cur2 分别指向左、右子数组的起始位置，使用 tmp 存储合并结果。确保在所有元素都合并后，将 tmp 拷贝回 nums 中。
3. 临时数组的使用：
   • 临时数组 tmp 存储每一轮合并结果，以确保排序结果被完整保留到下一轮递归。

时间复杂度和空间复杂度

• 时间复杂度：O(n log n)。每轮合并的时间复杂度为 O(n)，分区深度为 log n。
• 空间复杂度：O(n)，临时数组 tmp 占用额外空间。

2.2 数组中的逆序对（hard）

题目链接：剑指 Offer 51. 数组中的逆序对

题目描述：

在一个数组中的两个数字，如果前面的一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1：

• 输入：[7,5,6,4]
• 输出：5

解法（利用归并排序的过程 — 分治）

算法思路：

归并排序求逆序数是经典的方法。在归并排序的合并过程中，我们可以顺便统计出逆序对的数量，这样可以避免暴力统计的 O(n^2) 时间复杂度。

逆序对的产生方式可分为三种情况：

1. 左数组中的元素逆序。
2. 右数组中的元素逆序。
3. 左数组和右数组中的元素形成逆序。

归并排序过程可以分为两个步骤：

1. 分：将数组一分为二，不断划分，直到每个子数组长度为 1。
2. 治：将左右子数组合并成一个有序数组的过程中，统计逆序对的数量。

核心步骤与实现细节

1. **为什么可以利用归并排序求逆序对？**因为在归并排序的过程中，我们通过分治的方法将数组拆分成左右两部分。每部分内部的逆序对可以分别在排序的过程中统计。最终在归并左右数组时，可以统计那些横跨左右数组的逆序对，这三者相加即为总的逆序对数。
2. **核心问题：如何在合并两个有序数组的过程中统计逆序对的数量？**在合并左右两个已排序的数组时，可以高效统计出横跨两个数组的逆序对数。考虑以下例子：假设有两个有序序列 left = [5, 7, 9] 和 right = [4, 5, 8]。 目标是计算在合并的过程中 left 中的元素大于 right 中的元素的情况数量。
3. 合并并统计逆序对的过程：定义指针 cur1 遍历 left 数组，cur2 遍历 right 数组。 定义 ret 记录逆序对的数量，help 数组临时存储排序的结果。
   • 第一轮：
     • 比较 left[cur1] 和 right[cur2]，如果 left[cur1] > right[cur2]，则意味着从 cur1 到末尾的元素都大于 right[cur2]（因为 left 是有序的）。我们可以确定逆序对数量并将结果累加到 ret。
     • 若 left[cur1] <= right[cur2]，则将 left[cur1] 添加到 help 数组中。
   • 处理剩余元素：若一侧数组元素遍历完，剩余元素直接添加到 help 数组即可，不会再产生新的逆序对。

C++ 代码实现

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;
        
        // 1. 找中间点，将数组分成两部分
        int mid = (left + right) >> 1;
        
        // 2. 左、右部分的逆序对数量
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid + 1, right);
        
        // 3. 合并并统计逆序对数量
        int cur1 = left, cur2 = mid + 1, 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++];
        
        // 5. 将 tmp 数组内容拷贝回原数组
        for (int j = left; j <= right; j++) {
            nums[j] = tmp[j - left];
        }
        return ret;
    }
};

易错点提示

1. 递归终止条件：
   • 当 left >= right 时，表示已将数组分割到单个元素，递归停止返回 0。
2. 统计逆序对：
   • 当 nums[cur1] > nums[cur2] 时，说明 left[cur1] 及后面的所有元素都大于 right[cur2]，则这些元素与 right[cur2] 构成逆序对。统计并更新 ret 的值。
3. 处理剩余元素：
   • 若左数组或右数组有剩余，则直接将剩余部分加入到 tmp，因为剩余部分不会形成逆序对。
4. 拷贝回原数组：
   • 最后将 tmp 的排序结果拷贝回 nums，确保在递归的上一级合并时数组依旧有序。

时间复杂度和空间复杂度

• 时间复杂度：O(n log n)。归并排序的分治递归实现使得时间复杂度达到 O(n log n)。
• 空间复杂度：O(n)，需要额外的数组存储合并结果。

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

题目链接：315. 计算右侧小于当前元素的个数

题目描述：

给你一个整数数组 nums，按要求返回一个新数组 counts。 数组 counts 有如下性质：counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例 1：

• 输入：nums = [5,2,6,1]
• 输出：[2,1,1,0]

解释：

• 5 的右侧有 2 个更小的元素（2 和 1）。
• 2 的右侧有 1 个更小的元素（1）。
• 6 的右侧有 1 个更小的元素（1）。
• 1 的右侧有 0 个更小的元素。

解法（利用归并排序的过程 — 分治）

算法思路：

本题和求数组中的逆序对非常类似，但与逆序对的统计不同之处在于：

• 需要返回一个数组 counts，记录每个元素右侧更小的元素数量，而不是单一的逆序对总数。
• 归并排序过程中，除了排序，还需要记录排序过程中元素的索引位置的变化。

核心步骤

1. 辅助数组和索引绑定：
   • 定义一个 index 数组，用于记录元素对应的原始索引，确保元素与下标绑定在一起。
   • ret 数组存储每个元素右侧更小元素的数量。
2. 递归排序：
   • 递归地对数组进行分治排序，并统计左右子数组中每个元素右侧更小的元素数量。
3. 合并排序并统计逆序对：
   • 当合并两个有序数组时，如果发现左侧的某个元素大于右侧的当前元素，则说明该左侧元素右侧的所有元素都小于它。将这些逆序对数量累加到对应的 ret 索引上。
   • 同时，完成左右子数组的归并操作。

C++ 代码实现

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, 0); // 初始化结果数组为 0
        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) / 2;
        
        // 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]) {
                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 j = left; j <= right; j++) {
            nums[j] = tmpNums[j - left];
            index[j] = tmpIndex[j - left];
        }
    }
};

易错点提示

1. 确保索引正确绑定：
   • 在每次合并的过程中，索引数组 index 也需要同步排序，以保证结果数组 ret 的统计准确。
2. 统计逆序对的逻辑：
   • 当 nums[cur1] > nums[cur2] 时，说明从 cur2 到 right 的所有元素都小于 nums[cur1]，需要将这些数量累加到 ret[index[cur1]]。
3. 递归终止条件：
   • 当 left >= right 时停止递归，避免无效操作。

时间复杂度和空间复杂度

• 时间复杂度：O(n log n)。分治递归的时间复杂度是 O(log n)，每次合并的时间复杂度是 O(n)。
• 空间复杂度：O(n)。需要额外的临时数组 tmpNums 和 tmpIndex 进行合并排序。

2.4 翻转对（hard）

题目链接：493. 翻转对

题目描述：

给定一个数组 nums，如果 i < j 且 nums[i] > 2 * nums[j]，我们就将 (i, j) 称作一个重要翻转对。 你需要返回给定数组中的重要翻转对的数量。

示例 1：

• 输入：nums = [1,3,2,3,1]
• 输出：2

解法（归并排序 — 分治）

算法思路：

翻转对的统计与逆序对非常类似，都可以利用 归并排序 的思想，将问题分解为三部分：

1. 左数组中的翻转对数量。
2. 右数组中的翻转对数量。
3. 左右数组合并时的翻转对数量。

由于翻转对要求的是 nums[i] > 2 * nums[j]，直接在合并排序时统计会比较困难，因此：

• 我们在归并排序前，提前统计 左右两部分数组中满足条件的翻转对数量。
• 在统计完成后，再进行归并排序。

核心步骤与实现细节

1. 统计翻转对数量：
   • 使用两个指针 cur1 和 cur2，分别遍历左、右子数组。
   • 对于每个左数组元素 nums[cur1]，找到右数组中第一个不满足 nums[cur1] > 2 * nums[cur2] 的位置 cur2。
   • 此时，cur2 - mid - 1 即为当前 cur1 的翻转对数量，累加到结果中。
2. 合并两个有序数组：
   • 合并时，按照归并排序的逻辑，将两个子数组排序，并写入临时数组。
3. 递归分治：
   • 每次划分数组为 [left, mid] 和 [mid + 1, right]，递归统计翻转对数量并排序。

C++ 代码实现

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;
        
        // 1. 分区
        int mid = (left + right) / 2;
        
        // 2. 递归计算左右区间的翻转对数量
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid + 1, right);
        
        // 3. 统计翻转对数量
        int cur1 = left, cur2 = mid + 1;
        while (cur1 <= mid) {
            while (cur2 <= right && nums[cur2] * 2 < nums[cur1]) {
                cur2++;
            }
            ret += cur2 - mid - 1;
            cur1++;
        }
        
        // 4. 合并两个有序数组
        cur1 = left, cur2 = mid + 1;
        int i = left;
        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];
        }
        return ret;
    }
};

易错点提示

1. 统计翻转对的逻辑：
   • 必须确保 cur2 指针只向右移动，不会回退，避免重复计算。
   • 注意翻转对的判断条件 nums[cur1] > 2 * nums[cur2]，需要考虑到浮点运算可能导致的精度问题，因此 2 * nums[cur2] 可能需要写成 nums[cur1] > 2LL * nums[cur2]。
2. 归并排序的逻辑：
   • 合并时，确保临时数组和原数组的元素同步，避免在递归的上一层出错。
3. 边界条件：
   • 单元素或空数组的递归终止条件是 left >= right。

时间复杂度和空间复杂度

• 时间复杂度：O(n log n)。
  • 每次递归的深度是 log n，每层递归需要合并排序和统计翻转对，复杂度为 O(n)。
• 空间复杂度：O(n)。
  • 使用了额外的临时数组 tmp 进行排序。

优化点

1. 使用更大的临时数组（避免频繁分配内存）。
2. 在统计翻转对时，提前检查是否有可能的翻转对，减少无意义的遍历。

通过以上方法，翻转对的数量可以在 O(n log n) 的时间复杂度内高效统计。

写在最后

在本次归并排序专题中，我们以经典的分治思想为核心，逐层剖析了归并排序的精髓及其在算法中的高级应用。从数组排序到统计逆序对，再到复杂的翻转对和右侧更小元素计数，归并排序不仅是解决基础问题的利器，更是攻克高阶难题的关键。我们以逐步深入的方式，从基础实现到优化分析，贯穿了分治思想的深度与广度。

分治法的核心在于'分而治之'，通过不断将大问题拆解为小问题，并利用递归与合并的方式重新组合结果。在归并排序中，借助临时数组和指针操作，我们能够高效完成排序，并在此过程中完成复杂的统计任务。它不仅展现了算法的美学，更体现了计算机科学中化繁为简的哲学。