这一篇博文我们将讨论一些与排序算法有关的定理，这些定理将解释插入排序博文中提出的疑问（为什么冒泡排序与插入排序总是执行同样数量的交换操作，而选择排序不一定），同时为讲述高级排序算法做铺垫（高级排序为什么会更快）。
在讨论相关定理之前，我们必须先掌握一个与顺序有关的概念：逆序数。
所谓逆序数，就是“逆序组合的个数”，假设我们希望的顺序为从小到大（反之同理）：
设有元素互异数列X0,X1,X2……Xn-1，（元素互异即数列中任取两数均不相等）从中任取两数作为组合（Xa,Xb），若a<b（即Xa在数列中位于Xb之前）且Xa>Xb，则（Xa,Xb）逆序，若a<b且Xa<Xb，则（Xa,Xb）不是逆序。整个数列的逆序数即数列中所有逆序组合（Xa,Xb）的个数。（不难发现，若数列有n个数，则任取两数的组合（Xa,Xb）共有n(n-1)/2个，n为元素个数。）
下面我们来举几个计算逆序数的例子（依然假设我们希望的顺序为从小到大）：
1.设有数列1,2,3,4,5，因为从中任取两数（Xa,Xb）且a<b，均有Xa<Xb，即任一组合（Xa,Xb）均非逆序，所以数列1,2,3,4,5的逆序数为：逆序组合的个数=0
2.设有数列5,4,3,2,1，因为从中任取两数（Xa,Xb）且a<b，均有Xa>Xb，即任一组合（Xa,Xb）均为逆序，所以数列1,2,3,4,5的逆序数为：逆序组合的个数=n(n-1)/2=5*4/2=10
2.设有数列2,3,4,5,1，从中任取两数（Xa,Xb），a<b且Xa>Xb的组合有（2,1）,（3,1），（4,1），（5,1）共4个，即逆序组合共4个，所以数列2,3,4,5,1的逆序数为：逆序组合的个数=4
从例1我们可以推出定理1：若数列为有序，则其逆序数为0。例1的计算过程即本定理的证明。
而从定理1我们又可以得出定理2：若数列非有序，则其逆序数必大于0。证明过程类似于定理1，略
从定理1和定理2我们又可以得出定理3：将数列从非有序转换为有序（即排序）的过程，就是减少数列逆序数的过程。
明白了什么是逆序数，以及排序算法的“本质”之后，我们开始讨论定理4：
设有元素互异数列X0,X1,X2……Xn-1，其反数列为Xn-1,Xn-2,……X0，则这两个数列的逆序数之和必为n*(n-1)/2
因为数列元素互异，所以任取两数Xa,Xb且a<b，要么Xa>Xb，要么Xa<Xb。也就是说组合（Xa,Xb）若在原数列中非逆序，则必在反数列中逆序，反之则反。而元素个数为n的数列中组合（Xa,Xb）的个数共为n*(n-1)/2个，任一组合要么在原数列逆序，要么在反数列逆序，所以原数列与反数列的逆序数之和即组合（Xa,Xb）的个数：n*(n-1)/2
有了定理4，我们就可以给出定理5：
有n个互异元素的数列，其平均逆序数为n*(n-1)/4
从定理4可知，给定的数列与其反数列的逆序数之和为n*(n-1)/2，所以该数列的平均逆序数即两者之和的一半n*(n-1)/2。
接下来是简单的定理6：
对于元素互异数列，交换其中相邻的两个数Xn,Xn+1的位置，则数列的逆序数要么+1，要么-1。
假设（Xn,Xn+1）为逆序，则交换两者将使该组合变为非逆序，但不会影响其他组合如（Xa,Xn）（Xn,Xb）的顺序，从而数列逆序数-1
假设（Xn,Xn+1）为非逆序，则交换两者将使该组合变为逆序，但不会影响其他组合如（Xa,Xn）（Xn,Xb）的顺序，从而数列逆序数+1
根据
定理3：将数列从非有序转换为有序（即排序）的过程，就是减少数列逆序数直至0的过程。
定理5：有n个互异元素的数列，其平均逆序数为n*(n-1)/4
定理6：对于元素互异数列，交换其中相邻的两个数Xn,Xn+1的位置，则数列的逆序数要么+1，要么-1。
我们可以得出定理7：
通过交换相邻元素来完成排序的算法，其平均时间复杂度为Ω（n2）
对于n元素互异的数列，其平均逆序数为n*(n-1)/4，而排序即减少逆序数至0的过程，因为交换相邻元素最多使逆序数-1，所以必须有n*(n-1)/4次交换才能使数列逆序数为0，即交换相邻元素的排序算法平均需要执行n*(n-1)/4次交换操作，也就是说平均时间复杂度为Ω(n*(n-1)/4)，即Ω(n2)。虽然我们一直强调元素互异看起来有所不妥，但排序算法必然要可以处理元素互异情况，而且Ω(n)也只是平均时间复杂度，没有考虑任何具体情形。
至此，本篇博文对于排序算法的定理就算是介绍完毕了。但有关排序算法的分析尚未结束。
我们先来回答插入排序博文中的问题：为什么冒泡排序和插入排序执行的交换操作总是一样多。其原因如下：
这两个算法都是通过交换相邻元素来排序的，而且它们都不会执行使数列逆序数+1的交换，也就是说它们每执行一次交换就会且只会使数列的逆序数-1。所以对于给定数列，若其逆序数为n，则两者都将执行n次交换操作。
那么，选择排序有时候只需要更少的交换次数的原因也就出来了，因为选择排序并不是通过交换相邻元素来排序的算法，比如数列5,4,3,2,1，选择排序第一次“实质交换”后，数列变为了1,4,3,2,5，也就是说它这一次交换就使得数列的逆序数-7。所以选择排序可以使用更少的“实质交换”来完成排序，当然这并不意味着选择排序就会很快，原因不再赘述。
接下来，根据前面的定理（3、5、6）。我们可以推出本文最后一个定理，也就是定理7的推理，也是所有高级排序算法的根本：
要令排序算法的时间复杂度低于O(n2)，必须令算法执行“远距离的元素交换”，使得平均每次交换减少不止1逆序数。
下一篇博文我们将讨论希尔排序，它是插入排序的升级版，升级之处显然就是“令元素远距离的交换”，而且升级的思想非常直白，具体的实现我们将在下一篇博文介绍。