归并排序练习

归并排序使用先处理左边，再处理右边的思想。

排序数组

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

思路

先算出数组中的中间值，再对左边递归，再对右边递归即可对左右两区间各自进行排序。

mergeSort(nums, left, mid);

mergeSort(nums, mid + 1, right);

合并两数组 

定义cur1起始点为左边数组的第一位，定义cur2起始点为右边数组的第一位，如图：

再将两数较小的填入临时数组。

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++];

最后再输出数组即可

代码

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 left, int right)
    {
        if (left >= right) return;

        int mid = (left + right) >> 1;
        //对左右区间排序
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        //合并两数组      
        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 i = left; i <= right; i++)
            nums[i] = tmp[i - left];
    }
};

交易逆序对的总数

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

思路

本题依然使用归并思想，与上题的区别是合并数组步骤：若cur1所指向的值小于等于cur2指向值，则正常将数组按顺序合并，若cur1所指向的值大于cur2指向值,则cur1到mid中间的值都大于cur1，所以这些值都可以与cur2前的值形成逆序对，如此可以推断出逆序对数为mid - cur1 + 1,如图所示

再对未排完的剩余值进行排序即可。

代码 

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;

        int ret = 0, mid = (left + right) >> 1;
        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[cur1++];
            else
            {
                ret += mid - cur1 + 1;
                tmp[i++] = record[cur2++];
            }
        }

        //排序
        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;
    }
};

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

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

思路 

本题需要记录临时下标与原始下标，因为我们需要计算比某一值小的所有值，在合并数组期间会导致下标发生混乱。tmpIndex存储数组的临时下标。tmpNum用于临时存储元素值。后面每对数组进行处理都要注意临时下标和原始下标的操作。

代码

class Solution
{
    int tmpNums[100010];
    vector<int> index;//记录原始下标
    vector<int> ret;
    int tmpIndex[100010];
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;
        int mid = (left + right) >> 1;

        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        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];
        }
    }
};

翻转对

493. 翻转对 - 力扣（LeetCode）

思路

这题与逆序对的区别只有在递归后添加判断条件

while (cur1 <= mid)
{
    while (cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) cur2++;
    if (cur2 > right) break;
    ret += right - cur2 + 1;
    cur1++;
}        

只有cur1指向值大于cur2指向值两倍时才让cur2向后移。

代码 

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, mid = (left + right) >> 1;

        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid + 1, right);

        int cur1 = left, cur2 = mid + 1, i = left;
        while (cur1 <= mid)
        {
            while (cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) cur2++;
            if (cur2 > right) break;
            ret += right - cur2 + 1;
            cur1++;
        }

        //合并
        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++];

        for (int j = left; j <= right; j++)
            nums[j] = tmp[j];
        return ret;
    }
};