Question

题目：在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

例如在数组{7,5,6,4}中，一共存在5个逆序对，分别是（7,6）、（7,5）、（7,4）、（6,4）和（5,4）。

看到这个题目，我们的第一反应是顺序扫描整个数组。每扫描到一个数字的时候，逐个比较该数字和它后面的数字的大小。如果后面的数字比它小，则这两个数字就组成了一个逆序对。假设数组中含有n个数字。由于每个数字都要和O（n）个数字作比较，因此这个算法的时间复杂度是O（n²）。我们再尝试找找更快的算法。

我们以数组{7,5,6,4}为例来分析统计逆序对的过程。每次扫描到一个数字的时候，我们不能拿它和后面的每一个数字作比较，否则时间复杂度就是O（n²），因此我们可以考虑先比较两个相邻的数字。

如图5.1（a）和图5.1（b）所示，我们先把数组分解成两个长度为2的子数组，再把这两个子数组分别拆分成两个长度为1的子数组。接下来一边合并相邻的子数组，一边统计逆序对的数目。在第一对长度为1的子数组{7}、{5}中7大于5，因此（7,5）组成一个逆序对。同样在第二对长度为1的子数组{6}、{4}中也有逆序对（6,4）。由于我们已经统计了这两对子数组内部的逆序对，因此需要把这两对子数组排序（图5.1（c）所示），以免在以后的统计过程中再重复统计。

图5.1　统计数组{7,5,6,4}中逆序对的过程

注：图中省略了最后一步，即复制第二个子数组最后剩余的4到辅助数组中。（a）P1指向的数字大于P2指向的数字，表明数组中存在逆序对。P2指向的数字是第二个子数组的第二个数字，因此第二个子数组中有两个数字比7小。把逆序对数目加2，并把7复制到辅助数组，向前移动P1和P3。（b）P1指向的数字小于P2指向的数字，没有逆序对。把P2指向的数字复制到辅助数组，并向前移动P2和P3。（c）P1指向的数字大于P2指向的数字，因此存在逆序对。由于P2指向的数字是第二个子数组的第一个数字，子数组中只有一个数字比5小。把逆序对数目加1，并把5复制到辅助数组，向前移动P1和P3。

接下来我们统计两个长度为2的子数组之间的逆序对。我们在图5.2中细分图5.1（d）的合并子数组及统计逆序对的过程。

图5.2　图5.1（d）中合并两个子数组并统计逆序对的过程

我们先用两个指针分别指向两个子数组的末尾，并每次比较两个指针指向的数字。如果第一个子数组中的数字大于第二个子数组中的数字，则构成逆序对，并且逆序对的数目等于第二个子数组中剩余数字的个数（如图5.2（a）和图5.2（c）所示）。如果第一个数组中的数字小于或等于第二个数组中的数字，则不构成逆序对（如图5.2（b）所示）。每一次比较的时候，我们都把较大的数字从后往前复制到一个辅助数组中去，确保辅助数组中的数字是递增排序的。在把较大的数字复制到辅助数组之后，把对应的指针向前移动一位，接下来进行下一轮比较。

经过前面详细的讨论，我们可以总结出统计逆序对的过程：先把数组分隔成子数组，先统计出子数组内部的逆序对的数目，然后再统计出两个相邻子数组之间的逆序对的数目。在统计逆序对的过程中，还需要对数组进行排序。如果对排序算法很熟悉，我们不难发现这个排序的过程实际上就是归并排序。我们可以基于归并排序写出如下代码：

我们知道归并排序的时间复杂度是O（nlogn），比最直观的O（n²）要快，但同时归并排序需要一个长度为n的辅助数组，相当于我们用O（n）的空间消耗换来了时间效率的提升，因此这是一种用空间换时间的算法。

源代码：

本题完整的源代码详见36_InversePairs项目。

测试用例：

- 功能测试（输入未经排序的数组、递增排序的数组、递减排序的数组，输入的数组中包含重复的数字）。

- 边界值测试（输入的数组中只有两个数字、数组的数组只有一个数字）

- 特殊输入测试（表示数组的指针为NULL指针）。

本题考点：

- 考查分析复杂问题的能力。统计逆序对的过程很复杂，如何发现逆序对的规律，是应聘者解决这个题目的关键。

- 考查应聘者对归并排序的掌握程度。如果应聘者在分析统计逆序对的过程中发现问题与归并排序的相似性，并能基于归并排序形成解题思路，那通过这轮面试的几率就很高了。