归并排序求逆序对的高效方法

本文深入解析了统计数组中逆序对（即不满足从大到小排序的数对）的高效方法。首先明确了“坏数对”的定义，即满足 a[i]

定义“不满足排序条件”的数对

在处理数组排序问题时，有时我们需要统计数组中特定类型的“异常”数对。本教程关注的是那些不满足“从大到小”排序条件的数对。具体来说，如果数组中存在两个元素 a[i] 和 a[j]，满足以下两个条件：

1. i < j（即 a[i] 在 a[j] 之前出现）
2. a[i] < a[j]（即 a[i] 小于 a[j]）

我们就称 (a[i], a[j]) 为一个“不满足从大到小排序条件的数对”，或者简称为“坏数对”。

示例：

• 对于数组 hs = [7, 3, 5, 4, 1]：
  • 3 < 5 (索引 1 < 索引 2)
  • 3 < 4 (索引 1 < 索引 3) 因此，坏数对的数量为 2。
• 对于数组 hs = [8, 5, 6, 7, 2, 1]：
  • 5 < 6 (索引 1 < 索引 2)
  • 5 < 7 (索引 1 < 索引 3)
  • 6 < 7 (索引 2 < 索引 3) 因此，坏数对的数量为 3。

理解这个定义是解决问题的关键。接下来，我们将探讨两种实现此计数的方法。

朴素的 O(N^2) 解决方案

最直接的思路是遍历数组中的所有可能的元素对 (a[i], a[j])，并检查它们是否满足“坏数对”的条件。这可以通过嵌套循环实现。

思路阐述： 外层循环从数组的第一个元素遍历到倒数第二个元素（i 从 0 到 length - 2）。内层循环从 i 的下一个元素开始遍历到数组末尾（j 从 i + 1 到 length - 1）。在内层循环中，比较 a[i] 和 a[j]，如果 a[i] < a[j]，则计数器加一。

代码示例：

public class BadPairCounter {

