【优选算法】分治--归并排序

归并排序简介

归并排序是一种经典的分治算法，其核心思想是将数组分成两个子数组，分别对它们进行排序，然后将排好序的子数组合并成一个最终的有序数组。归并排序以其稳定的时间复杂度（O (n log n)）和稳定性（相等元素的相对顺序不变）而闻名，常用于外部排序和链表排序。

核心思想：

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

一、排序数组

题目描述：

思路讲解：
排序的方式有很多种，这里我选择使用归并排序进行排序。以下是具体思路：

1. 分解数组：
   • 计算中间索引 mid = (left + right) / 2，将数组分为 [left, mid] 和 [mid+1, right] 两部分
2. 递归排序子数组：
   • 对左子数组 [left, mid] 和右子数组 [mid+1, right] 分别递归调用归并排序
3. 合并有序子数组：
   • 创建临时数组 tmp，将两个有序子数组合并到 tmp中
   • 将 tmp 中的元素复制回原数组的对应位置

编写代码：

class Solution {
    vector<int> tmp;
public:
    void _sortArray(vector<int>& nums , int left , int right) 
    {
        if(left >= right)   return;
        int mid = left + (right - left)/2;
        _sortArray(nums,left,mid);
        _sortArray(nums,mid+1,right);

        int i = left , j = mid + 1 , pos = 0;
        while(i <= mid && j <= right)
        {
            int num1 = nums[i] , num2 = nums[j];
            if(num1 < num2)
            {
                tmp[pos++] = num1;
                i++;
            }
            else
            {
                j++;
                tmp[pos++] = num2;
            }
        }

        while(i <= mid)
        {
            tmp[pos++] = nums[i++];
        }

        while(j <= right)
        {
            tmp[pos++] = nums[j++];
        }

        for(int i = left ; i <= right ; i++)
        {
            nums[i] = tmp[i-left];
        }
    }
    
    vector<int> sortArray(vector<int>& nums) {
        tmp.resize(nums.size());
        _sortArray(nums,0,nums.size()-1);
        return nums;
    }
};

二、交易逆序对的总数

题目描述：

思路讲解：
本道题需要我们找到逆序对的总数，最简单的思路就是暴力枚举出所有的二元组，判断是否为逆序对，需要两层循环完成，但是这个思路写出的代码会超时。

这里我们就需要换一种思路了，假设我们将数组分为左子数组和右子数组，那么整个数组的逆序对 = 左子数组内部的逆序对 + 右子数组内部的逆序对 + 一左一右的逆序对（左/右各取一个数）。

当一个数组得到了逆序对，再对数组进行排序，则并不会对该数组获取逆序对有影响，当左子数组和右子数组排序后，由于分别是从两个数组中取一个数，所以也不会影响获取一左一右的逆序对。

那么我们就获取左子数组内部的逆序对，再对左子数组进行排序，接着获取右子内部数组的逆序对，再对右子数组进行排序，然后获取一左一右的逆序对，到这里就看到了归并排序的影子了，在获取一左一右的逆序对后，我们再将左子数组和右子数组组成的数组进行排序。

这里就使用归并的方法来解决本道题，大家这里可能会疑惑，这个方法跟暴力枚举有什么区别，使用归并排序还有空间的开销。这里就来讲解排序的作用，由于获取左子数组内部的逆序对和获取右子数组内部的逆序对是通过递归完成的，所以我们主要解决的是获取一左一右的逆序对。观察下面两个策略，当数组进行排序后，通过对两个数组中的两个数进行对比，就可以一下子找出一批逆序对，可以大大增加搜索逆序对的效率。以下是在左右子数组有序情况下，快速统计逆序对的两种策略：

• 策略一：找出该数之前，有多少个数比我大（升序）

  • nums[cur1] > nums[cur2]; --> ret += (mid - cur1 + 1)，cur2++
  • nums[cur1] <= nums[cur2]; --> cur1++
    

• 策略二：找到该数之后，有多少个数比我小（降序）

  • nums[cur1] > nums[cur2]; --> ret += (right - cur2 + 1)，cur1++
  • nums[cur1] <= nums[cur2]; --> cur2++
    

