一個新的就地穩(wěn)定歸并算法

胡圣榮

(華南農(nóng)業(yè)大學(xué) 工程學(xué)院，廣東 廣州 510642)

0 引言

在計算機(jī)科學(xué)與實踐中經(jīng)常遇到歸并問題，它是外排序的基礎(chǔ)，在內(nèi)排序中則可構(gòu)成歸并排序。另外，一些并行排序算法也經(jīng)常采用歸并的方法;在各種排序網(wǎng)絡(luò)中，基于歸并的排序網(wǎng)絡(luò)比較簡單而實用。

在經(jīng)典內(nèi)排序方法中，時間復(fù)雜性(即使最壞)為O(nlog2n)且穩(wěn)定的只有歸并排序，但它需要O(n)的輔助空間。為此很多文獻(xiàn)研究附加空間少的歸并算法，如就地歸并，其中常用的一個方法是“內(nèi)部緩存”技術(shù)［1-2］;同時為保證時間性能，還會用到一些其它技術(shù)，如鄰塊交換的旋轉(zhuǎn)算法、連續(xù)交換中的浮洞技術(shù)［2］等。不難發(fā)現(xiàn)，很多算法過于追求“就地”與“線性性能”，結(jié)果比較復(fù)雜，而線性因子也可能較大，并不適合歸并排序;還有些不再是穩(wěn)定的。較典型的有Geffert等的穩(wěn)定算法，最多m(t+1)+n/2t+o(m)次比較，5n+12m+o(m)次移動［2］，其中m≤n，t=「log2(n/m)」。這類算法中 Kim 的實現(xiàn)［3］有一定實用性，但仍很復(fù)雜。若放松嚴(yán)格的“就地”要求，允許O(log2n)的附加棧空間，如文Ellis和 Markov的ShuffleMerge算法［4］，雖不是線性的，但算法簡潔實用。Dalkilic的實現(xiàn)［5］則進(jìn)一步提高了時空性能和實用性。

本文給出一種簡便的就地歸并算法，附加空間O(1)，比較次數(shù)為理論上的最少m+n-1，但移動次數(shù)略多。

1 算法

基本思想:設(shè)初始待歸并區(qū)間為A［i，j)、B［j，to)(它們存放于同一數(shù)組R中)，對兩者從前向后掃描，設(shè)當(dāng)前位置分別為i、p，在［j，p)之間形成動態(tài)存儲區(qū)，存放之前歸并比較時前段區(qū)間的較大者，即這些元素后移形成緩沖區(qū)，它們大于或等于A區(qū)間已歸并好的部分，把它們組織成循環(huán)隊列Q，隊頭指針為f，見圖1(a)，于是:

(1)若Q［f］≤B［p］，則Q［f］出隊，放到A［i］位置，原A［i］入隊，見圖1(b)。否則，

(2)Q循環(huán)左移使隊頭位于緩沖區(qū)開始位置(以下簡稱理順操作)，B［p］移到A［i］位置，原A［i］入隊，隊長增1，見圖 1(c)。

該過程進(jìn)行中可能出現(xiàn)兩種情況:

(1)若原A區(qū)間已處理完，則把Q理順作為新的A區(qū)間，與p開始的B區(qū)間繼續(xù)歸并。

(2)若原B空間已處理完，則把Q理順，歸并結(jié)束。

按以上方法，每比較一次，必定有一個元素到位，比較次數(shù)最多m+n-1次。如果Q中不出現(xiàn)理順操作，則每個元素最多入隊、出隊1次，移動量最好O(m+n);但一般要多次理順隊列，移動量最壞O(mn)。

該過程不破壞穩(wěn)定性。歸并算法如下:

L1:while(i＜ j＆＆R［i］＜ =R［j］)i++;

L2:if(i＞=j)結(jié)束返回;

L3:交換 R［i］和 R［j］，形成初始隊列;i++;p=j+1;

L4:while(i＜j＆＆p＜to)

if(隊頭 ＜ =R［p］){隊頭出隊并置于 R［i］，原 R［i］入隊，i++;}

else{理順隊列，將 R［p］置于 R［i］，原 R［i］入隊，i++;p++;}

L5:if(p ＞ =to){理順隊列;交換 R［i，j)和隊列區(qū) R［j，p);結(jié)束返回;}

else{理順隊列;i=j;j=p;轉(zhuǎn) L1。}

其中理順隊列可通過交換隊頭的前后兩部分R［j，f)和R［f，p)來實現(xiàn)，這是相鄰塊交換，可用移動量較少的旋轉(zhuǎn)算法［2］實現(xiàn)，它交換長度為m、n的相鄰兩塊移動量為m+n+GCP(m，n)，其中GCP為求最大公約數(shù)。

圖1 歸并算法原理

2 性能分析與測試

對歸并算法的測試，通常取2個隨機(jī)序列，分別排序后再歸并，考察歸并時比較次數(shù)、移動次數(shù)等［3-6］。本文采用另一種較簡便的做法:將歸并算法用于歸并排序，考察排序的比較次數(shù)、移動次數(shù)，這是因為歸并排序要大量調(diào)用歸并過程，更易反映歸并的總體性能(文［4］也考察了歸并排序，但沒有從排序結(jié)果“折算”歸并結(jié)果，見下述)。

