冒泡排序的對換次數(shù)與排列逆序數(shù)相等的證明

李均成

【摘要】以代數(shù)的方法證明冒泡排序過程中元素的對換次數(shù)就是排列的逆序數(shù).

【關(guān)鍵詞】冒泡排序;對換次數(shù);排列;逆序數(shù)

證明：不失一般性地，以由若干自然數(shù)作元素的全排列為例，規(guī)定從左到右由小到大為標(biāo)準(zhǔn)次序.

對相鄰元素的對換，考慮如下排列：

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

記此排列的逆序數(shù)為T1.為使a，b兩元素具備對換條件，設(shè)a>b，并且m1，m2，…，mi已按冒泡排序的規(guī)則排為標(biāo)準(zhǔn)次序.繼此對a，b兩元素比較大小并對換，排列變?yōu)?/p>

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

記此排列的逆序數(shù)為T2.對換后，元素m1，m2，…，mi，mj，…，mn的逆序數(shù)不變，元素a的逆序數(shù)也不變，元素b的逆序數(shù)減1.因此，對換后，排列（2）中各元素的逆序數(shù)之和（即排列（2）的逆序數(shù)）為T2=T1-1，

即a，b兩相鄰元素對換后，排列的逆序數(shù)減1.

對非相鄰元素的對換，考慮如下排列：

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

記此排列的逆序數(shù)為T3.為使a，b兩元素具備直接對換的條件，設(shè)b

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

記此排列的逆序數(shù)為T4.對換后，元素m1，m2，…，mn的逆序數(shù)不變.元素b的逆序數(shù)減小n+1，元素a的逆序數(shù)增大n.因此，對換后，排列（4）中各元素的逆序數(shù)和（即排列（4）的逆序數(shù)）為：T4=T3-1，

即a，b兩非相鄰元素對換后，排列的逆序數(shù)減1.若a，b兩端還存在其他元素（其中，a左端的元素次序已對換為標(biāo)準(zhǔn)次序），顯然，a，b兩元素的對換于這些元素的逆序數(shù)都不產(chǎn)生影響.所以，上述結(jié)論仍然成立.

總之，對排列中的兩個元素a，b，不論a，b相鄰與否，以及a，b兩端是否還存在其他元素（即不論a，b處于排列中的什么位置），只要它們按冒泡排序的對換條件發(fā)生一次對換，它們所在排列的逆序數(shù)就減小1.從而冒泡排序的每一次對換都將排列的逆序數(shù)減小1，直到該排列的逆序數(shù)降為0.

因此，在冒泡排序的過程中，元素相對換的次數(shù)就是該排列的逆序數(shù).證畢.

【參考文獻(xiàn)】

[1]同濟(jì)大學(xué)數(shù)學(xué)系.工程數(shù)學(xué)·線性代數(shù)（第五版）[M].北京：高等教育出版社，2007，5（5）：4-5，8-9.