    /**
     * 使用双重循环统计数组中不满足从大到小排序条件的数对。
     * 时间复杂度为 O(N^2)。
     *
     * @param hs 输入数组
     * @return 坏数对的数量
     */
    public static int countBadPairsBruteForce(int[] hs) {
        int count = 0;
        for (int i = 0; i < hs.length; i++) {
            for (int j = i + 1; j < hs.length; j++) {
                // 比较当前元素 hs[i] 与其后面的所有元素 hs[j]
                if (hs[i] < hs[j]) {
                    // System.out.println("Found bad pair: (" + hs[i] + "," + hs[j] + ")"); // 可选：打印坏数对
                    count++;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[] arr1 = {7, 3, 5, 4, 1};
        System.out.println("Array: " + java.util.Arrays.toString(arr1) + ", Bad pairs (Brute Force): " + countBadPairsBruteForce(arr1)); // 预期输出 2

        int[] arr2 = {8, 5, 6, 7, 2, 1};
        System.out.println("Array: " + java.util.Arrays.toString(arr2) + ", Bad pairs (Brute Force): " + countBadPairsBruteForce(arr2)); // 预期输出 3
    }
}

优缺点分析：

• 优点： 实现简单直观，易于理解和调试。
• 缺点： 时间复杂度为 O(N^2)，对于大型数组，性能会显著下降。当 N 达到数万甚至更高时，这种方法将变得不可接受。

基于归并排序的 O(N log N) 优化方案

为了提高性能，我们可以利用归并排序（Merge Sort）的分治思想。归并排序在合并（merge）两个已排序的子数组时，可以同时进行计数操作，从而将时间复杂度降低到 O(N log N)。

为何归并排序适合此问题： 归并排序的核心在于将一个大问题分解为两个独立的子问题，然后将子问题的结果合并。在合并过程中，我们正好有机会比较来自不同子数组的元素，这正是统计“坏数对”所需要的。当我们合并两个子数组时，如果一个元素来自左子数组，另一个元素来自右子数组，并且它们满足 a[i] < a[j] 的条件，我们就可以进行计数。

归并排序核心逻辑与计数原理：

1. 递归分解： 将数组递归地分成两半，直到每个子数组只包含一个元素。单个元素的数组不存在“坏数对”，计数为 0。
2. 合并阶段的计数（关键）： 这是算法的核心。当我们将两个已排序（这里我们选择降序排序，以便于计数）的子数组 l 和 r 合并成一个大的有序数组 a 时，我们进行计数。
   • 我们使用两个指针 lIdx 和 rIdx 分别指向 l 和 r 的当前元素。
   • 我们希望将 a 排序成降序。因此，每次比较 l[lIdx] 和 r[rIdx] 时：
     • 如果 l[lIdx] >= r[rIdx]：说明 l[lIdx] 更大或相等，应该先放入 a。此时，l[lIdx] 与 r 中任何元素都不会形成“坏数对”（因为 l[lIdx] 至少不小于 r[rIdx]，而 r 中的后续元素会更小或相等）。我们将 l[lIdx] 放入 a，并移动 lIdx。
     • 如果 l[lIdx] < r[rIdx]：说明 r[rIdx] 更大。按照降序排序的规则，r[rIdx] 应该先放入 a。此时，关键的计数发生了！ 因为 r[rIdx] 比 l[lIdx] 大，并且 l[lIdx] 在原数组中出现在 r[rIdx] 之前（因为 l 是左半部分，r 是右半部分）。更重要的是，由于 l 数组本身是降序排列的，所以 l[lIdx] 及其之后的所有 l 数组中剩余的元素 (l[lIdx+1], l[lIdx+2], ...) 都将小于或等于 l[lIdx]。因此，所有这些 l 数组中剩余的元素都将小于 r[rIdx]。所以，r[rIdx] 与 l 数组中从 lIdx 开始到末尾的所有元素都形成了“坏数对”。我们将这些坏数对的数量加到总计数中：count += (l.length - lIdx)。然后将 r[rIdx] 放入 a，并移动 rIdx。
   • 当一个子数组遍历完后，将另一个子数组中剩余的元素直接放入 a。这些操作不会产生新的“坏数对”计数，因为它们不再是跨子数组的比较。
3. 累积结果： 每次 mergeSort 调用都会返回其子数组和自身合并阶段产生的“坏数对”数量，这些数量需要逐层累加。

代码示例（Java）：

import java.util.Arrays;

public class BadPairMergeSortCounter {

    /**
     * 主入口函数，调用归并排序进行坏数对计数。
     * 为了避免修改原始数组，建议在外部进行数组复制。
     *
     * @param hs 输入数组
     * @return 坏数对的数量
     */
    public static int countBadPairsMergeSort(int[] hs) {
        // 为了避免修改原始数组，先复制一份
        int[] tempArray = Arrays.copyOf(hs, hs.length);
        return mergeSortAndCount(tempArray, tempArray.length);
    }

    /**
     * 归并排序的核心递归函数，同时进行坏数对计数。
     *
     * @param a 待排序和计数的数组片段
     * @param n 数组片段的长度
     * @return 当前片段及其子片段中坏数对的总数
     */
    private static int mergeSortAndCount(int[] a, int n) {
        if (n <= 1) { // 数组长度为0或1时，没有坏数对
            return 0;
        }

        int mid = n / 2;
        int[] l = new int[mid];
        int[] r = new int[n - mid];

        // 使用 System.arraycopy 提高效率
        System.arraycopy(a, 0, l, 0, mid);
        if (n - mid > 0) { // 确保右半部分有元素
            System.arraycopy(a, mid, r, 0, n - mid);
        }

        // 递归计算左右子数组中的坏数对，并累加
        int totalBadPairs = 0;
        totalBadPairs += mergeSortAndCount(l, mid);
        totalBadPairs += mergeSortAndCount(r, n - mid);

        // 合并左右子数组并计算跨子数组的坏数对
        totalBadPairs += mergeAndCount(a, l, r);
        return totalBadPairs;
    }

    /**
     * 合并两个已排序（降序）的子数组，并计算跨子数组的坏数对。
     *
     * @param a 目标数组，用于存放合并后的结果
     * @param l 左子数组
     * @param r 右子数组
     * @return 跨左右子数组产生的坏

理论要掌握，实操不能落！以上关于《归并排序求逆序对的高效方法》的详细介绍，大家都掌握了吧！如果想要继续提升自己的能力，那么就来关注golang学习网公众号吧！