计数逆序对（Count Inversions）的进阶应用：利用归并排序高效统计全局逆序数 题目描述 给定一个整数数组 nums ，统计数组中逆序对的数量。逆序对的定义为：在数组中的两个元素 (i, j) ，如果满足 i < j 且 nums[i] > nums[j] ，则称 (i, j) 为一个逆序对。要求设计一个时间复杂度优于 O(n²) 的算法。 解题过程 暴力法的局限性 最直接的方法是遍历所有可能的 (i, j) 对（i < j），检查是否满足 nums[i] > nums[j] 。这种方法的时间复杂度为 O(n²)，在数据量较大时效率极低。 归并排序的启发 归并排序的核心思想是分治：将数组不断二分，分别排序后再合并。在合并两个已排序的子数组时，可以高效地统计逆序对： 设左子数组为 left[] ，右子数组为 right[] ，当前左指针为 i ，右指针为 j 。 在合并过程中，如果 left[i] > right[j] ，则说明 left[i] 大于右子数组中从 j 开始的所有剩余元素（因为右子数组已排序），此时逆序对数量需增加 len(left) - i 。 具体步骤 分治 ：将数组递归地二分，直到子数组长度为 1（天然有序）。 合并与统计 ：在合并两个有序子数组时： 比较 left[i] 和 right[j] ，若 left[i] <= right[j] ，则将 left[i] 放入合并数组，左指针 i 右移。 若 left[i] > right[j] ，则将 right[j] 放入合并数组，并增加逆序对计数 count += len(left) - i （因为左子数组中剩余元素均大于 right[j] ），右指针 j 右移。 递归返回 ：每个递归层级返回当前子数组的逆序对总数，包括左右子数组内部的逆序对和合并过程中发现的跨子数组逆序对。 示例分析 以数组 [4, 3, 2, 1] 为例： 第一层二分：左 [4, 3] ，右 [2, 1] 。 递归处理左子数组：合并 [4] 和 [3] 时发现 4 > 3 ，计数 +1，得到有序左子数组 [3, 4] 。 递归处理右子数组：合并 [2] 和 [1] 时发现 2 > 1 ，计数 +1，得到有序右子数组 [1, 2] 。 合并左右子数组：比较 3 > 1 ，计数 +2（因左子数组剩余 [3, 4] 均大于 1）；比较 3 > 2 ，计数 +2；比较 4 > 2 ，计数 +1。总逆序对数为 1+1+2+2+1=7。 复杂度分析 时间复杂度：O(n log n)，与归并排序相同。 空间复杂度：O(n)，用于合并时的临时数组。 通过结合归并排序的分治策略，逆序对统计的效率从 O(n²) 优化至 O(n log n)，适用于大规模数据。