一種改進的雞尾酒排序算法

張 凡，殷 鋒，苗瀟文，張細凱

(西南民族大學(xué)計算機科學(xué)與技術(shù)學(xué)院，計算機系統(tǒng)國家民委重點實驗室， 四川成都 610041)

雞尾酒排序算法是一種基于雙向遍歷的冒泡排序改進算法，具有冒泡排序算法的穩(wěn)定性[1]. 該算法通過對序列進行雙向遍歷排序，有效地縮小了數(shù)據(jù)比較區(qū)間，在一定程度上提高了冒泡算法的排序效率，但算法仍存在大量重復(fù)的數(shù)據(jù)比較、對初始輸入序列的數(shù)據(jù)隨機度過敏感以及比較區(qū)間收縮不徹底等問題[2-3].對于該算法的改進思想主要是縮小數(shù)據(jù)比較區(qū)間以及減少重復(fù)的數(shù)據(jù)比較，改進方法主要有通過標(biāo)記是否發(fā)生數(shù)據(jù)交換來降低數(shù)據(jù)的重復(fù)比較，跳過有序數(shù)據(jù)單元來縮小數(shù)據(jù)比較區(qū)間[4-6].通過上述方法改進的雞尾酒排序算法的排序效率雖有所提高，但仍存在大量冗余重復(fù)的數(shù)據(jù)比較，數(shù)據(jù)比較區(qū)間也存在進一步收縮的可能性.

本文提出的T -CCS 算法利用標(biāo)記數(shù)據(jù)交換位進行分段式逆向遍歷排序，在正向遍歷比較過程中以發(fā)生數(shù)據(jù)交換為條件，標(biāo)記發(fā)生數(shù)據(jù)交換位置的同時開始分段逆向遍歷排序，直到不發(fā)生數(shù)據(jù)交換條件時跳回標(biāo)記位繼續(xù)正向遍歷，直到再次發(fā)生數(shù)據(jù)交換時更新標(biāo)記位并重復(fù)上述過程直到所有排序完成，有效的縮小了正向遍歷和逆向遍歷的數(shù)據(jù)比較區(qū)間，同時由于將逆向遍歷比較進行了分段處理，保證了在標(biāo)記位前的數(shù)據(jù)為有序序列，進一步減少了重復(fù)的數(shù)據(jù)比較.

圖1 兩種算法排序效率比較Fig.1 Comparison of the sorting efficiency of the two algorithms

雞尾酒排序算法作為一種改進的冒泡排序算法，在某些條件下，可以大量的減少待排序列數(shù)據(jù)間的比較次數(shù)，有效的提高冒泡算法的排序效率[10]，但是其仍存在以下缺陷:

首先，根據(jù)雞尾酒排序算法排序的流程圖可知，它每次進行正向或者逆向排序時均帶著一個特定的“目標(biāo)”，即完成該次排序后應(yīng)該將某個數(shù)據(jù)放置某個特定的位置.例如第一次正向遍歷排序的目標(biāo)便是找出最大值放到數(shù)組的最后一位，第一次逆向遍歷排序的目標(biāo)則是找到最小值放到數(shù)組的第一位，這種帶著“目標(biāo)”進行排序的方式，忽略了排序過程出現(xiàn)的多次重復(fù)的數(shù)據(jù)比較，降低了排序效率；其次，輸入待排序列中可能存在一些存儲在連續(xù)單元里的有序數(shù)據(jù)，該

1 雞尾酒排序算法

雞尾酒排序算法又稱來回漣漪排序算法，它是為減少待排序列數(shù)據(jù)之間的比較輪次而衍生出來的一種改進型的冒泡算法[7]，相較于傳統(tǒng)的冒泡排序算法[8-9]的排序效率有一定的提升(如圖1 所示).其主要思想是假設(shè)待排的n個數(shù)據(jù)存儲于一維數(shù)組N中，在第一次正向遍歷中依次進行冒泡排序操作，找出最大值置于數(shù)組的最后一位N[last]，縮小比較區(qū)間為N[0]到N[n-1]并從N[last-1]處開始逆向遍歷依次進行冒泡排序操作并找出最小值置于數(shù)組的第一位N[begin]，此時縮減比較區(qū)間N[1]到N[n-1]，再次進行正向遍歷排序.重復(fù)上述過程直到不再發(fā)生數(shù)據(jù)交換時，排序結(jié)束.其排序流程如圖2 所示.算法仍會對這些數(shù)據(jù)進行多次重復(fù)比較[11]，使得數(shù)據(jù)比較區(qū)間收縮不夠徹底，仍有優(yōu)化的空間[12]，尤其是當(dāng)輸入待排序列的數(shù)據(jù)規(guī)模較大時，每次全序列遍歷比較都會消耗大量的時間[13-14]；最后，該算法的排序效率受到初始輸入待排序列的數(shù)據(jù)隨機度影響[15]，在某些情況下其排序效率會迅速降低.

