逆序对

设A为一个有n个数字的有序集（n>1），其中所有数字各不相同。 如果存在正整數i, j使得1 ≤ i ＜ j ≤ n而且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]，所以为一个合法的逆序对。 目前求逆序对数目比较普遍的方法是利用归并排序做到的时间复杂度。 当然，也可以利用树状数组、线段树来实现这种基础功能。复杂度均为。