分治算法c++逆序对

### 使用C++通过分治算法计算数组中逆序对数量

#### 什么是逆序对
在一个数组中，如果有两个索引 \(i\) 和 \(j\) 满足 \(i < j\) 并且 \( \text{arr}[i] > \text{arr}[j]\)，则称这对元素构成一个逆序对[^1]。

#### 分治算法原理
利用「归并排序」来计算逆序对是一个非常经典的方法。该方法的关键在于「合并两个有序数组」的过程，在此过程中能够一次性计算出一部分逆序对的数量。具体来说：

- **分解阶段**：将原始数组不断分割成更小的子数组直到每个子数组只含有单个元素。
- **合并阶段**：当重新组合这些已排序的小数组时，每当右边较小的元素被放置到最终位置前，意味着左边剩余未处理的所有元素都与当前右半边元素形成新的逆序对[^2]。

这种方法的时间复杂度为 O(n log n)[^3]。

#### C++代码实现
下面给出完整的基于上述思路的C++程序用于计算给定整型向量内的全部逆序对数目:

#include <vector>
using namespace std;

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        vector<int> tmp(nums.size());
        return mergeSortCounting(nums, tmp, 0, nums.size() - 1);
    }

private:
    long mergeSortCounting(vector<int>& nums, vector<int>& tmp, int left, int right){
        if (left >= right) return 0;
        
        int mid = left + (right - left)/2;
        long cnt = mergeSortCounting(nums, tmp, left, mid) + mergeSortCounting(nums, tmp, mid+1, right);
        int i = left, j = mid + 1, k = left;
        while(i <= mid && j <= right){
            if(nums[i] <= nums[j]){
                tmp[k++] = nums[i++];
            }
            else{
                tmp[k++] = nums[j++];
                cnt += mid - i + 1; // 记录跨越两部分形成的逆序对
            }
        }
        while(i<=mid) tmp[k++]=nums[i++];
        while(j<=right) tmp[k++]=nums[j++];
        copy(tmp.begin()+left,tmp.begin()+right+1,nums.begin()+left);

        return cnt;
    }
};

这段代码实现了归并排序的同时也完成了逆序对计数的任务。`mergeSortCounting()` 函数负责递归调用自身来进行拆分操作，并在每次合并时更新总的逆序对数量[^4]。