鄒永林

（常熟理工學(xué)院計(jì)算機(jī)學(xué)院，常熟　215500）

歸并排序的概念與算法設(shè)計(jì)

鄒永林

（常熟理工學(xué)院計(jì)算機(jī)學(xué)院，常熟215500）

0　引言

歸并排序是一種重要的內(nèi)部排序方法，在數(shù)據(jù)結(jié)構(gòu)課程中作為一類獨(dú)特的排序方法專門進(jìn)行介紹和討論。但是，其算法設(shè)計(jì)在教學(xué)實(shí)踐中常與合并排序混為一談，這在一定程度上造成了對歸并排序概念的曲解和算法設(shè)計(jì)的缺失。

本文首先分析了歸并排序與合并排序的差異，進(jìn)而對標(biāo)準(zhǔn)的歸并排序算法設(shè)計(jì)進(jìn)行了探討。

1　歸并排序與合并排序的差異

關(guān)于利用歸并思想進(jìn)行排序的方法，英文著作中采用“Merge Sort”一詞標(biāo)識，中文文獻(xiàn)中有兩個(gè)術(shù)語：“歸并排序”和“合并排序”，在數(shù)據(jù)結(jié)構(gòu)課程中常采用前者，在算法分析課程中采用后者，但在進(jìn)行算法設(shè)計(jì)與分析時(shí)，使用相同的算法代碼進(jìn)行說明。

實(shí)際上，歸并排序和合并排序之間，存在著一定的差異。以下分別從算法思想和排序過程兩個(gè)方面進(jìn)行討論。

1.1算法思想

在國內(nèi)絕大多數(shù)數(shù)據(jù)結(jié)構(gòu)著作［1-5］中，一般使用“歸并排序”一詞，且采用嚴(yán)蔚敏等的定義，即：“假設(shè)初始序列含有n個(gè)記錄，則可看成是n個(gè)有序子序列，每個(gè)子序列的長度為1，然后兩兩歸并，得到「n/2?個(gè)長度為2或1的有序子序列；再兩兩歸并，…，如此重復(fù)，直到得到一個(gè)長度為n的有序序列為止”。

而國外相關(guān)著作中，一般采用“合并排序”而非“歸并排序”的術(shù)語。Clifford A.Shaffer的定義［6］是：“合并排序是基于分治法的，它將一個(gè)數(shù)組分成兩個(gè)長度相等的子數(shù)組，為每一個(gè)子數(shù)組排序，然后再將它們合并成一個(gè)數(shù)組”。Anany Levitin的定義［7］是，“對于一個(gè)需要排序的數(shù)組A［0…n-1］，合并排序把它一分為二：A［0…?n/2」-1］和A［n/?2…n」-1］，并對每個(gè)子數(shù)組遞歸排序，然后把這兩個(gè)排好序的子數(shù)組合并為一個(gè)有序數(shù)組”。

從上述定義中可以看出，歸并排序和合并排序是兩個(gè)不同的概念，合并排序強(qiáng)調(diào)分治思想，利用一分為二的方法將一個(gè)待排序序列分成基本相等的兩個(gè)子序列，遞歸進(jìn)行排序；而歸并排序更注重兩兩歸并，至于如何將一個(gè)長度為n的待排序序列分解成n個(gè)長度為1的有序子序列，沒有具體約定。

1.2排序過程

在排序過程中，根據(jù)待排序序列的長度不同，歸并排序和合并排序也有差別。

當(dāng)序列長度n取2的冪次方時(shí)，歸并排序和合并排序的過程完全一致。因?yàn)榇藭r(shí)待排序序列總能劃分為兩個(gè)相等且長度為2的冪次方的子序列。

但更一般的情況是，當(dāng)n取非2的冪次方時(shí)，排序過程完全不同［2-5］。假設(shè)以一個(gè)含有11個(gè)元素的待排序序列｛49，38，65，97，76，13，27，49，85，36，21｝為例，排序過程分別如圖1和圖2所示。

圖1是按照合并排序思想進(jìn)行排序的完整過程?？梢钥闯?，每次分區(qū)時(shí)，均以當(dāng)前待排序區(qū)間的長度的一半?ni/2」進(jìn)行子區(qū)間劃分，直至得到n個(gè)長度為1的子序列，然后進(jìn)行兩兩合并完成排序；而在圖2中，從第四次劃分的結(jié)果開始，描述了符合歸并排序定義的過程，體現(xiàn)了（相鄰元素）兩兩歸并的特點(diǎn)，并不關(guān)心如何從一個(gè)包含n個(gè)元素的待排序序列得到n個(gè)長度為1的子序列。

