本文共 2207 字，大约阅读时间需要 7 分钟。

为了高效计算数组中的逆序对数量，我们可以采用分治法，这种方法类似于归并排序，具有O(n log n)的时间复杂度，显著优于暴力解法的O(n²)复杂度。

逆序对的定义

逆序对是指数组中两个数字，其中前一个数字大于后一个数字。例如，数组[1, 2, 3, 4, 5, 6, 0]中的逆序对包括以下情况：

• (6, 0)
• (5, 0)
• (4, 0)
• (3, 0)
• (2, 0)
• (1, 0)

总共6个逆序对，输出恰为6。

分治法思路

分治法将数组分成两部分，递归处理每一部分，最后合并求逆序对数。归并过程中，同时统计逆序对数，避免第二次排序带来的额外时间。

分治法步骤

样例分析

输入数组：[1, 2, 3, 4, 5, 6, 0]

代码实现

import java.util.ArrayList;import java.util.List;public class InversePairs {    public int inversePairs(int[] nums) {        return merge(nums, 0, nums.length - 1);    }    private int merge(int[] nums, int l, int r) {        if (l >= r) {            return 0;        }        int mid = l + (r - l) / 2;        int left = merge(nums, l, mid);        int right = merge(nums, mid + 1, r);        int reversedCount = mergeCount(nums, l, mid, mid + 1, r);        return left + right + reversedCount;    }    private int mergeCount(int[] nums, int leftL, int leftR, int rightL, int rightR) {        int count = 0;        int leftPointer = leftL;        int rightPointer = rightL;        while (leftPointer <= leftR && rightPointer <= rightR) {            if (nums[leftPointer] > nums[rightPointer]) {                // All elements from leftPointer to leftR are greater than nums[rightPointer], so add (leftR - leftPointer + 1) to count                count += leftR - leftPointer + 1;                rightPointer++;            } else {                // No inversion contributed from the right until now                count += 0;                leftPointer++;            }        }        return count;    }    public static void main(String[] args) {        int[] nums = new int[]{1, 2, 3, 4, 5, 6, 0};        System.out.println(new InversePairs().inversePairs(nums));    }}

代码解释

• merge方法递归地将数组分割并计算逆序对数量。
• mergeCount方法用于统计合并两个有序数组时的逆序对数。
• 主函数 inversePairs 递归调用 merge方法，处理整个数组并输出结果。

逆序对数量计算优化

• 时间复杂度：归并排序思考过程中，时间复杂度为O(n log n)，空间复杂度为O(n)。
• 稳定性：算法正确性通过归纳法保证，稳定性取决于合并过程的正确性，逻辑清晰，容易理解。

此实现正确计算逆序对数量，便于扩展处理多种数据集，尤其是需要高效处理大规模数据的情况。