逆序对是满足 i

统计 PHP 数组中的逆序对数量，本质是找出所有满足 i $arr[j] 的索引对 (i, j)。这个问题不能靠简单双重循环暴力解决（时间复杂度 O(n²)，大数据下超时），推荐用归并排序思想在线性对数时间内完成（O(n log n)）。

什么是逆序对？

逆序对不是指数组倒序，而是指“顺序错位”的元素对：前面的数比后面的数大，且它们在原数组中位置靠前。例如：

• [2, 4, 1, 3] 中，(2,1)、(4,1)、(4,3) 是逆序对 → 共 3 个；
• [5, 4, 3, 2, 1] 是完全逆序，逆序对数为 C(5,2) = 10；
• [1, 2, 3, 4] 是升序，逆序对数为 0。

用归并排序法高效统计（推荐）

归并排序在合并两个有序子数组时，能自然捕获跨子数组的逆序关系：当左半部分的某个元素 大于 右半部分当前元素，说明它和右半部分从当前起的所有元素都构成逆序对。

PHP 实现要点：

btpanel phpsite 宝塔面板PHP网站

宝塔面板 PHP 网站管理：站点创建、删除、启停、PHP 版本切换、域名管理、SSL证书管理、伪静态管理、数据库管理

下载

立即学习“PHP免费学习笔记（深入）”；

• 递归分割数组至单元素；
• 合并时，若 $left[$i] > $right[$j]，则贡献 count($left) - $i 个逆序对；
• 需在每次合并中累加计数，并返回排序后的子数组供上层使用。

简易可运行示例代码

以下是一个完整、无依赖的 PHP 函数：

function countInversions($arr) {
    if (count($arr) <= 1) return 0;
<pre class="brush:php;toolbar:false;">$mid = (int)(count($arr) / 2);
$left = array_slice($arr, 0, $mid);
$right = array_slice($arr, $mid);

$inv = countInversions($left) + countInversions($right);

// 合并并统计跨区间逆序对
$i = $j = $k = 0;
$merged = [];
while ($i < count($left) && $j < count($right)) {
    if ($left[$i] <= $right[$j]) {
        $merged[$k++] = $left[$i++];
    } else {
        $merged[$k++] = $right[$j++];
        $inv += count($left) - $i; // 关键：左半剩余全部 > 当前右元
    }
}

while ($i < count($left)) $merged[$k++] = $left[$i++];
while ($j < count($right)) $merged[$k++] = $right[$j++];

return $inv;

}

// 测试 echo countInversions([2, 4, 1, 3]); // 输出：3

注意事项与边界情况

实际使用时注意：

• 数组含重复元素（如 [2, 2, 1]）时，定义是否将 > 改为 >= —— 通常逆序对定义为严格大于，重复不计入；
• 大数组慎用递归，PHP 默认栈深度有限，可改写为迭代归并（稍复杂但更健壮）；
• 若只需判断是否存在逆序对（而非总数），一次遍历记录最小后缀即可，O(n) 时间；
• 索引从 0 开始，无需额外偏移处理。