逆序对

维基百科,自由的百科全书
跳转至: 导航搜索

设 A 为一个有 n 个数字有序集 (n>1),其中所有数字各不相同。

如果存在正整數 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j],則 <A[i], A[j]> 這一個有序對稱為 A 的一個逆序對,也称作逆序数。

例如:数组 <2,3,8,6,1> 的逆序对为:<2,1> <3,1> <8,6> <8,1> <6,1> 共5个逆序对。

对于<2,1>:1 ≤ 1 < 5 ≤ 5 ,A[1] > A[5],所以<A[1],A[5]>为一个合法的逆序对。

目前求逆序对数目比较普遍的方法是利用归并排序做到O(n \log n)的时间复杂度。 当然,也可以利用树状数组、线段树来实现这种基础功能。复杂度均为O(n \log n)