算法实战：归并排序与数组逆序对详解

47. 归并排序

题目链接：

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

题目描述：

题目示例：

解法 (归并排序)：

算法思路：

归并排序的核心思想是「分而治之」（Divide and Conquer），整个过程可以概括为两个阶段：

分：将数组一分为二，一直分解到数组长度为 1，使整个数组的排序过程被分为「左半部分排序」+「右半部分排序」; 治：将两个较短的有序数组合并成一个长的有序数组，一直合并到最初的长度。

C++ 算法代码：

class Solution {
public:
    vector<int> tmp; // 用于存放两个有序数组合并后的结果

    void mergesort(vector<int>& nums, int left, int right) {
        if (left == right) return;

        // 1、选择中间点划分区间
        int mid = (right - left) / 2 + left;
        // 将数组分成两块：[left, mid] [mid + 1, right]

        // 2、把左右区间排序
        mergesort(nums, left, mid);
        mergesort(nums, mid + 1, right);

        // 3、将两个数组合并成一个有序数组
        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++];

        // 将两个数组有序合并到 tmp 中后，再还原给原数组 nums 对应部分位置
        for (int i = left; i <= right; i++) {
            nums[i] = tmp[i - left];
        }
    }

    vector<int> sortArray(vector<int>& nums) {
        tmp.resize(nums.size());
        mergesort(nums, 0, nums.size() - 1);
        return nums;
    }
};

算法总结及流程解析：

---

48. 数组中的逆序对

题目链接：

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

题目描述：

题目示例：

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

算法思路：

用归并排序求逆序数是很经典的方法，主要就是在归并排序的合并过程中统计出逆序对的数量。在合并两个有序序列的过程中，我们可以利用数组的有序性，快速求出逆序对的数量，而不是将所有情况都枚举出来。

我们将这个问题分解成几个小问题，逐一破解：

为什么可以利用归并排序？

如果我们将数组从中间划分成两个部分，那么逆序对产生的方式可以划分为三组：

1. 逆序对中两个元素全部从左数组中选择；
2. 逆序对中两个元素全部从右数组中选择；
3. 逆序对中两个元素一个选左数组，另一个选右数组。

根据排列组合的分类相加原理，这三种情况下产生的逆序对的总和，正好等于总的逆序对数量。而这个思路正好匹配归并排序的过程：先排序左数组，再排序右数组，最后左数组和右数组合二为一。

因此，我们可以利用归并排序的过程，先求出左半数组中逆序对的数量，再求出右半数组中逆序对的数量，最后求出一个选择左边、另一个选择右边情况下逆序对的数量，三者相加即可。

核心逻辑：如何在合并两个有序数组的过程中，统计出逆序对的数量？

合并两个有序序列时求逆序对的方法主要有两种：

1. 快速统计出某个数前面有多少个数比它大；
2. 快速统计出某个数后面有多少个数比它小。

这里我们采用第一种思路：当 nums[cur1] > nums[cur2] 时，说明 [cur1, mid] 区间所有值都大于 nums[cur2]，此时可以直接计算当前 nums[cur2] 贡献的逆序对个数。

C++ 算法代码：

class Solution {
public:
    int count = 0;
    vector<int> tmp; // 用于存放两个有序数组合并后的结果

    int reversePairs(vector<int>& record) {
        tmp.resize(record.size());
        mergesort(record, 0, record.size() - 1);
        return count;
    }

    void mergesort(vector<int>& nums, int left, int right) {
        if (left >= right) return;

        // 1、选择中间点划分区间
        int mid = (right - left) / 2 + left;

        // 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]) {
                tmp[i++] = nums[cur1++];
            } else {
                // 当第一次遇见 nums[cur1] > nums[cur2], 说明 [cur1, mid] 区间所有值都大于 nums[cur2]
                // 计算当前 nums[cur2] 的逆序对个数
                count += mid - cur1 + 1;
                tmp[i++] = nums[cur2++];
            }
        }

        // 处理还没有排序的剩余部分
        while (cur1 <= mid) tmp[i++] = nums[cur1++];
        while (cur2 <= right) tmp[i++] = nums[cur2++];

        // 将两个数组有序合并到 tmp 中后，再还原给原数组 nums 对应部分位置
        for (int i = left; i <= right; i++) {
            nums[i] = tmp[i - left];
        }
    }
};

算法总结及流程解析：

小结：到此，归并排序与数组逆序对这两道算法题就讲解完了。归并排序采用分治思想，先将数组不断二分至单个元素，再通过有序合并操作完成排序，时间复杂度为 O(nlogn)。希望大家能有所收获！