使用归并排序高效统计数组中不满足降序排列的数对

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
    }
}

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 跨左右子数组产生的坏