分治-归并排序

1. 基本思想

"分治-归并排序"是一种经典的排序算法，利用分治法的思想将一个大的问题拆解成多个小问题，再合并求解的过程。具体过程如下：

1. 分解：将待排序的数组不断分成两半，递归地对每个子数组进行归并排序，直到每个子数组只包含一个元素（即已经有序）。

2. 合并：将两个有序的子数组合并成一个有序的大数组。合并过程是归并排序的核心，它确保在合并时保持数组的有序性。

3. 递归：继续递归处理子数组，直到所有子数组都已排序并合并成一个完整的有序数组。

归并排序的时间复杂度为O(n log n)，由于需要额外的空间来存储临时数组，因此空间复杂度为O(n)。它是一种稳定的排序算法，适用于大规模数据的排序。

2. 排序数组（中等）

tmp：用于在合并阶段存储排序后的中间结果。

递归基：

 - if (l >= r)：当左边界 l 大于或等于右边界 r 时，说明区间长度为 1 或 0，此时区间本身有序，不需要进一步处理。

划分区间：

 - int mid = (l + r) >> 1：通过计算中间点 mid，将当前区间 [l, r] 分为两部分：

    - 左区间 [l, mid]

    - 右区间 [mid + 1, r]

合并两个有序区间：

 - int left = l, right = mid + 1, i = 0：初始化三个指针：

 - left 指向左区间的起始位置。

 - right 指向右区间的起始位置。

 - i 指向临时数组 tmp 的起始位置。

比较左右区间的元素：

    - 如果左区间的当前元素小于等于右区间的当前元素，将左区间的元素加入 tmp，并移动左指针。

    - 否则，将右区间的元素加入 tmp，并移动右指针。 

处理剩余元素：

    - 左区间或右区间可能有元素未处理完毕，需要将剩余的元素依次加入 tmp。

还原排序结果：

 - for(int i = l; i <= r; i++) nums[i] = tmp[i - l];

    - 将临时数组 tmp 中的排序结果还原到原数组的对应区间 [l, r]。

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

        //1.选取中间点划分区间
        int mid = (l + r) >> 1;

        //2.把左右区间排序
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);

        //3. 合并两个有序数组
        int left = l, right = mid + 1, i = 0;
        while(left <= mid && right <= r)
        {
            if(nums[left] <= nums[right]) tmp[i++] = nums[left++];
            else tmp[i++] = nums[right++];
        }
        while(left <= mid) tmp[i++] = nums[left++];
        while(right <= r) tmp[i++] = nums[right++];

        //4. 还原
        for(int i = l; i <= r; i++)
            nums[i] = tmp[i - l];
        
    }
};

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

3. 交易逆序对的总数（困难）

基本思想和与上面相同，不同点在于需要在排序时记录逆序对的个数。该题使用归并排序，排序时使用降序和升序都可以解决问题，下面以升序为例。

由于我们使用归并排序，因此进入下面第三步时[left, mid], [mid + 1, right]左右两区间各自已经有序。当我们nums[cur1]和nums[cur2]来排序时，如果nums[cur1] > nums[cur2] ，说明[cur1, mid]之间的数（升序）都大于nums[cur2]，都构成逆序对。

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;

        //1. 找中间点将数组分成两部分
        int mid = (left + right) >> 1;

        //2. 左区间逆序对 + 排序 + 右区间逆序对 + 排序 
        int ret = 0;
        ret += mergeSort(record, left, mid);
        ret += mergeSort(record, mid + 1, right);

        //3. 统计左右区间逆序个数 + 合并两个有序数组
        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++];
            }
        }

        //4. 处理未完成排序 + 将已排序部分加入目标数组
        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;
    }
};

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

4, 计算右侧小于当前元素的个数（困难）

这一题与上面的不同点在于排序时要记录nums数组中元素原来的下标，用于在累加每次归并时符合题意的个数。

class Solution {
    vector<int> ret;
    int tmpr[100000];
    vector<int> index;
    int tmpi[100000];
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;

        //1. 找中间值，将数组划分成两部分
        int mid = (left + right) >> 1;

        //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])
            {
                tmpi[i] = index[cur2];
                tmpr[i++] = nums[cur2++];
            }
            else 
            {
                ret[index[cur1]] += right - cur2 + 1;
                tmpi[i] = index[cur1];   
                tmpr[i++] = nums[cur1++];
            }
        }
        //4. 处理排序+还原
        while(cur1 <= mid)
        {
            tmpi[i] = index[cur1]; 
            tmpr[i++] = nums[cur1++]; 
        }
        while(cur2 <= right)
        {
            tmpi[i] = index[cur2]; 
            tmpr[i++] = nums[cur2++]; 
        }
        for(int j = left; j <= right; ++j)
        {
            nums[j] = tmpr[j - left];
            index[j] = tmpi[j - left];
        }
    }
};

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

5. 翻转对

这题的不同点在于，排序和记录翻转对的条件不同。

例如在逆序对那题 排序和判断是否逆序对 的条件都是nums[cur1] <= nums[cur2]

而在本题中，排序的条件是nums[cur1] <= nums[cur2]，而判断是否是翻转对条件是nums[cur2] >= nums[cur1] / 2.0，需要分开处理。

class Solution {
    int tmp[50000];
    
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 count = 0;
        //1. 找中间值将数组分成两个部分
        int mid = (left + right) >> 1;

        //2. 处理左右区间
        count += mergeSort(nums, left, mid);
        count += mergeSort(nums, mid + 1, right);

        //3. 处理一左一右
        int cur1 = left, cur2 = mid + 1, i = 0;
        while(cur1 <= mid)
        {
            while(cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) cur2++;
            if(cur2 > right) 
                break;
            count += right - cur2 + 1;
            cur1++;
        }
        //4. 降序
        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++];
        //5. 还原数组
        for(int j = left; j <= right; ++j)
            nums[j] = tmp[j - left];
        return count;
    }
};

 493. 翻转对 - 力扣（LeetCode）