以下是具体思路：

1. 将数组从中间分为左、右两个子数组，递归处理每个子数组，直到子数组长度为 1（无法再分）
2. 这里我选择在升序的情况下，使用策略一，找出该数之前，有多少个数比我大
3. 对两个已排序的左右子数组进行合并，同时统计逆序对：
   • 若 nums[cur1] > nums[cur2]，则 左子数组 中 cur1 及之后的所有元素都与 nums[cur2] 构成逆序对，逆序对数量增加 (mid - cur1 + 1)
   • 否则，不构成逆序对，继续比较下一个元素
   • 将合并后的有序数组返回，供上层递归使用
4. 累计逆序对总数，递归过程中，每层的逆序对数量 = 左子数组内部的逆序对 + 右子数组内部的逆序对 + 合并时跨左右的逆序对
5. 返回逆序对总数

编写代码：

class Solution {
    vector<int> tmp;
public:
    int _reversePairs(vector<int>& record , int left , int right)
    {
        if(left >= right)   return 0;

        int mid = (left + right) / 2;

        int ret = _reversePairs(record,left,mid);
        ret += _reversePairs(record,mid+1,right);
        
        int cur1 = left , cur2 = mid + 1 , pos = 0;
        while(cur1 <= mid && cur2 <= right)
        {
            int num1 = record[cur1] , num2 = record[cur2];

            // 策略一:找出该数之前，有多少个数比我大（升序）
            // if(num1 > num2)
            // {
            //     tmp[pos++] = num2;
            //     ret += (mid - cur1 + 1);
            //     cur2++;
            // }
            // else
            // {
            //     tmp[pos++] = num1;
            //     cur1++;
            // }

            // 策略二:找到该数之后，有多少个数比我小（降序）
            if(num1 > num2)
            {
                tmp[pos++] = num1;
                ret += (right - cur2 + 1);
                cur1++;
            }
            else
            {
                tmp[pos++] = num2;
                cur2++;
            }
        }

        while(cur1 <= mid)
        {
            tmp[pos++] = record[cur1++];
        }

        while(cur2 <= right)
        {
            tmp[pos++] = record[cur2++];
        }

        for(int i = left ; i <= right ; i++)
        {
            record[i] = tmp[i-left];
        }

        return ret;
    }

    int reversePairs(vector<int>& record) {
        tmp.resize(record.size());
        int ans = _reversePairs(record,0,record.size()-1);

        return ans;
    }
};

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

题目描述：

思路讲解：
本道题需要我们解决 “计算右侧小于当前元素的个数” 问题，和上一题的思路一样，我们可以利用归并排序的分治思想高效求解。核心思路是在归并排序的合并阶段，统计每个元素右侧小于它的元素数量。

每一层的统计策略：找到该数之后，有多少个数比我小（降序）

• nums[cur1] > nums[cur2]; --> ret += (right - cur2 + 1)，cur1++
• nums[cur1] <= nums[cur2]; --> cur2++
  

以下是具体思路：

1. 创建 index 数组记录元素原始索引，用于跟踪元素位置变化
2. 递归将数组分为左、右子数组，直到子数组长度为 1
3. 对两个有序子数组进行合并，同时统计左数组元素右侧的小元素：
   • 若 nums[cur1] > nums[cur2]，则 nums[cur2] 及右侧所有元素均小于 nums[cur1]，因此 count[nums[cur1]的原始索引] += (right - cur2 + 1)
   • 否则，不统计，继续比较下一个元素
   • 合并后更新索引数组，保持索引与元素的对应关系
4. 递归结束后，count 数组即为每个元素右侧小于它的元素数量，返回 count数组

编写代码：

