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

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

本文详细探讨了如何高效统计数组中不满足从大到小排序条件的数对，即满足 a[i] < a[j] 且 i < j 的元素对。文章首先定义了这类“坏数对”，接着介绍了简单直观的 O(N^2) 暴力解法，并深入分析了如何通过修改归并排序算法，在 O(N log N) 的时间复杂度内完成计数，包括其核心计数原理、代码实现细节及性能优化，旨在提供一个全面的教程。

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

在处理数组排序问题时，有时我们需要统计数组中特定类型的“异常”数对。本教程关注的是那些不满足“从大到小”排序条件的数对。具体来说，如果数组中存在两个元素 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学习网公众号吧！