Java 中使用归并排序高效统计“逆序对”：不满足降序排列条件的数对

public class ArrayInversionCounter {

    /**
     * 使用双循环统计不满足降序排列条件的数对（逆序对）。
     * 时间复杂度：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) {
        System.out.println("--- 暴力解法测试 ---");
        int[] arr1 = {7, 3, 5, 4, 1};
        System.out.println("数组: " + java.util.Arrays.toString(arr1) + ", 逆序对数量: " + countBadPairsBruteForce(arr1)); // 预期输出: 2

        int[] arr2 = {8, 5, 6, 7, 2, 1};
        System.out.println("数组: " + java.util.Arrays.toString(arr2) + ", 逆序对数量: " + countBadPairsBruteForce(arr2)); // 预期输出: 3
    }
}

import java.util.Arrays; // 引入Arrays类以便使用toString和arraycopy

public class MergeSortInversionCounter {

    /**
     * 统计不满足降序排列条件的数对（逆序对）的入口函数。
     * 为了避免修改原始数组，先复制一份。
     *
     * @param hs 输入数组
     * @return 逆序对的数量
     */
    public static int countBadPairsMergeSort(int[] hs) {
        // 创建数组副本，避免修改原始输入数组
        int[] tempArray = Arrays.copyOf(hs, hs.length);
        return mergeSort(tempArray, tempArray.length);
    }

    /**
     * 归并排序主函数，递归地分割数组并累加逆序对计数。
     *
     * @param a 待排序和计数的数组（或子数组）
     * @param n 数组（或子数组）的长度
     * @return 当前子数组中的逆序对数量
     */
    public static int mergeSort(int[] a, int n) {
        // 基本情况：如果数组只有一个元素，无需排序，逆序对为0
        if (n < 2) {
            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);
        System.arraycopy(a, mid, r, 0, n - mid);

        // 递归计算左右子数组中的逆序对，并将结果累加
        int result = 0;
        result += mergeSort(l, mid);
        result += mergeSort(r, n - mid);

        // 合并左右子数组并计算跨子数组的逆序对
        result += merge(a, l, r); 
        return result;
    }

    /**
     * 合并两个已排序的子数组，并计算合并过程中产生的逆序对。
     * 同时将合并后的结果存回原数组 a 中，使其按降序排列。
     *
     * @param a 原始数组的引用，用于存放合并后的降序结果
     * @param l 左子数组 (已降序)
     * @param r 右子数组 (已降序)
     * @return 合并过程中产生的逆序对数量
     */
    public static int merge(int[] a, int[] l, int[] r) {
        // System.out.println("Merging " + Arrays.toString(l) + " and " + Arrays.toString(r)); // 可选：打印合并过程
        int inversionCount = 0;
        int lIdx = 0, rIdx = 0, aIdx = 0; // 左子数组索引，右子数组索引，目标数组索引

        // 遍历左右子数组，进行比较和合并
        while (lIdx < l.length && rIdx < r.length) {
            if (l[lIdx] >= r[rIdx]) {
                // 如果左边元素更大或相等，符合降序排列，将其放入结果数组
                a[aIdx++] = l[lIdx++];
            } else {
                // 如果右边元素更大（即 l[lIdx] < r[rIdx]），则 l[lIdx] 与 r[rIdx] 构成逆序对。
                // 并且由于 l 数组已降序，l[lIdx] 之后的所有元素都小于或等于 l[lIdx]，
                // 所以 r[rIdx] 也比 l 数组中所有剩余元素都大。
                // 此时，l 数组中从 lIdx 到末尾的所有元素都与 r[rIdx] 构成逆序对。
                // System.out.println("  Found bad pair: (" + l[lIdx] + "," + r[rIdx] + ")"); // 仅作演示
                inversionCount += (l.length - lIdx); // 累加逆序对数量
                a[aIdx++] = r[rIdx++]; // 将 r[rIdx] 放入结果数组
            }
        }

        // 将剩余的左子数组元素复制到结果数组
        if (lIdx < l.length) {
            System.arraycopy(l, lIdx, a, aIdx, l.length - lIdx);
        }
        // 将剩余的右子数组元素复制到结果数组
        if (rIdx < r.length) {
            System.arraycopy(r, rIdx, a, aIdx, r.length - rIdx);
        }

        return inversionCount;
    }

    public static void main(String[] args) {
        System.out.println("\n--- 归并排序解法测试 ---");
        int[] arr1 = {7, 3, 5, 4, 1};
        System.out.println("数组: " + java.util.Arrays.toString(arr1) + ", 逆序对数量: " + countBadPairsMergeSort(arr1)); // 预期输出: 2

        int[] arr2 = {8, 5, 6, 7, 2, 1};
        System.out.println("数组: " + java.util.Arrays.toString(arr2) + ", 逆序对数量: " + countBadPairsMergeSort(arr2)); // 预期输出: 3
    }
}