如何查找或统计部分有序数组中所有非相邻的无序元素对

你提到的这类满足「i < j 且 a[i] > a[j]」的无序对就是经典的逆序对，仅统计总数的场景下，存在比插入排序思路O(n²)效率高很多的最优算法，时间复杂度可以做到O(nlogn)，目前常用的有两类实现方案：

方案1：归并排序改造法 #

这是最容易理解和实现的方案，核心利用归并排序分治+合并有序子数组的特性：

• 把数组递归拆分成左右两个子数组，分别统计两个子数组内部的逆序对数量
• 合并两个升序的左右子数组时，统计跨两个子数组的逆序对数量：如果左子数组当前指针指向的元素 > 右子数组当前指针指向的元素，那么左子数组当前指针之后的所有元素都比右指针当前元素大，直接累加左子数组剩余元素的个数即可
• 最终总逆序对数量 = 左子数组逆序对数量 + 右子数组逆序对数量 + 跨子数组逆序对数量

该方案时间复杂度O(nlogn)，空间复杂度O(n)，你给出的示例[1,4,3,2,5]用该方法统计结果恰好为3，和你的预期一致。

方案2：树状数组（Fenwick Tree）改造法 #

该方案适合数组元素数值范围大但数组长度较小的场景，性能表现通常比归并法更好：

• 先对数组元素做离散化处理，把原数值映射到1~n的连续区间（避免数值过大占用过多空间，不影响计数结果）
• 从数组末尾向前遍历，每遍历到一个元素，查询树状数组中已经存储的、比当前元素小的数的个数，该值就是以当前元素为第一个元素的逆序对数量，累加到总结果中
• 查询完成后把当前元素插入到树状数组中

该方案时间复杂度同样为O(nlogn)，离散化后空间复杂度可以压缩到O(n)，实现起来更简洁。

补充说明：如果需要输出所有逆序对，最坏时间复杂度确实是O(n²)，因为完全倒序的数组本身就存在n*(n-1)/2个逆序对，无法突破这个下界；但仅统计数量的场景下，基于比较的逆序对统计的时间复杂度下界就是O(nlogn)，上述两种方案已经是最优解。

内容的提问来源于stack exchange，提问作者Aditya Pratap Singh