根據(jù)上述分析，可以得到以下結(jié)論：合并排序和歸并排序是兩個(gè)不同的概念，其共同點(diǎn)是排序過程都借助2-路歸并的方法進(jìn)行，其差別體現(xiàn)在如何從一個(gè)長度為n的序列得到n個(gè)長度為1的子序列。因此，可以認(rèn)為，合并排序和歸并排序是歸并類排序的兩種不同方法，合并排序算法不能準(zhǔn)確描述歸并排序的所有可能情況。換句話說，歸并排序的算法不能以合并排序算法完全代替。

圖1　合并排序的過程示意圖

2　歸并排序的算法設(shè)計(jì)

參照合并排序的算法，可以設(shè)計(jì)出符合標(biāo)準(zhǔn)歸并排序思想的算法。

在圖2中，合并前的分區(qū)過程描述了歸并排序借鑒合并排序的分區(qū)方法進(jìn)行遞歸分區(qū)并得到符合歸并排序思想的n個(gè)長度為1的子序列的具體過程。從這個(gè)遞歸分區(qū)過程可以看出，當(dāng)對一個(gè)長度為n的待排序序列進(jìn)行歸并排序時(shí)，只要將每次分區(qū)的長度設(shè)置為2的冪次方即可。

對應(yīng)的歸并排序的算法代碼可設(shè)計(jì)如下：

圖2　歸并排序的過程示意圖

與標(biāo)準(zhǔn)的合并排序算法相比，上述算法中專門設(shè)置了一個(gè)參數(shù)del，作為分區(qū)的基準(zhǔn)長度，實(shí)現(xiàn)按照2的冪次方值的遞減序列進(jìn)行遞歸分區(qū)的目的。參數(shù)del的取值可根據(jù)實(shí)際長度n計(jì)算得到，在主函數(shù)中提前確定。

對圖2中的實(shí)例利用上述算法進(jìn)行排序，可得到與圖2完全一致的結(jié)果。

另外，從圖1和圖2描述的排序過程可知，對于一個(gè)包含n個(gè)元素的序列，歸并排序與合并排序的效率完全相同。

3　討論

本文通過對合并排序和歸并排序的概念和排序過程的分析，明確了兩者之間的聯(lián)系和區(qū)別，據(jù)此提出了歸并類排序的概念，并將兩者歸屬其下；然后，借鑒合并排序的算法，完成了歸并排序算法的設(shè)計(jì)，并通過實(shí)例驗(yàn)證了算法的正確性。

本文的研究有助于規(guī)范和完善數(shù)據(jù)結(jié)構(gòu)課程中有關(guān)歸并排序的知識體系和教學(xué)內(nèi)容，也可為學(xué)習(xí)和理解歸并排序知識提供幫助。

［1］嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）［M］.清華大學(xué)出版社，2014：283-284.

［2］胡學(xué)鋼.數(shù)據(jù)結(jié)構(gòu)（C語言版）［M］.高等教育出版社，2004：168-169.

［3］吳仁群.數(shù)據(jù)結(jié)構(gòu)簡明教程［M］.機(jī)械工業(yè)出版社，2011：193-195.

［4］周桂紅.數(shù)據(jù)結(jié)構(gòu)［M］.北京郵電大學(xué)出版社，2010：218-221.

［5］張曉莉，王苗，羅文劼.數(shù)據(jù)結(jié)構(gòu)與算法［M］.機(jī)械工業(yè)出版社，2008：245-247.

［6］Clifford A.Shaffer.數(shù)據(jù)結(jié)構(gòu)與算法分析［M］.電子工業(yè)出版社，1998：164-166.

［7］Anany Levitin.算法設(shè)計(jì)與分析基礎(chǔ)［M］.清華大學(xué)出版社，2007：95-97.

Order by Merging；Sequencing by Merging；Partition；Algorithm Design

Concept and Algorithm Design of Merge Sort

ZOU Yong-lin
（School of Computer Science and Engineering，Changshu Institute of Technology，Changshu 215500）

1007-1423（2015）20-0048-04

10.3969/j.issn.1007-1423.2015.20.011

鄒永林（1963-），男，江蘇常熟人，碩士，副教授，研究方向?yàn)樗惴ǚ治雠c設(shè)計(jì)

2015-04-21

2015-07-01

從算法思想和排序過程兩方面討論歸并排序和合并排序的區(qū)別，指出歸并排序算法不能以合并排序算法完全替代；進(jìn)而借鑒合并排序算法設(shè)計(jì)符合標(biāo)準(zhǔn)的歸并排序思想的算法，并通過實(shí)例驗(yàn)證算法的正確性。

歸并排序；合并排序；分區(qū)；算法設(shè)計(jì)

Discusses the differences between merge sort（order by merging）and merge sort（sequencing by merging）on two aspects of algorithm thought and sorting process，points out that the algorithm of merge sort（order by merging）cannot be entirely replaced by merge sort（sequencing by merging）；designs the algorithm of merge sort（order by merging）referencing the standard merge sort algorithm，takes an example to verify the correctness of the algorithm.