一個新的就地穩定歸并算法

胡圣榮

(華南農業大學 工程學院，廣東 廣州 510642)

0 引言

在計算機科學與實踐中經常遇到歸并問題，它是外排序的基礎，在內排序中則可構成歸并排序。另外，一些并行排序算法也經常采用歸并的方法;在各種排序網絡中，基于歸并的排序網絡比較簡單而實用。

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

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

1 算法

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

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

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

該過程進行中可能出現兩種情況:

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

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

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

該過程不破壞穩定性。歸并算法如下:

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

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

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)和隊列區 R［j，p);結束返回;}

else{理順隊列;i=j;j=p;轉 L1。}

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

圖1 歸并算法原理

2 性能分析與測試

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

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

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

表1 歸并排序結果對比

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

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

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

類似，若規模為2n則有

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

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

3 結論

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

［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］范時平，聶永萍，汪林林.一種基于數據塊交換的快速穩定原地歸并算法［J］.重慶郵電學院學報(自然科學版)，2004，16(4):93-96.

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

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