归并排序的进阶应用：求解逆序对数量问题

题目描述：给定一个整数数组，计算数组中逆序对的数量。逆序对定义为：对于数组中的两个元素 nums[i] 和 nums[j]，如果 i < j 且 nums[i] > nums[j]，则 (i, j) 构成一个逆序对。

解题过程：

1. 问题分析

   • 暴力解法需要比较所有元素对，时间复杂度为O(n²)
   • 我们需要更高效的解法，目标是在O(n log n)时间内完成
   • 归并排序的合并过程天然适合统计逆序对

2. 归并排序基础回顾

   • 分治策略：将数组分成两半，分别排序后合并
   • 合并时比较两个有序子数组的元素，按顺序放入原数组

3. 关键观察：在合并过程中统计逆序对

   • 当合并左右两个有序子数组时
   • 如果左子数组当前元素大于右子数组当前元素
   • 说明左子数组中该元素及其后面的所有元素都与右子数组当前元素构成逆序对

4. 具体实现步骤

   • 在归并排序的合并函数中添加逆序对统计
   • 当从右子数组取元素时，累加左子数组剩余元素数量到逆序对计数
   • 递归处理左右子数组，将逆序对数量相加

5. 算法伪代码

   function countInversions(nums):
       return mergeSortCount(nums, 0, len(nums)-1)
   
   function mergeSortCount(nums, left, right):
       if left >= right:
           return 0
   
       mid = (left + right) // 2
       count = mergeSortCount(nums, left, mid) + 
               mergeSortCount(nums, mid+1, right) +
               mergeAndCount(nums, left, mid, right)
       return count
   
   function mergeAndCount(nums, left, mid, right):
       temp = []  // 临时数组
       i, j = left, mid+1
       count = 0
   
       while i <= mid and j <= right:
           if nums[i] <= nums[j]:
               temp.append(nums[i])
               i += 1
           else:
               temp.append(nums[j])
               count += (mid - i + 1)  // 关键步骤
               j += 1
   
       // 将剩余元素复制到临时数组
       while i <= mid:
           temp.append(nums[i])
           i += 1
       while j <= right:
           temp.append(nums[j])
           j += 1
   
       // 将排序结果复制回原数组
       nums[left:right+1] = temp
       return count
   

6. 时间复杂度分析

   • 与归并排序相同，为O(n log n)
   • 空间复杂度O(n)用于临时数组

7. 示例演示
   数组[2,4,1,3,5]的逆序对计算过程：

   • 逆序对：(2,1), (4,1), (4,3)
   • 总数为3对
   • 通过归并排序过程可准确统计出这个数量