- 对于下标
i<j，如果A[i]>A[j]，则称(i,j)是一对逆序对 (inversion) 。
- 例：序列中有多少逆序对？冒泡和插入排序分别需要交换元素多少次？ 一共9对； 冒泡和插入排序都需要交换9次。
- 交换2个相邻元素正好消去1个逆序对！
- 设序列中共有对逆序对，则对于插入排序的时间复杂度：
- 可以看出， 插入排序的时间复杂度和逆序对数是线性关系； ——也就是说，如果序列基本有序(逆序对数和元素个数是一个数量级，甚至更小)，那么插入排序简单且高效。
定理1：任意个不同元素组成的序列平均具有个逆序对。
定理2：任何仅以交换相邻两元素来排序的算法，其平均时间复杂度为。
- 这意味着：要提高算法效率，我们必须： 每次消去不止1个逆序对每次交换相隔较远的2个元素