【剑指Offer刷题小记】数组中的逆序对（JAVA版）

题目描述：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007.

问题分析：

（1）题目拿到手应该就能想到一个最简单的暴力算法，对数组中的每个数进行遍历，比较该数和后面的数的大小从而计算逆序对。很显然，这种方法虽然简单，但明显需要大量的时间，暴力算法的时间复杂度达到了O(n²)。

（2）此题暴力算法明显不可取，因此来对数组进行分析看能找出什么规律。以数组[6，3，2，4]来分析，该数组的逆序对数为4。我们可以画图分析，当把数组分成两个部分时，如果计算出每个部分的逆序对数，然后再计算出左边数组相对于右边数组的逆序对数，相加就是整个数组的总逆序对数了。因此可以利用排序算法中的归并算法，对数组进行拆分，递归计算每个子数组的逆序对数，最后相加的总和即为逆序对的总数。

可以构建一个临时数组，用来把每次计算完逆序对的子数组进行排序后存入，以免重复计算。同时每个子数组计算完逆序对数后还要对1000000007取余，防止数字太大而产生的越界。

代码截图：