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

还在递归调用归并排序吗？文章的剩余内容如下： (l, mid); inversions += mergeSortAndCountInversions(r, n - mid); // 合并两个已排序的子数组，并统计合并过程中产生的逆序对 inversions += mergeAndCountInversions(a, l, r, mid, n - mid); return inversions; } /** * 合并两个已排序的子数组，并统计逆序对。 * * @param a 目标数组，用于存放合并后的结果（原地修改） * @param l 左子数组 * @param r 右子数组 * @param left 左子数组的长度 * @param right 右子数组的长度 * @return 在合并过程中产生的逆序对数量 */ private static int mergeAndCountInversions(int[] a, int[] l, int[] r, int left, int right) { int i = 0, j = 0, k = 0; int inversions = 0; // 遍历左右子数组，按降序合并到目标数组 a while (i < left && j < right) { if (l[i] >= r[j]) { a[k++] = l[i++]; } else { // 发现逆序对：l[i] < r[j]，则 r[j] 与 l[i] 及其后的所有元素构成逆序对 a[k++] = r[j++]; inversions += (left - i); //System.out.println("Inversion found, count updated: " + inversions); } } // 将剩余的元素复制到目标数组 a while (i < left) { a[k++] = l[i++]; } while (j < right) { a[k++] = r[j++]; } return inversions; } public static void main(String[] args) { // 测试用例 int[] hs1 = {7, 3, 5, 4, 1}; int[] hs2 = {8, 5, 6, 7, 2, 1}; int[] hs3 = {3, 2, 1}; // 预期逆序对：3 int[] hs4 = {1, 2, 3}; // 预期逆序对：0 int[] hs5 = {5, 4, 3, 2, 1}; // 预期逆序对：10 int[] hs6 = {1, 3, 5, 2, 4, 6}; // 预期逆序对：3 System.out.println("Inversions in [7, 3, 5, 4, 1]: " + countBaad(hs1)); // 输出: 2 System.out.println("Inversions in [8, 5, 6, 7, 2, 1]: " + countBaad(hs2)); // 输出: 3 System.out.println("Inversions in [3, 2, 1]: " + countBaad(hs3)); // 输出: 3 System.out.println("Inversions in [1, 2, 3]: " + countBaad(hs4)); // 输出: 0 System.out.println("Inversions in [5, 4, 3, 2, 1]: " + countBaad(hs5)); // 输出: 10 System.out.println("Inversions in [1, 3, 5, 2, 4, 6]: " + countBaad(hs6)); // 输出: 3 } } 5. 性能优化与注意事项 空间复杂度：尽管归并排序的时间复杂度为 O(N log N)，但它是一种非原地排序算法，需要额外的 O(N) 空间来存储临时数组。在空间资源受限的情况下，这可能是一个需要考虑的因素。稳定性：归并排序是一种稳定的排序算法，即相等元素的相对顺序在排序后不会改变。这在某些应用中可能很重要。 总结 本文详细介绍了如何利用归并排序算法高效地统计数组中的逆序对。通过改造归并排序的合并过程，我们可以将时间复杂度降低到 O(N log N)，远优于朴素的 O(N^2) 解法。本文提供了完整的 Java 实现代码，并讨论了性能优化和注意事项。希望本教程能够帮助读者更好地理解和应用归并排序算法。

1. 理解“逆序对”问题

在数组处理中，我们有时需要识别那些不符合特定排序规则的元素对。本教程关注的是一种特定类型的“逆序对”：如果一个数组中存在一对元素 (hs[i], hs[j])，其中 i < j 且 hs[i] < hs[j]，则称这对元素构成一个“逆序对”，因为它不满足从大到小的降序排列条件。换句话说，一个较小的数字却出现在一个较大数字的前面，而这两个数字本应在降序排列中颠倒位置。

示例：

• 对于数组 hs = [7, 3, 5, 4, 1]：
  • (3, 5)：3 小于 5，且 3 在 5 之前。这是一个逆序对。
  • (3, 4)：3 小于 4，且 3 在 4 之前。这是一个逆序对。
  • 总计 2 个逆序对。
• 对于数组 hs = [8, 5, 6, 7, 2, 1]：
  • (5, 6)：5 小于 6。
  • (5, 7)：5 小于 7。
  • (6, 7)：6 小于 7。
  • 总计 3 个逆序对。

2. 朴素的双循环解法

最直观的解决方案是使用嵌套循环遍历数组中的所有可能元素对。外层循环固定一个元素 hs[i]，内层循环检查 hs[i] 之后的所有元素 hs[j]（其中 j > i），如果 hs[i] < hs[j]，则计数器加一。

