什么是逆序对？
在开始讨论计算逆序对数量的问题前，我们需要了解什么是逆序对。在一个数组中，如果两个数在数组中的相对位置与它们在原来有序数列中的相对位置相反，那么这两个数构成了一个逆序对。例如，数组[3, 2, 1]中，(3,2)、(3,1)、(2,1)都是逆序对。
问题描述
给定一个长度为n的数组，计算其中大小为三的逆序对数量。例如，数组[3, 2, 1, 4, 5]中，大小为三的逆序对有(3,2,1)和(4,3,2)两个，因此逆序对数量为2。
朴素算法
一个最直观的思路是对于每个大小为三的数列，判断其是否为逆序对。这可以通过三重循环来实现，它的时间复杂度为O(n^3)。代码如下：
function naiveCount($arr)
{
$n = count($arr);
$count = 0;
for ($i = 0; $i < $n - 2; $i++) {
for ($j = $i + 1; $j < $n - 1; $j++) {
for ($k = $j + 1; $k < $n; $k++) {
if ($arr[$i] > $arr[$j] && $arr[$j] > $arr[$k]) {
$count++;
}
}
}
}
return $count;
}
虽然这个算法很简单，但是它的效率非常低。对于长度为n的数组，时间复杂度为O(n^3)，当n很大时，算法的效率就会变得非常糟糕。因此，我们需要寻求其他的算法来解决这个问题。
归并排序思想
归并排序概述
当我们需要对一个数组进行排序时，通常会选择归并排序。归并排序是一种分治算法，它的基本思想是将原问题划分为若干个子问题，分别求解子问题，最后将子问题的解合并得到原问题的解。归并排序的基本流程如下：
将待排序数组不断递归划分为左右两个子数组，直到每个子数组只剩下一个元素
将左右两个子数组合并，得到一个新的有序数组
持续以上两步，直到所有子数组都合并成一个有序数组
关于归并排序的详细介绍可以参考其他文章，这里不再赘述。
归并排序求逆序对
因为归并排序的过程中，子数组都是已经有序的。因此，对于原数组中的两个数$x$和$y$，如果$x$在归并排序过程中出现在$y$的后面，那么它们构成了一个逆序对。举个例子，考虑下图所示的数组：
[4, 2, 3, 1]
首先将数组递归划分，得到下面的树形结构：
[4, 2, 3, 1]
/ \
[4, 2] [3, 1]
/ \ / \
[4] [2] [3] [1]
接下来进行归并排序，得到新的子数组。这一步过程中，左子数组的2已经在右子数组的3的前面出现，右子数组的1已经在左子数组的4的前面出现，因此数组中有两个逆序对。归并排序过程如下图所示：
[4, 2, 3, 1] -> [2, 4] [1, 3] -> [1, 2, 3, 4]
得到一个有序数组后，就可以统计逆序对数量了。仍然是使用一个归并排序的过程来完成，只不过在数组合并的过程中，需要多加一个统计逆序对数量的步骤。具体来说，每次比较左右两个子数组的最后一个元素时，如果左子数组的最后一个元素$x$大于右子数组的最后一个元素$y$，那么左子数组中$x$后面的所有元素都与$y$构成逆序对，逆序对数量为左子数组剩余的元素个数。代码如下：
function mergeCount(&$arr, $left, $mid, $right)
{
$i = $left;
$j = $mid + 1;
$k = 0;
$tmp = array();
$count = 0;
while ($i <= $mid && $j <= $right) {
if ($arr[$i] <= $arr[$j]) {
$tmp[$k++] = $arr[$i++];
} else {
$count += $mid - $i + 1;
$tmp[$k++] = $arr[$j++];
}
}
while ($i <= $mid) {
$tmp[$k++] = $arr[$i++];
}
while ($j <= $right) {
$tmp[$k++] = $arr[$j++];
}
for ($i = 0; $i < $k; $i++) {
$arr[$left + $i] = $tmp[$i];
}
return $count;
}
function mergeSort(&$arr, $left, $right)
{
$count = 0;
if ($left < $right) {
$mid = (int)(($left + $right) / 2);
$count = mergeSort($arr, $left, $mid) + mergeSort($arr, $mid + 1, $right);
$count += mergeCount($arr, $left, $mid, $right);
}
return $count;
}
在上面的代码中，$left$和$right$分别表示待排序的子数组的左右边界。在$mergeSort$的过程中，可以通过递归不断地将子数组分成更小的子数组。在$mergeCount$的过程中，$left$到$mid$和$mid+1$到$right$这两个子数组已经有序了，我们需要将它们合并成一个有序的数组。在这个过程中，我们使用一个临时数组$tmp$来存放排好序的元素。$i$、$j$、$k$分别表示左子数组、右子数组和临时数组的指针，$count$表示逆序对的数量。当左子数组的元素$x$大于右子数组的元素$y$时，$count$就会加上左子数组剩余的元素个数($mid-i+1$)，也就是$x$后面的元素都与$y$构成逆序对。
总结
本文介绍了两种解决计算大小为三的逆序对数量的算法。第一种算法是朴素算法，它的时间复杂度为O(n^3)。第二种算法基于归并排序，它的时间复杂度为O(nlogn)，效率比朴素算法高得多。这两种算法都是解决逆序对问题的经典算法，在实际中也广泛应用于其他问题的解决。