逆序对

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

设 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个。

目前求逆序对数目比较普遍的方法是利用归并排序做到O(n \log n)的时间复杂度。