逆序對

設 A 為一個有 n 個數字的有序集 (n>1)，其中所有數字各不相同。 如果存在正整數 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，則 這個有序對稱為 A 的一個逆序對，也稱作逆序數。

定義

對於一個包含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代碼如下：