逆序
成员为数的数组的一个逆序(inversion)即具有行至i < j 但 a[i] > a[j] 的序偶(odered pair) (a[i], a[j])。
排序
初始数组的逆序，是基于交换相邻元素的排序的交换次数。
因为交换两个逆序的相邻元素恰好消除一个逆序，而一个排过序的数组没有逆序。
定理
假设不存在重复元素：
定理1
N 个互异元素的数组的平均逆序数是N(N-1)/4
定理 2
通过交换相邻元素进行排序的任何算法平均都需要Ω(N2)时间。
基于交换相邻元素的排序算法
这里交换相邻元素的排序算法指每次交换只消除一个逆序的排序算法，如插入排序、冒泡排序、选择排序等
参考文献
【1】Weiss M A. Data structures & algorithm analysis in C++[M]. Pearson Education, 2012.
