数组中的逆序对：基于归并排序的高效解法

创作时间:

作者:

@小白创作中心

数组中的逆序对：基于归并排序的高效解法

引用

CSDN

https://m.blog.csdn.net/2401_89367332/article/details/144307977

在算法和数据结构领域，"逆序对"是一个经典的计算问题。本文将详细介绍如何使用归并排序算法高效解决"数组中的逆序对"问题，包括算法原理、代码实现、复杂度分析以及应用场景等多个方面。

问题背景

在算法和数据结构领域，"逆序对"是一个经典的计算问题。逆序对定义为数组中前面的元素大于后面的元素的数对。例如，在序列[7,5,6,4]中，存在的逆序对包括：

(7,5)
(7,6)
(7,4)
(5,4)
(6,4)

问题分析

问题要求

给定一个整数数组，要求计算数组中所有逆序对的总数。

暴力解法的局限性

最直接的解法是通过暴力遍历，对每一个元素与其后续元素进行比较。但这种方法的时间复杂度为O(n²)，在处理大规模数据时效率极低。

归并排序解法

核心思路

本题的高效解法基于归并排序的合并阶段。归并排序分治算法不仅可以对数组进行排序，还能在排序过程中统计逆序对。

算法原理

将数组递归地分成两个子数组
分别对左右子数组进行归并排序
在合并有序子数组的过程中统计逆序对

逆序对统计关键点

当右子数组的元素小于左子数组的元素时，意味着：

右子数组的当前元素与左子数组的从当前位置到末尾的所有元素都构成逆序对
逆序对的数量等于左子数组中剩余元素的个数

代码实现详解

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        vector<int> tmp(nums.size());
        return mergesort(0, nums.size(), nums, tmp);
    }
    int mergesort(int left, int right, vector<int> & nums, vector<int> & tmp) {
        // 递归终止条件：子数组长度小于2
        if (left >= right-1) {
            return 0;
        }
        
        // 分治：计算中间位置
        int mid = (left+right)/2;
        
        // 递归统计左右子数组的逆序对
        int total = mergesort(left, mid, nums, tmp) + 
                    mergesort(mid, right, nums, tmp);
        
        // 将原数组对应区间复制到临时数组
        copy(nums.begin()+left, nums.begin()+right, tmp.begin()+left);
        
        // 合并有序子数组并统计逆序对
        int l_head = left, r_head = mid;
        for (int k = left; k < right; k++) {
            // 左子数组遍历完毕
            if (l_head == mid) {
                nums[k] = tmp[r_head++];
            }
            // 右子数组遍历完毕
            else if(r_head == right) {
                nums[k] = tmp[l_head++];
            }
            // 发现逆序对：右子数组元素小于左子数组元素
            else if (tmp[l_head] > tmp[r_head]) {
                nums[k] = tmp[r_head++];
                total += mid-l_head;  // 关键：统计逆序对数量
            }
            // 正常有序情况
            else {
                nums[k] = tmp[l_head++];
            }
        }
        return total;
    }
};