Java 实现：

public static int countBaadBruteForce(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 number pair: (" + hs[i] + "," + hs[j] + ")");
                count++;
            }
        }
    }
    return count;
}

示例调用及输出：

System.out.println(countBaadBruteForce(new int[]{7, 3, 5, 4, 1})); // 输出: 2
System.out.println(countBaadBruteForce(new int[]{8, 5, 6, 7, 2, 1})); // 输出: 3

复杂度分析： 这种方法的平均和最坏时间复杂度为 O(N^2)，其中 N 是数组的长度。对于大规模数据集，这种方法效率低下。

3. 利用归并排序优化逆序对计数

为了提高效率，我们可以利用归并排序（Merge Sort）的特性。归并排序是一种分治算法，它将数组递归地分成两半，分别排序，然后将两个已排序的子数组合并。在合并过程中，我们可以巧妙地统计逆序对。这种方法可以将时间复杂度降低到 O(N log N)。

3.1 归并排序基本原理回顾

归并排序的核心思想是：

1. 分解（Divide）： 将待排序数组从中间分成两个子数组。
2. 解决（Conquer）： 递归地对这两个子数组进行排序。
3. 合并（Combine）： 将两个已排序的子数组合并成一个完整的有序数组。

3.2 改造合并过程以统计逆序对

关键在于“合并”阶段。假设我们有两个已经分别按降序排列的子数组 L 和 R。在将它们合并回原数组 A 的过程中，我们比较 L 的当前元素 l[lIdx] 和 R 的当前元素 r[rIdx]：

• 情况一：l[lIdx] >= r[rIdx]

  • 这意味着 l[lIdx] 已经比 r[rIdx] 大或相等，符合降序排列的趋势。我们将其放入合并后的数组 A 中，并移动 L 的指针 lIdx。此时不产生新的逆序对。

• 情况二：l[lIdx] < r[rIdx]

  • 这意味着 l[lIdx] 比 r[rIdx] 小，但 l[lIdx] 来自于原数组中 r[rIdx] 之前的位置（因为 L 和 R 是由原数组分割而来的，L 中的元素都在 R 中的元素之前）。
  • 因此，l[lIdx] 和 r[rIdx] 构成一个逆序对。
  • 更重要的是，由于 L 数组已经按降序排列，l[lIdx] 之后的元素（即 l[lIdx+1], l[lIdx+2], ..., l[l.length-1]）都比 l[lIdx] 小或相等。这意味着所有这些剩余的 L 数组元素也都小于 r[rIdx]。
  • 所以，当 l[lIdx] < r[rIdx] 时，我们不仅发现了一个逆序对 (l[lIdx], r[rIdx])，实际上，r[rIdx] 会与 L 数组中从 lIdx 开始到末尾的所有 (l.length - lIdx) 个元素都构成逆序对。
  • 我们将 r[rIdx] 放入合并后的数组 A 中，并移动 R 的指针 rIdx，同时将 (l.length - lIdx) 加到总逆序对计数中。

3.3 递归累积计数

归并排序的 mergeSort 函数需要修改为返回逆序对的总数。这意味着每次递归调用 mergeSort 时，不仅要对子数组进行排序，还要将子数组内部产生的逆序对以及在合并两个子数组时产生的逆序对累加起来。

4. 完整的 Java 实现

为了避免修改原始输入数组的副作用，我们首先对输入数组进行复制。

import java.util.Arrays;

public class InversionCounter {

    /**
     * 入口函数：计算数组中的逆序对。
     * 为了避免修改原始数组，先进行数组复制。
     *
     * @param hs 输入数组
     * @return 逆序对的数量
     */
    public static int countBaad(int[] hs) {
        // 复制数组以避免修改原始输入
        int[] copiedArray = Arrays.copyOf(hs, hs.length);
        return mergeSortAndCountInversions(copiedArray, copiedArray.length);
    }

    /**
     * 归并排序并统计逆序对的递归函数。
     * 此方法会原地修改传入的数组，将其按降序排序。
     *
     * @param a 待处理数组
     * @param n 数组长度
     * @return 当前子问题中的逆序对数量
     */
    private static int mergeSortAndCountInversions(int[] a, int n) {
        // 基本情况：如果数组只有一个元素，无需排序，逆序对为0
        if (n <= 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 inversions = 0;
        inversions += mergeSortAndCountInversions

今天带大家了解了的相关知识，希望对你有所帮助；关于文章的技术知识我们会一点点深入介绍，欢迎大家关注golang学习网公众号，一起学习编程~