基于归并排序统计降序违规对的Java代码错误排查求助

我有一个Java函数public static int countBaad(int[] hs)，输入一个数组，需要统计数组中前面元素小于后面元素的数对数量（即不符合从大到小排序的违规对）。

示例： #

• 当hs = [7,3,5,4,1]时，答案应为2，违规对是(3,5)和(3,4)，因为3小于后面的数，不符合降序排列要求；
• 当hs = [8,5,6,7,2,1]时，答案应为3，其中5小于6、7（2个对），6小于7（1个对），总计3个违规对。

尝试的代码： #

public static int countBaad(int[] hs){
    return mergeSort(hs, hs.length);
}

public static int mergeSort(int[] a, int n) {
    if (n < 2) {
        return n;
    }
    int mid = n / 2;
    int[] l = new int[mid];
    int[] r = new int[n - mid];

    for (int i = 0; i < mid; i++) {
        l[i] = a[i];
    }
    for (int i = mid; i < n; i++) {
        r[i - mid] = a[i];
    }
    mergeSort(l, mid);
    mergeSort(r, n - mid);

    return merge(a, l, r, mid, n - mid);
}
public static int merge(int[] a, int[] l, int[] r, int left, int right) {
    int size = 0;
    int i = 0, j = 0, k = 0;
    while (i < left && j < right) {
        if (l[i] <= r[j]) {
            a[k++] = l[i++];
            size++;
        }
        else {
            a[k++] = r[j++];
            size++;
        }
    }
    while (i < left) {
        a[k++] = l[i++];
        size++;
    }
    while (j < right) {
        a[k++] = r[j++];
        size++;
    }
    return size;
}

错误结果： #

• 输入hs = [7,3,5,4,1]返回5；
• 输入hs = [8,5,6,7,2,1]返回6。

核心问题 #

你的代码完全没实现统计违规对的逻辑，当前逻辑只是在统计数组的元素总数（每次merge返回元素个数，最终结果等于数组长度），和需求完全不符。归并排序统计这类数对的核心是在合并阶段统计跨左右子数组的违规对，同时累加左右子数组内部的违规数。

具体问题点 #

1. 递归终止条件错误：当数组长度小于2时，没有元素对，违规数应为0，而非返回n；
2. mergeSort未累加子数组违规数：递归处理左右子数组时，没有保存它们的违规数，只返回了merge的结果；
3. merge函数逻辑错误：当前只是做普通的归并合并，没有统计任何违规对，反而在计数元素数量。

修正后的代码 #

import java.util.Arrays;

public static int countBaad(int[] hs) {
    // 避免修改原数组，拷贝一份进行排序统计
    int[] copy = Arrays.copyOf(hs, hs.length);
    return mergeSort(copy, copy.length);
}

public static int mergeSort(int[] a, int n) {
    if (n < 2) {
        // 长度小于2，没有元素对，违规数为0
        return 0;
    }
    int mid = n / 2;
    int[] l = new int[mid];
    int[] r = new int[n - mid];

    for (int i = 0; i < mid; i++) {
        l[i] = a[i];
    }
    for (int i = mid; i < n; i++) {
        r[i - mid] = a[i];
    }

    // 累加左右子数组内部的违规数
    int leftCount = mergeSort(l, mid);
    int rightCount = mergeSort(r, n - mid);

    // 加上跨左右子数组的违规数
    return leftCount + rightCount + merge(a, l, r, mid, n - mid);
}

public static int merge(int[] a, int[] l, int[] r, int left, int right) {
    int badCount = 0;
    int i = 0, j = 0, k = 0;

    // 左右子数组已经是降序排序好的，合并时统计违规对
    while (i < left && j < right) {
        if (l[i] > r[j]) {
            // 左元素大于右元素，符合降序，直接放入结果
            a[k++] = l[i++];
        } else {
            // 左元素<=右元素，说明左子数组中从i到末尾的所有元素都小于当前右元素
            // 这些都是违规对，数量为left - i
            badCount += left - i;
            // 放入右元素到结果
            a[k++] = r[j++];
        }
    }

    // 处理剩余元素
    while (i < left) {
        a[k++] = l[i++];
    }
    while (j < right) {
        a[k++] = r[j++];
    }

    return badCount;
}

修正说明 #

1. 递归终止：返回0，符合无元素对的情况；
2. 累加子数组违规数：递归左右子数组时保存各自的违规数，最终总和加上合并阶段的违规数；
3. 合并阶段统计：利用左右子数组已降序的特性，当左元素<=右元素时，左子数组剩余的所有元素都和当前右元素形成违规对，直接计算数量left - i；
4. 保护原数组：新增数组拷贝，避免排序修改输入的原数组。

测试验证 #

• 输入[7,3,5,4,1]，返回2，符合预期；
• 输入[8,5,6,7,2,1]，返回3，符合预期。

内容的提问来源于stack exchange，提问作者Dave Shah