归并排序算法

一.回顾

该算法思想以及复杂度等在牢蒯的多种排序算法这篇文章里，所以这里只是针对特定题型进行讲解，如果读者忘记了归并排序，可以先看看牢蒯这篇文章，然后再借助这道题复习一下：

https://leetcode.cn/problems/sort-an-arrayhttps://leetcode.cn/problems/sort-an-array这是答案，写完可以对照一下：

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int left = 0,right = nums.size() - 1;
        _Mergesort(nums,left,right);
        return nums;
    }
    void _Mergesort(vector<int>& nums,int left,int right)
    {
        if(left >= right)
        {
            return;
        }
        //后序遍历
        int mid = (right + left) / 2;
        _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)
        {
            if(nums[cur1] <= nums[cur2])
            {
                tmp[i++] = nums[cur1++];
            }
            else
            {
                tmp[i++] = 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];
        }
    }
};

二.逆序对

https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcofhttps://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof

1.大致框架

逆序对可以大篇幅的套用归并排序的思想：

2.详解核心部分

①.策略一.找左边序列里比cur2大的数的个数

思考：策略一是否可以使用降序？

答案是不可以，会重复！

②.策略二.找右边序列里比cur1小的数的个数

该策略无法使用升序，原因也是会重复。

3.答案

class Solution {
    int tmp[50010];//写在这儿可避免每递归一次，就创建一次数组所带来的巨大开销
public:
    int reversePairs(vector<int>& record) {
        int left = 0,right = record.size() - 1;
        return _mergesort(record,left,right);
    }
    int _mergesort(vector<int>& record,int left,int right)
    {
        if(left >= right)
        {
            return 0;
        }
        int ret = 0;
        int mid = (left + right) / 2;
        //左逆序对 + 排序 + 右逆序对 + 排序
        ret += _mergesort(record,left,mid);
        ret += _mergesort(record,mid + 1,right);
        //合并左右有序区间+一左一右(左区间里找比cur2大的)
        int cur1 = left,cur2 = mid + 1,i = 0;
        while(cur1 <= mid && cur2 <= right)
        {
            if(record[cur1] > record[cur2])//注意不要写成>=
            {
                tmp[i++] = record[cur2++];
                ret += mid - cur1 + 1;
            }
            else
            {
                tmp[i++] = record[cur1++];
            }
        }
        //合并剩余
        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;
    }
};

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/2401_87941709/article/details/170286919