逆序对

维基百科,自由的百科全书
跳转至: 导航搜索
Permutation with one of its inversions highlighted

It may be denoted by the pair or places (2, 4) or the pair of elements (5, 2).

设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,1> <8,6> <6,1>共5个逆序对。

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

目前求逆序对数目比较普遍的方法是利用归并排序做到时间复杂度

当然,也可以利用树状数组、线段树来实现这种基础功能。复杂度均为