逆序对是满足 i $arr[j] 的索引对，可用归并排序在 O(n log n) 时间内高效统计：分割数组递归求解，合并时若 $left[i] > $right[j]，则左半剩余元素均与 $right[j] 构成逆序对，累加 count($left) - $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 实现要点：
立即学习“PHP免费学习笔记（深入）”；
ECTouch移动商城系统
下载
ECTouch是上海商创网络科技有限公司推出的一套基于 PHP 和 MySQL 数据库构建的开源且易于使用的移动商城网店系统！应用于各种服务器平台的高效、快速和易于管理的网店解决方案，采用稳定的MVC框架开发，完美对接ecshop系统与模板堂众多模板，为中小企业提供最佳的移动电商解决方案。ECTouch程序源代码完全无加密。安装时只需将已集成的文件夹放进指定位置，通过浏览器访问一键安装，无需对已有
- 递归分割数组至单元素；
- 合并时，若
$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 开始，无需额外偏移处理。
