冒泡排序算法及其改進算法的實驗分析

淦 艷 楊 有 余 平

（重慶師范大學計算機與信息科學學院，重慶沙坪壩 400047)

排序是計算機程序設計中的一種重要操作，它的功能是將任意序列的數據元素或記錄，重新排列成一個按關鍵字有序的序列.在計算機系統(tǒng)中，元素或記錄排序的時間占系統(tǒng)整個運行時間的比例很大；并且有序序列為記錄的查找、插入和刪除提供了方便，可以有效提高搜索效率；因此研究各類有效的排序算法一直是人們感興趣的問題，也是計算機研究中的重要課題之一.

根據排序過程中數據記錄是否被存儲在內存中，可將排序方法分為兩大類.[1]一類是內部排序，指的是待排序記錄存放在計算機內部存儲器中進行排序；另一類是外部排序，指的是待排序記錄的數量很大，以致于內存一次不能容納全部記錄，在排序過程中尚需對外存進行訪問的排序過程.而內部排序又包含插入排序、交換排序、選擇排序、歸并排序和計數排序等五類.在交換排序中，冒泡排序是其典型代表，本文將通過編程實驗，驗證和分析冒泡排序及其三種改進算法在不同隨機程度輸入序列下的性能.

為便于后續(xù)討論，做如下假設：由于鏈式存儲比數組存儲多一倍的存儲空間，因此算法中記錄均默認為按數組方式存儲，沒有特殊說明時，均認為按升序排序.

1 相關的冒泡排序算法

1.1 傳統(tǒng)冒泡排序算法

冒泡排序的基本思想是：[1]首先將第一個記錄的關鍵字和第二個記錄的關鍵字進行比較，若為逆序，則將兩個記錄交換，然后比較第二個和第三個記錄的關鍵字.依次類推，直至n-1個記錄和第n個記錄的關鍵字進行過比較為止.上述過程稱為第一次排序，其結果是讓最大的記錄被安置到最后一個記錄的位置上.然后再進行下一次排序，直至整個序列有序為止.冒泡排序算法用C語言描述如下：

template＜class Type＞

1.2 帶標記的冒泡排序

帶標記的冒泡排序算法基本思想是：[2]在冒泡排序過程中，只要在某一次排序過程中發(fā)現沒有進行記錄的交換，則說明該組記錄已經有序，此時應該退出循環(huán)，即排序完成.帶標記的冒泡排序算法用C語言描述如下：

1.3 雙向冒泡排序

雙向冒泡排序算法基本思想是：[2,3]在傳統(tǒng)的冒泡排序排序方法中，每次只能確定一個位置上的記錄，如果一次能夠確定兩個位置上的記錄，則會使排序所需次數減少，即在一端冒泡的同時在另一端也進行反向冒泡.用C語言描述如下：

1.4 交替排序法

交替排序法是冒泡排序的變異.其基本思想是：[4]假設記錄序列為R[ i](0 i n 1)≤ ≤ - ，首先將數據交換標志p置0，將R[1]與R[2]、R[3]與R[4]等兩兩相比較，如果逆序，則交換，同時將p置1；再將R[2]與R[3]、R[4]與R[5]兩兩相比較，如果逆序，則交換，同時將p置1；然后看p是否為0，若為0，就退出，即完成排序，否則繼續(xù)循環(huán).用C語言描述如下：

2 實驗與分析

為了比較各個排序算法的性能，我們使用一臺桌面電腦（AMD Sempron Dual Core Processer 2100， 1.81GHz，2.87GB的內存，Windows XP系統(tǒng)），在vs6.0環(huán)境下，用C語言編寫程序，調用隨機函數、時間函數來統(tǒng)計輸入規(guī)模不同、傳統(tǒng)冒泡排序算法及三種改進算法的耗時情況.該程序的主要功能為：產生的序列為1到100之間的隨機序列；采用數組的方式存貯隨機序列；根據不同的輸入規(guī)模，得到傳統(tǒng)冒泡排序算法及三種改進排序算法的時間耗.

首先，我們將考察四種算法隨輸入規(guī)模變化時的時間消耗.假設輸入序列在以下三種情況下產生：（1）前25%由隨機函數產生，后75%為升序序列；（2）前50%由隨機函數產生，后50%為升序序列；（3）前75%由隨機函數產生，后25%為升序序列.在這三種情況下，當輸入規(guī)模分別為1 000、2 000、4 000、8 000、10 000、20 000、40 000、80 000時，四種排序算法的時間消耗分別如表1和圖1所示.

表1 四種冒泡排序算法針對輸入規(guī)模的耗時

圖1 四種排序算法隨輸入規(guī)模的耗時曲線

由表1和圖1可知：在序列1情況下，傳統(tǒng)的冒泡排序算法不及改進的三種算法優(yōu)越，其中雙向冒泡排序為最佳，其次是交替排序，最后是帶標記冒泡.在序列2情況下，如果輸入規(guī)模小于4000，帶標記冒泡算法高于傳統(tǒng)冒泡算法，但隨輸入規(guī)模的增加，帶標記冒泡效率不及傳統(tǒng)冒泡算法；忽略個別誤差值，從整體來看雙向冒泡、交替排序算法效率高于傳統(tǒng)冒泡算法.在序列3情況下，傳統(tǒng)冒泡排序算法效率高于改進的三種排序算法，此時的改進算法已經無優(yōu)勢可言.因此，在輸入序列的隨機程度比較大的情況下，三種改進的冒泡排序算法其性能較佳；相反，隨著輸入序列隨機程度的降低，三種改進的冒泡排序算法其性能優(yōu)勢越來越弱.