圖2 雞尾酒算法排序流程圖Fig.2 Cocktail algorithm sorting flow map

2 改進的雞尾酒排序算法

針對上述中雞尾酒排序算法存在的缺陷，本文提出了一種分段式逆向遍歷排序的雞尾酒排序算法.該算法的主要思想是在排序的正向遍歷排序過程中，如果在x處數(shù)據(jù)間發(fā)生了位置交換，則立即從x處開始進行逆向遍歷排序，同時標(biāo)記位置x，直到不出現(xiàn)數(shù)據(jù)交換而結(jié)束逆向遍歷排序，返回標(biāo)記位置x繼續(xù)未完成的正向遍歷排序并重復(fù)執(zhí)行上述操作直到不再出現(xiàn)數(shù)據(jù)交換.這樣就保證了在標(biāo)記位x之前的序列均為有序序列，從而有效地縮小了后續(xù)遍歷時的數(shù)據(jù)比較區(qū)間.由于進入逆向遍歷排序的條件是當(dāng)排序過程出現(xiàn)了數(shù)據(jù)交換，因此只要滿足該條件，便會一直進行逆向遍歷排序，直到不再發(fā)生數(shù)據(jù)交換，即逆向遍歷排序條件不成立時結(jié)束逆向遍歷排序返回標(biāo)記點繼續(xù)正向遍歷排序.這種排序方式將進行多次局部的逆向排序操作，而理論上只需要進行一次完整的正向遍歷便可完成整個序列的排序. 本文的算法描述如下:

為了更直觀的描述T -CCS 的排序過程，現(xiàn)給出一個按索引值排序的隨機序列a，其使用T -CCS 排序的過程圖如圖3 所示.

圖3 T-CCS 對序列a 進行排序的過程Fig.3 T-CCS sorting map diagram for sequence a

第一步:在對序列a 進行正向遍歷排序時，a[6]與a[2]發(fā)生了位置交換，觸發(fā)第一次逆向遍歷排序，同時在a[2]處設(shè)置標(biāo)記位F1.

第二步:第一次逆向排序中，a[2]與a[4]滿足數(shù)據(jù)位置交換條件，發(fā)生了數(shù)據(jù)位置交換，滿足繼續(xù)逆向遍歷排序的條件，因此比較a[2]與a[1]，由于a[2]＞a[1]，未發(fā)生數(shù)據(jù)位置交換，不滿足繼續(xù)逆向排序的條件，隨即停止第一次逆向排序，從F1處繼續(xù)未完成的正向遍歷排序.

第三步:a[6]與a[5]發(fā)生交換，觸發(fā)第二次逆向遍歷排序，同時在a[5]處更新標(biāo)記位為F2.

第四步:由于a[5]＞a[4]，未發(fā)生位置交換，不滿足繼續(xù)逆向遍歷排序的條件，因此停止第二次逆向遍歷排序，從F2處繼續(xù)未完成的正向遍歷排序.

第五步:a[6]與a[3]發(fā)生位置交換，觸發(fā)第三次逆向遍歷排序，同時在a[3]處更新標(biāo)記位為F3.

第六步:a[3]與a[5]發(fā)生位置交換，滿足逆向遍歷排序的條件，繼續(xù)第三次逆向遍歷排序.

第七步:a[3]與a[4]發(fā)生位置交換，仍滿足逆向遍歷排序的條件，繼續(xù)第三次逆向遍歷排序.

第八步:a[3]＜a[2]，不滿足繼續(xù)逆向遍歷排序的條件，返回F3處繼續(xù)未完成的正向遍歷排序.

第九步:a[5]與a[6]未發(fā)生位置交換，且正向遍歷排序結(jié)束，完成排序.

3 實驗與分析

在了解T-CCS 算法的原理后，將通過實驗進一步對T-CCS 的排序效率進行分析. 無論是T -CCS還是雞尾酒排序算法，都沒有跳出二層嵌套循環(huán)這一雙向排序算法所必要的條件，因此算法的時間復(fù)雜度并未發(fā)生改變.但T -CCS 通過減少重復(fù)的數(shù)據(jù)比較和逐次縮短比較區(qū)間，降低了算法的空間復(fù)雜度，有效的提高雞尾酒算法的排序效率.

為了比較本文算法與雞尾酒排序算法以及常見改進算法的排序效率，引入不同規(guī)模相同隨機度的隨機序列，通過對已有實驗數(shù)據(jù)的擬合預(yù)測，得到大規(guī)模輸入數(shù)據(jù)下各算法的耗時情況.四種算法關(guān)于輸入序列數(shù)據(jù)規(guī)模的耗時表現(xiàn)分別為表1 和圖4 所示.

