定义“不满足排序条件”的数对
在处理数组排序问题时，有时我们需要统计数组中特定类型的“异常”数对。本教程关注的是那些不满足“从大到小”排序条件的数对。具体来说，如果数组中存在两个元素 a[i] 和 a[j]，满足以下两个条件：
- i
- a[i]
我们就称 (a[i], a[j]) 为一个“不满足从大到小排序条件的数对”，或者简称为“坏数对”。
示例：
- 对于数组 hs = [7, 3, 5, 4, 1]：
- 3
- 3
- 对于数组 hs = [8, 5, 6, 7, 2, 1]：
- 5
- 5
- 6
理解这个定义是解决问题的关键。接下来，我们将探讨两种实现此计数的方法。
朴素的 O(N^2) 解决方案
最直接的思路是遍历数组中的所有可能的元素对 (a[i], a[j])，并检查它们是否满足“坏数对”的条件。这可以通过嵌套循环实现。
思路阐述： 外层循环从数组的第一个元素遍历到倒数第二个元素（i 从 0 到 length - 2）。内层循环从 i 的下一个元素开始遍历到数组末尾（j 从 i + 1 到 length - 1）。在内层循环中，比较 a[i] 和 a[j]，如果 a[i]
代码示例：
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
}
}优缺点分析：
- 优点： 实现简单直观，易于理解和调试。
- 缺点： 时间复杂度为 O(N^2)，对于大型数组，性能会显著下降。当 N 达到数万甚至更高时，这种方法将变得不可接受。
基于归并排序的 O(N log N) 优化方案
为了提高性能，我们可以利用归并排序（Merge Sort）的分治思想。归并排序在合并（merge）两个已排序的子数组时，可以同时进行计数操作，从而将时间复杂度降低到 O(N log N)。
为何归并排序适合此问题： 归并排序的核心在于将一个大问题分解为两个独立的子问题，然后将子问题的结果合并。在合并过程中，我们正好有机会比较来自不同子数组的元素，这正是统计“坏数对”所需要的。当我们合并两个子数组时，如果一个元素来自左子数组，另一个元素来自右子数组，并且它们满足 a[i]
归并排序核心逻辑与计数原理：
- 递归分解： 将数组递归地分成两半，直到每个子数组只包含一个元素。单个元素的数组不存在“坏数对”，计数为 0。
-
合并阶段的计数（关键）： 这是算法的核心。当我们将两个已排序（这里我们选择降序排序，以便于计数）的子数组 l 和 r 合并成一个大的有序数组 a 时，我们进行计数。
- 我们使用两个指针 lIdx 和 rIdx 分别指向 l 和 r 的当前元素。
- 我们希望将 a 排序成降序。因此，每次比较 l[lIdx] 和 r[rIdx] 时：
- 如果 l[lIdx] >= r[rIdx]：说明 l[lIdx] 更大或相等，应该先放入 a。此时，l[lIdx] 与 r 中任何元素都不会形成“坏数对”（因为 l[lIdx] 至少不小于 r[rIdx]，而 r 中的后续元素会更小或相等）。我们将 l[lIdx] 放入 a，并移动 lIdx。
- 如果 l[lIdx] 此时，关键的计数发生了！ 因为 r[rIdx] 比 l[lIdx] 大，并且 l[lIdx] 在原数组中出现在 r[rIdx] 之前（因为 l 是左半部分，r 是右半部分）。更重要的是，由于 l 数组本身是降序排列的，所以 l[lIdx] 及其之后的所有 l 数组中剩余的元素 (l[lIdx+1], l[lIdx+2], ...) 都将小于或等于 l[lIdx]。因此，所有这些 l 数组中剩余的元素都将小于 r[rIdx]。所以，r[rIdx] 与 l 数组中从 lIdx 开始到末尾的所有元素都形成了“坏数对”。我们将这些坏数对的数量加到总计数中：count += (l.length - lIdx)。然后将 r[rIdx] 放入 a，并移动 rIdx。
- 当一个子数组遍历完后，将另一个子数组中剩余的元素直接放入 a。这些操作不会产生新的“坏数对”计数，因为它们不再是跨子数组的比较。
- 累积结果： 每次 mergeSort 调用都会返回其子数组和自身合并阶段产生的“坏数对”数量，这些数量需要逐层累加。
代码示例（Java）：
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 跨左右子数组产生的坏 