上述算法歸并兩個等長段時，設(shè)段長為t/2，則比較次數(shù)為O(t)，移動次數(shù)最壞O(t2);用于歸并排序時，設(shè)規(guī)模為n，則比較次數(shù)為O(nlog2n)，移動次數(shù)最壞O(n2)(參見下面歸并和歸并排序兩者復(fù)雜性的關(guān)系)。下面通過測試來考察算法的平均性能。這里取文［6］的歸并算法進(jìn)行對比(重寫代碼，以下稱算法［6］，基本思想是將后段前部的較小部分交換到前段未歸并部分之前，通過旋轉(zhuǎn)算法實現(xiàn)。可能排印瑕疵，文［6］原算法比較次數(shù)有多余)。

測試時對隨機(jī)序列進(jìn)行排序，由于C/C++系統(tǒng)隨機(jī)函數(shù)rand()范圍0～32 767，當(dāng)規(guī)模很大后出現(xiàn)重復(fù)，這里采用文［7］的長周期隨機(jī)函數(shù)，各規(guī)模下測試若干組隨機(jī)序列后平均。與文［7］不同的是，這里不通過改變種子來獲得不同序列，而是在長周期隨機(jī)序列中依次截取所需長度的子序列(通過rand()改變種子最多可生成32 767組不同隨機(jī)序列(要排除rand()=0的情形)，而本文序列組數(shù)會遠(yuǎn)大于此數(shù))。組數(shù)的多少自動調(diào)整:最多106組，以該規(guī)?？偱判驎r間不超過1分鐘為準(zhǔn)(該時間根據(jù)硬件條件設(shè)置)但最少10組。結(jié)果見表1，其中C、M、T表示關(guān)鍵字比較次數(shù)(106)、移動次數(shù)(106)、實際運(yùn)行時間(秒)，其中運(yùn)行時間包含了比較次數(shù)、移動次數(shù)的累計時間，這相當(dāng)于人為地將比較、移動操作增加了一點“延時”。

表1 歸并排序結(jié)果對比

從表1可見，在測試范圍內(nèi)，與算法［6］相比，本文比較次數(shù)相同，移動次數(shù)、實際運(yùn)行時間等都較少，規(guī)模較大后約為后者1/3左右。

采用更多測試數(shù)據(jù)(略)，進(jìn)行類似文［8］的穩(wěn)定性擬合，本文比較次數(shù)約為1.44nln(n)-1.24n，移動次數(shù)約為n2/24;算法［6］移動次數(shù)約為n2/8。

下面由歸并排序結(jié)果反推歸并結(jié)果:設(shè)歸并長為t/2的等長兩段(歸并后長t)的復(fù)雜性為f(t)，在歸并排序中分別對長n/2的2段歸并1次、長n/4的4段歸并2次、…、長1的n段歸并n/2次，所以歸并排序的復(fù)雜性為

類似，若規(guī)模為2n則有

式(2)-2×(1) 得f(2n)=T(2n)-2T(n)，也即f(n)=T(n)-2T(n/2)。

由排序的移動次數(shù)T(n)≈n2/24知?dú)w并的移動次數(shù)f(n)≈T(n)-2*T(n/2)=n2/48。由排序的比較次數(shù)T(n)≈1.44nln(n)-1.24n，知?dú)w并的比較次數(shù)f(n)≈T(n)-2*T(n/2)=1.44nln2≈n，與理論結(jié)果一致。

3 結(jié)論

就歸并而言，本文算法具有簡便、穩(wěn)定、就地進(jìn)行、比較次數(shù)最優(yōu)的特點，只是移動次數(shù)為二次，不適合用于歸并排序(大規(guī)模時)。也正是因為移動次數(shù)為二次，算法尚有很大的改進(jìn)空間，其中一個工作是優(yōu)化、改進(jìn)緩沖區(qū)的數(shù)據(jù)組織，擬后續(xù)進(jìn)行。

［1］Kronrod M A.Optimal ordering algorithm without operational field［C］//Soviet Math.Dokl.1969，10(744-746):342.

［2］Geffert V，Katajainen J，Pasanen T.Asymptotically efficient in-place merging［J］.Theoretical Computer Science，2000，237(1):159-181.

［3］Kim P S，Kutzner A.On optimal and efficient in place merging［M］//SOFSEM 2006:Theory and Practice of Computer Science.Springer Berlin Heidelberg，2006:350-359.

［4］Ellis J，Markov M.In situ，stable merging by way of the perfect shuffle［J］.The Computer Journal，2000，43(1):40-53.

［5］Dalkilic M E，Acar E，Tokatli G.A simple shuffle-based stable in-place merge algorithm［J］.Procedia Computer Science，2011，3:1 049-1 054.

［6］范時平，聶永萍，汪林林.一種基于數(shù)據(jù)塊交換的快速穩(wěn)定原地歸并算法［J］.重慶郵電學(xué)院學(xué)報(自然科學(xué)版)，2004，16(4):93-96.

［7］胡圣榮.關(guān)于排序算法的隨機(jī)輸入序列［J］.武漢理工大學(xué)學(xué)報，2006，28(9):105-107.

［8］胡圣榮.關(guān)于排序效率的數(shù)值估計［J］.廣州城市職業(yè)學(xué)院學(xué)報，2008，2(1):61-64.