表1 四種排序算法關(guān)于輸入規(guī)模的耗時(單位：秒)Table 1 Time-consuming (in seconds) for four sorting algorithms on input scale

由表1 和圖4 可知，隨著輸入序列的數(shù)據(jù)規(guī)模不斷增大，傳統(tǒng)的冒泡算法和帶標(biāo)記的冒泡算法在排序耗時上趨于相同，與雞尾酒排序算法的執(zhí)行效率差距逐漸增大，而T -CCS 算法在對大規(guī)模數(shù)據(jù)序列的排序耗時遠遠低于其他三種算法，且當(dāng)數(shù)據(jù)規(guī)模增大時T-CCS 的效率優(yōu)勢越發(fā)明顯.總體來說，T -CCS 算法比傳統(tǒng)的冒泡排序算法的排序效率提高26% 左右，比雞尾酒排序算法的排序效率提高20%左右，且這種提升不會因為輸入序列的數(shù)據(jù)規(guī)模增大而產(chǎn)生震蕩，是一種穩(wěn)定的效率提升.

圖4 四種排序算法關(guān)于輸入規(guī)模的耗時趨勢圖Fig.4 Time-consuming trend map of four sorting algorithms on input scale

圖5 四種排序算法關(guān)于序列隨機度的耗時趨勢圖(數(shù)據(jù)規(guī)模：100 000)Fig.5 Time-consuming trend map of four sorting algorithms on sequence randomness (data size：100 000)

為了比較四種算法在對相同規(guī)模不同隨機度輸入序列的排序中的表現(xiàn)，引入隨機度x來衡量輸入序列的數(shù)據(jù)有序程度，x的值表示輸入序列中無序序列所占的比例.當(dāng)x為0 時，數(shù)據(jù)的隨機度為0，表示輸入序列為順序序列；當(dāng)x為1 時，數(shù)據(jù)的隨機度為1，表示輸入序列為倒序序列.當(dāng)指定輸入序列的數(shù)據(jù)規(guī)模為100 000 時得出四種算法關(guān)于輸入序列隨機度的表現(xiàn)如表2，圖5 所示.

表2 四種冒泡排序算法關(guān)于數(shù)據(jù)隨機度的耗時(單位：秒)Table 2 Time spent by four bubble sorting algorithms on data randomness (in seconds)

由表2 和圖5 可知，在同等規(guī)模的輸入數(shù)據(jù)下，傳統(tǒng)的冒泡排序算法因其獨特的排序原理，它的排序效率受序列隨機度的影響較小；當(dāng)序列隨機度在[0，0.6]區(qū)間時，帶標(biāo)記的冒泡排序算法的排序效率要高于傳統(tǒng)的冒泡排序算法，而當(dāng)序列隨機度在[0.8，1]區(qū)間時，其表現(xiàn)反而不如傳統(tǒng)的冒泡排序算法，因此該算法更適合低隨機度的序列的排序處理

傳統(tǒng)的雞尾酒算法與T -CCS 算法的效率均受到數(shù)據(jù)隨機度的影響，其中雞尾酒排序算法受到的影響近乎為線性的影響，當(dāng)序列隨機度在[0 -0.2]區(qū)間時，T-CCS 算法對序列隨機度的敏感度與傳統(tǒng)的冒泡排序相差無幾；當(dāng)序列的隨機度在[0，0.4]區(qū)間時，T-CCS 算法對序列隨機度的敏感度低于傳統(tǒng)的雞尾酒算法，當(dāng)序列的隨機度在[0.4，1]區(qū)間時，兩種算法對序列隨機度的敏感度基本相同，但是在相同的序列隨機度下T -CCS 算法相比于傳統(tǒng)的雞尾酒算法有著更高的執(zhí)行效率.

4 總結(jié)

數(shù)據(jù)的排序是計算機科學(xué)中某些研究問題的前提和基礎(chǔ).與傳統(tǒng)的冒泡排序相比，雞尾酒排序算法的效率有一定程度的提高，但仍存在改進的可能，該算法在排序過程中存在的重復(fù)冗余數(shù)據(jù)比較和比較區(qū)間收縮不徹底等問題仍然是改進的方向，. 針對上述問題，本文根據(jù)雙向排序的相關(guān)理論，對雞尾酒排序算法做出了一定改進并進行實驗分析.實驗結(jié)果證明，本文提出的T -CCS 算法在大規(guī)模數(shù)據(jù)排序效率以及對輸入序列數(shù)據(jù)隨機度的敏感度等方面都取得了較好的效果.