class Solution {
    vector<int> index , tmp_index , tmp_nums;
public:
    void _countSmaller(vector<int>& nums , vector<int>& count , int left , int right) {
        if(left >= right)   return;

        int mid = (left + right) / 2;
        _countSmaller(nums,count,left,mid);
        _countSmaller(nums,count,mid+1,right);

        int cur1 = left , cur2 = mid + 1 , pos = 0;
        while(cur1 <= mid && cur2 <= right)
        {
            if(nums[cur1] > nums[cur2])
            {
                tmp_nums[pos] = nums[cur1];
                count[index[cur1]] += (right - cur2 + 1);
                tmp_index[pos++] = index[cur1++];
            }
            else
            {
                tmp_nums[pos] = nums[cur2];
                tmp_index[pos++] = index[cur2++];
            }
        }

        while(cur1 <= mid)
        {
            tmp_nums[pos] = nums[cur1];
            tmp_index[pos++] = index[cur1++];
        }

        while(cur2 <= right)
        {
            tmp_nums[pos] = nums[cur2];
            tmp_index[pos++] = index[cur2++];
        }

        for(int i = left ; i <= right ; i++)
        {
            nums[i] = tmp_nums[i - left];
            index[i] = tmp_index[i - left];
        }
    }

    vector<int> countSmaller(vector<int>& nums) {
        int size = nums.size();
        vector<int> count(size);
        index.resize(size);
        tmp_index.resize(size);
        tmp_nums.resize(size);

        for(int i = 0 ; i < size ; i++)
        {
            index[i] = i;
        }

        _countSmaller(nums,count,0,size-1);
        return count;
    }
};

四、翻转对

题目描述：

思路讲解：
本道题需要我们计算数组中满足 i < j 且 nums[i] > 2*nums[j] 的数对数量。和第二题的思路一样，我们可以利用归并排序的分治思想高效求解。将数组分成两半，分别排序后合并。在合并之前中，我们可以同步统计满足条件的翻转对。以下是在左右子数组有序情况下，快速统计翻转对的两种策略：

• 策略一：找出该数之前，有多少个数的一半比我大（升序）

  • nums[cur1] > 2*nums[cur2]; --> ret += (mid - cur1 + 1)，cur2++
  • nums[cur1] <= 2*nums[cur2]; --> cur1++
    

• 策略二：找到该数之后，有多少个数的两倍比我小（降序）

  • nums[cur1] > 2*nums[cur2]; --> ret += (right - cur2 + 1)，cur1++
  • nums[cur1] <= 2*nums[cur2]; --> cur2++
    

以下是具体思路：

1. 将数组从中间分为左、右两个子数组，递归处理每个子数组，直到子数组长度为 1。
2. 这里我选择在升序的情况下，使用策略一，找出该数之前，有多少个数的一半比我大
3. 对两个已排序的左右子数组，统计满足条件的翻转对：
   • 若 nums[cur1] > 2*nums[cur2]，则 左子数组 中 cur1 及之后的所有元素都与 nums[cur2] 构成翻转对，翻转对数量增加 (mid - cur1 + 1)
   • 否则，不构成翻转对，继续比较下一个元素
4. 将两个已排序的子数组合并为一个有序数组，供上层递归使用
5. 递归过程中，每层的翻转对数量 = 左子数组内部的翻转对 + 右子数组内部的翻转对 + 合并时跨左右的翻转对

编写代码：

class Solution {
    vector<int> tmp_nums;
public:
    int _reversePairs(vector<int>& nums , int left , int right) {
        if(left >= right) return 0;

        int mid = (left + right) / 2;

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

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

        cur1 = left , cur2 = mid + 1;
        while(cur1 <= mid && cur2 <= right)
        {
            tmp_nums[pos++] = nums[cur1] > nums[cur2] ? nums[cur2++] : nums[cur1++];
        }

        while(cur1 <= mid)
        {
            tmp_nums[pos++] = nums[cur1++];
        }

        while(cur2 <= right)
        {
            tmp_nums[pos++] = nums[cur2++];
        }

        for(int i = left ; i <= right ; i++)
        {
            nums[i] = tmp_nums[i-left];
        }

        return ret;
    }


    int reversePairs(vector<int>& nums) {
        tmp_nums.resize(nums.size());

        return _reversePairs(nums,0,nums.size()-1);
    }
};

结尾

如果有什么建议和疑问，或是有什么错误，大家可以在评论区中提出。
希望大家以后也能和我一起进步！！🌹🌹
如果这篇文章对你有用的话，希望大家给一个三连支持一下！！🌹🌹