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

李均成

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

【關鍵詞】冒泡排序;對換次數;排列;逆序數

證明：不失一般性地，以由若干自然數作元素的全排列為例，規定從左到右由小到大為標準次序.

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

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.