其次，考慮在指定輸入規(guī)模情況下，四種算法在輸入序列隨機度變化時的時間消耗.假設輸入規(guī)模指定為10 000，四種排序算法的時間消耗如表2和圖2所示.表2中，隨機度為x，表示序列前x%是隨機序列，后(100-x)%為升序序列.當x=0時，表示序列為正序序列，當x=100時，表示序列完全隨機.

表2 四種冒泡排序算法針對隨機度的耗時

圖2 四種排序算法隨隨機度的耗時曲線

當輸入規(guī)模在10 000時，由表2和圖2可知：

（1）傳統(tǒng)冒泡排序的耗時曲線基本上呈一條水平直線，它表明輸入序列的隨機度對傳統(tǒng)冒泡排序的時間消耗影響很小，或者說傳統(tǒng)冒泡排序的時間消耗只與輸入規(guī)模有關，而與輸入序列的隨機度無關；相反，另外三種算法的耗時曲線基本上呈相同斜率的直線，它表明這三種算法的時間消耗隨輸入序列隨機度的增大而增加，同時這三種算法對應耗時增加的速度基本相同.

（2）傳統(tǒng)冒泡排序的耗時曲線與其它三條曲線都有相交點，在某相交點的左邊，傳統(tǒng)冒泡排序的耗時高于相比較的算法，而在相交點的右邊，則相比較算法的耗時高于傳統(tǒng)算法.比如，傳統(tǒng)冒泡排序算法和交替冒泡排序算法在隨機度為 55時相交，它表明當輸入序列的隨機度小于 55時，交替冒泡排序算法的耗時較小，性能優(yōu)于傳統(tǒng)排序，否則，當隨機度進一步增大時，其性能還不如傳統(tǒng)排序.

（3）在改進的三種冒泡排序算法中，如果將其對應曲線視為斜線，則對應的截距不同.雙向冒泡、交替排序和帶標記的冒泡排序對應的橫截距從大到小變化，它表明這三種算法對輸入序列隨機度的敏感性從小變大.此即：在相同耗時情況下，雙向冒泡排序算法可以容忍更大程度的隨機度；在相同隨機度的情況下，雙向冒泡排序算法的耗時最少.

3 總 結

通過對傳統(tǒng)的、帶標記的、雙向的和交替排序四種冒泡排序算法的概述及改進算法的實驗分析可以得出：

首先，用文字和C語言描述冒泡排序及其三種改進算法的基本思想，分析和總結出它們的平均時間復雜度為O(n2)，空間復雜度為O(1).

其次，驗證了輸入不同隨機程度的序列時，四種排序算法的性能存在差異.當輸入序列前25%隨機后75%升序時，帶標記冒泡、雙向冒泡、交替排序算法效率均高于傳統(tǒng)冒泡排序算法，且雙向冒泡排序耗時最少；當輸入序列前50%隨機后50%升序時，雙向冒泡排序和交替排序算法效率高于傳統(tǒng)冒泡排序算法；當輸入序列前75%隨機后25%升序時，改進的三種算法效率不及傳統(tǒng)冒泡排序，此時則應選擇傳統(tǒng)冒泡排序算法.然后，由實驗數據表明四種算法的時間消耗與輸入序列的規(guī)模近似地呈指數曲線關系.

最后，驗證了輸入規(guī)模均為10 000，不同隨機程度下，四種算法的性能由圖2觀察可知：實驗說明輸入序列的隨機度對傳統(tǒng)冒泡排序的時間消耗影響很小，或者說傳統(tǒng)冒泡排序的時間消耗只與輸入規(guī)模有關，而與輸入序列的隨機度無關；雙向冒泡、交替排序和帶標記的冒泡排序算法的耗時曲線基本上呈相同斜率的直線，它表明這三種算法的時間消耗隨輸入序列隨機度的增大而增加，同時這三種算法對應耗時增加的速度基本相同.另外傳統(tǒng)冒泡排序的耗時曲線與其它三條曲線都有相交點，在某相交點的左邊，傳統(tǒng)冒泡排序的耗時高于相比較的算法，而在相交點的右邊，則相比較算法的耗時高于傳統(tǒng)算法.除此之外，如果改進三種算法對應的曲線視為直線，則對應直線的傾斜度為 40?左右，且截距不同.這說明輸入序列隨機度的敏感性存在差異，即雙向冒泡、交替排序和帶標記的冒泡排序的敏感性從小到大.因此，將輸入規(guī)模、隨機程度等因素考慮到實際應用中，會提高算法效率，節(jié)省排序時間.

[1]嚴蔚敏，吳偉民.數據結構[M].北京:清華大學出版社，1997.

[2]周秋芬.冒泡排序算法及其改進[J].新鄉(xiāng)教育學院學報，2009（3）:160-161.

[3]楊義磊.冒泡排序的分析改進算法[EB/OL].中國科技論文在線，http://www.paper.edu.cn.

[4]王愛松，張景龍.冒泡排序法的變異——交替排序法[J].內蒙古民族大學學報，2009（2）:21.