淦 艷 楊 有 余 平

（重慶師范大學(xué)計(jì)算機(jī)與信息科學(xué)學(xué)院，重慶沙坪壩 400047)

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

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

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

1 相關(guān)的冒泡排序算法

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

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

template＜class Type＞

1.2 帶標(biāo)記的冒泡排序

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

1.3 雙向冒泡排序

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

1.4 交替排序法

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

2 實(shí)驗(yàn)與分析

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

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

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

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

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

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

表2 四種冒泡排序算法針對(duì)隨機(jī)度的耗時(shí)

圖2 四種排序算法隨隨機(jī)度的耗時(shí)曲線

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

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

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

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

3 總 結(jié)

通過對(duì)傳統(tǒng)的、帶標(biāo)記的、雙向的和交替排序四種冒泡排序算法的概述及改進(jìn)算法的實(shí)驗(yàn)分析可以得出：

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

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

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

[1]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社，1997.

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

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

[4]王愛松，張景龍.冒泡排序法的變異——交替排序法[J].內(nèi)蒙古民族大學(xué)學(xué)報(bào)，2009（2）:21.