Java数组逆序对计数详解

1. 概述

本文将探讨数组逆序对计数问题，这是计算机科学中用于衡量数组与有序状态偏离程度的重要概念。我们将从逆序对的定义和示例讲起，深入分析两种核心解法。

首先介绍暴力解法，通过检查所有元素对来统计逆序对数量；接着讲解更高效的分治策略，利用改进的归并排序算法显著减少比较次数。

2. 什么是数组逆序对？

数组中的逆序对本质上就是元素顺序错乱的情况。当较低索引位置的元素值大于较高索引位置的元素值时，就构成一个逆序对。具体来说，对于数组A，满足以下条件的索引对*(i, j)*即为逆序对：

i < j
A[i] > A[j]

在有序数组中不存在逆序对，因为所有元素都处于正确位置。而在无序数组中，逆序对数量直接反映了数组的"混乱程度"——逆序对越多，通过相邻元素交换排序所需的步骤就越多。

2.1 示例

以简单数组为例：

[3, 1, 2]

该数组包含2个逆序对：

(3,1)：索引0的3 > 索引1的1
(3,2)：索引0的3 > 索引2的2

3. 暴力解法

暴力解法思路简单直接：遍历所有可能的元素对，检查是否构成逆序对。这种方法易于理解和实现，但时间复杂度高达*O(n²)*，处理大型数组时效率低下。

核心逻辑是通过嵌套循环检查所有元素对*(i, j)（其中i < j*），当满足*A[i] > A[j]*时递增计数器：

@Test
void givenArray_whenCountingInversions_thenReturnCorrectCount() {
    int[] input = {3, 1, 2};
    int expectedInversions = 2;

    int actualInversions = countInversionsBruteForce(input);

    assertEquals(expectedInversions, actualInversions);
}

int countInversionsBruteForce(int[] array) {
    int inversionCount = 0;
    for (int i = 0; i < array.length - 1; i++) {
        for (int j = i + 1; j < array.length; j++) {
            if (array[i] > array[j]) {
                inversionCount++;
            }
        }
    }
    return inversionCount;
}

✅ 优点：实现简单，适合小型数组
❌ 缺点：随着数组规模增大，性能急剧下降

4. 优化解法：分治策略

分治策略通过归并排序原理显著提升效率。不再逐对检查，而是递归分割数组至单元素状态，在合并有序子数组时统计跨区逆序对：

@Test
void givenArray_whenCountingInversionsWithOptimizedMethod_thenReturnCorrectCount() {
    int[] inputArray = {3, 1, 2};
    int expectedInversions = 2;

    int actualInversions = countInversionsDivideAndConquer(inputArray);

    assertEquals(expectedInversions, actualInversions);
}

主方法负责参数校验并启动递归：

int countInversionsDivideAndConquer(int[] array) {
    if (array == null || array.length <= 1) {
        return 0;
    }
    return mergeSortAndCount(array, 0, array.length - 1);
}

核心逻辑在mergeSortAndCount方法中：分割数组、递归处理子数组、合并时统计逆序对：

int mergeSortAndCount(int[] array, int left, int right) {
    if (left >= right) {
        return 0;
    }

    int mid = left + (right - left) / 2;
    int inversions = mergeSortAndCount(array, left, mid) + mergeSortAndCount(array, mid + 1, right);

    inversions += mergeAndCount(array, left, mid, right);
    return inversions;
}

mergeAndCount方法执行合并操作并统计跨区逆序对。首先创建临时数组：

int[] leftArray = new int[mid - left + 1];
int[] rightArray = new int[right - mid];

System.arraycopy(array, left, leftArray, 0, mid - left + 1);
System.arraycopy(array, mid + 1, rightArray, 0, right - mid);

⚠️ 注意：System.arraycopy()是高效的数组复制方法

合并时统计逆序对的关键逻辑：

int i = 0, j = 0, k = left, inversions = 0;

while (i < leftArray.length && j < rightArray.length) {
    if (leftArray[i] <= rightArray[j]) {
        array[k++] = leftArray[i++];
    } else {
        array[k++] = rightArray[j++];
        inversions += leftArray.length - i;  // 关键统计点
    }
}

当右数组元素小于左数组元素时，左数组剩余元素均构成逆序对，因此直接增加leftArray.length - i。最后处理剩余元素：

while (i < leftArray.length) {
    array[k++] = leftArray[i++];
}

while (j < rightArray.length) {
    array[k++] = rightArray[j++];
}

return inversions;

✅ 核心优势：时间复杂度优化至*O(n log n)*，适合大规模数据

5. 方法对比

维度	暴力解法	分治解法
时间复杂度	O(n²)	O(n log n)
空间复杂度	O(1)	O(n)（临时数组）
适用场景	小型数组（n < 1000）	中大型数组（n ≥ 1000）
实现难度	简单粗暴	需理解递归与归并逻辑

⚠️ 关键结论：当数组规模超过1000时，分治解法性能优势显著，暴力解法基本不可用

6. 总结

本文系统讲解了数组逆序对计数的两种实现方案：

暴力解法：双重循环检查所有元素对，实现简单但性能差
分治解法：基于归并排序的优化算法，通过递归分割和合并统计实现高效计算

对于有经验的开发者，建议直接采用分治解法——虽然实现稍复杂，但*O(n log n)*的时间复杂度能轻松处理百万级数据。暴力解法仅适用于教学场景或极小规模数据。

完整源码可在GitHub仓库获取。

Persistence

REST

Security