冒泡排序的对换次数与排列逆序数相等的证明

李均成

【摘要】以代数的方法证明冒泡排序过程中元素的对换次数就是排列的逆序数.

【关键词】冒泡排序;对换次数;排列;逆序数

证明：不失一般性地，以由若干自然数作元素的全排列为例，规定从左到右由小到大为标准次序.

对相邻元素的对换，考虑如下排列：

m1，m2，…，mi，a，b，mj，…，mn.（1）

记此排列的逆序数为T1.为使a，b两元素具备对换条件，设a>b，并且m1，m2，…，mi已按冒泡排序的规则排为标准次序.继此对a，b两元素比较大小并对换，排列变为

m1，m2，…，mi，b，a，mj，…，mn.（2）

记此排列的逆序数为T2.对换后，元素m1，m2，…，mi，mj，…，mn的逆序数不变，元素a的逆序数也不变，元素b的逆序数减1.因此，对换后，排列（2）中各元素的逆序数之和（即排列（2）的逆序数）为T2=T1-1，

即a，b两相邻元素对换后，排列的逆序数减1.

对非相邻元素的对换，考虑如下排列：

a，m1，m2，…，mn，b.（3）

记此排列的逆序数为T3.为使a，b两元素具备直接对换的条件，设b

b，m1，m2，…，mn，a.（4）

记此排列的逆序数为T4.对换后，元素m1，m2，…，mn的逆序数不变.元素b的逆序数减小n+1，元素a的逆序数增大n.因此，对换后，排列（4）中各元素的逆序数和（即排列（4）的逆序数）为：T4=T3-1，

即a，b两非相邻元素对换后，排列的逆序数减1.若a，b两端还存在其他元素（其中，a左端的元素次序已对换为标准次序），显然，a，b两元素的对换于这些元素的逆序数都不产生影响.所以，上述结论仍然成立.

总之，对排列中的两个元素a，b，不论a，b相邻与否，以及a，b两端是否还存在其他元素（即不论a，b处于排列中的什么位置），只要它们按冒泡排序的对换条件发生一次对换，它们所在排列的逆序數就减小1.从而冒泡排序的每一次对换都将排列的逆序数减小1，直到该排列的逆序数降为0.

因此，在冒泡排序的过程中，元素相对换的次数就是该排列的逆序数.证毕.

【参考文献】

[1]同济大学数学系.工程数学·线性代数（第五版）[M].北京：高等教育出版社，2007，5（5）：4-5，8-9.