使用归并排序高效统计数组中的“坏对”数量

public class BadPairCounter {

    /**
     * 使用暴力法统计数组中的“坏对”数量。
     * 时间复杂度：O(N^2)
     *
     * @param hs 输入整数数组
     * @return 坏对的总数
     */
    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++) {
                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): " + countBaadBruteForce(arr1)); // Expected: 2

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

import java.util.Arrays;

public class BadPairMergeSortCounter {

    /**
     * 入口方法，统计数组中的“坏对”数量。
     * 为了不修改原始数组，先进行复制。
     *
     * @param hs 输入整数数组
     * @return 坏对的总数
     */
    public static int countBaad(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) {
        if (n <= 1) { // 基准情况：数组长度为0或1，没有坏对
            return 0;
        }

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

        // 分割数组
        System.arraycopy(a, 0, l, 0, mid);
        if (n - mid > 0) { // 确保右子数组有元素
            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;
    }

    /**
     * 合并两个已降序排序的子数组，并统计合并过程中产生的“坏对”。
     *
     * @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 badPairCount = 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 数组和 r 数组都是降序排列的，
                // r[rIdx] 比 l 数组中从 lIdx 位置到末尾的所有元素都大。
                // 因此，r[rIdx] 与 l 数组中所有剩余元素 (l.length - lIdx 个) 都构成“坏对”。
                badPairCount += (l.length - lIdx);
                // System.out.println("  Found " + (l.length - lIdx) + " bad pairs with " + r[rIdx] + " from " + Arrays.toString(Arrays.copyOfRange(l, lIdx, l.length))); // 可选：详细日志
                a[aIdx++] = 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 badPairCount;
    }

    public static void main(String[] args) {
        int[] arr1 = {7, 3, 5, 4, 1};
        System.out.println("Array: " + java.util.Arrays.toString(arr1) + ", Bad pairs (Merge Sort): " + countBaad(arr1)); // Expected: 2

        int[] arr2 = {8, 5, 6, 7, 2, 1};
        System.out.println("Array: " + java.util.Arrays.toString(arr2) + ", Bad pairs (Merge Sort): " + countBaad(arr2)); // Expected: 3
    }
}