歸并排序的概念與算法設計

鄒永林

（常熟理工學院計算機學院，常熟　215500）

歸并排序的概念與算法設計

鄒永林

（常熟理工學院計算機學院，常熟215500）

0　引言

歸并排序是一種重要的內部排序方法，在數據結構課程中作為一類獨特的排序方法專門進行介紹和討論。但是，其算法設計在教學實踐中常與合并排序混為一談，這在一定程度上造成了對歸并排序概念的曲解和算法設計的缺失。

本文首先分析了歸并排序與合并排序的差異，進而對標準的歸并排序算法設計進行了探討。

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

關于利用歸并思想進行排序的方法，英文著作中采用“Merge Sort”一詞標識，中文文獻中有兩個術語：“歸并排序”和“合并排序”，在數據結構課程中常采用前者，在算法分析課程中采用后者，但在進行算法設計與分析時，使用相同的算法代碼進行說明。

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

1.1算法思想

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

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

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

1.2排序過程

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

當序列長度n取2的冪次方時，歸并排序和合并排序的過程完全一致。因為此時待排序序列總能劃分為兩個相等且長度為2的冪次方的子序列。

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

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

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

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

2　歸并排序的算法設計

參照合并排序的算法，可以設計出符合標準歸并排序思想的算法。

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

對應的歸并排序的算法代碼可設計如下：

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

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

對圖2中的實例利用上述算法進行排序，可得到與圖2完全一致的結果。

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

3　討論

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

本文的研究有助于規(guī)范和完善數據結構課程中有關歸并排序的知識體系和教學內容，也可為學習和理解歸并排序知識提供幫助。

［1］嚴蔚敏，吳偉民.數據結構（C語言版）［M］.清華大學出版社，2014：283-284.

［2］胡學鋼.數據結構（C語言版）［M］.高等教育出版社，2004：168-169.

［3］吳仁群.數據結構簡明教程［M］.機械工業(yè)出版社，2011：193-195.

［4］周桂紅.數據結構［M］.北京郵電大學出版社，2010：218-221.

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

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

［7］Anany Levitin.算法設計與分析基礎［M］.清華大學出版社，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-），男，江蘇常熟人，碩士，副教授，研究方向為算法分析與設計

2015-04-21

2015-07-01

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

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

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.