逆序对，数学术语，设 A 为一个有 n 个数字的有序集 (n＞1)，其中所有数字各不相同。

对于一个包含N个非负整数的数组A[1..n]，如果有i < j，且A[ i ]>A[ j ]，则称(A[ i] ,A[ j] )为数组A中的一个逆序对。

例如，数组（3，1，4，5，2）的逆序对有(3,1),(3,2),(4,2),(5,2)，共4个。

问题描述

给定一个数组，求该数组中包含多少个逆序对。

求解方法

方法一：最原始的方法，利用两重循环进行枚举。该算法的时间复杂度为O(n^2)。

C++代码如下：

Pascal代码如下：

方法二：利用归并排序的思想求解逆序对的个数，这是解决该问题的一种较为高效的算法。该算法的时间复杂度为O(nlogn)。

C++代码如下：

Pascal代码如下：

方法三：利用树状数组求逆序对，开始先将序列离散化以提高算法的时空效率，然后从序列的最左端开始建立树状数组，每创建一个就执行一次 i - getsum( x ) (x 为离散化的 值) 累加到ans上。最后的 ans即为所求的答案。注意在进行排序的时候如果两个数组的值相等, 则需要确保排序后原先的相对顺序不发生改变, 即确保使用稳定的排序方式。

该算法的时间复杂度为O(nlogn)。

C++代码如下：