基于數組的歸并排序算法該如何理解？

謝邀。

我的上個回答簡要討論了下什么是算法，并且介紹了C語言程序開發中比較基本的數組排序算法——插入排序法，如果題主看了，應該有助于理解本題。

事實上，讓C語言https://www.52fb.cn具有魅力的是算法，拿到問題，能夠設計出解決方案并且完成代碼的是https://www.b5b6.com，只會按照步驟編碼的是碼農。

這是上個回答的主題，有朋友看到也有感而發：在評論區說，“程序是骨架，算法才是靈魂”。的確，C語言程序只是指令，計算機只會冷冰冰的按照指令辦事，它并不能解決問題，真正解決問題的還是人。

什么樣的算法才是好的算法呢？

假設計算機是無限快的，并且存儲器是免費的無限大的，那最好的算法就是最容易實現的算法。

然而，計算機也許是快的，但它們不是無限快。存儲器也許是廉價的，但不是免費的。所以計算時間是一種有限資源，存儲器的空間也一樣。優秀的https://www.b5b6.com應該盡力設計出開銷更小的算法。

下面再討論下C語言程序開發中，數組的歸并排序算法，這種算法也是比較經典的排序法，在數組元素非常多的情況下，效率遠遠高于插入排序法。

什么是歸并排序呢？

歸并排序的定義，希望了解“一本正經”的官方書面定義可以自行百科。這里就不寫了，因為“冷冰冰的”書面定義對不了解它的人來說太難懂。

我打算用一些容易理解的例子來解釋它。

假設有一個C語言數組需要排序，那數組長度為多長最簡單呢？顯然是長度為 1 時，排序最簡單，什么都不需要做，就能夠排好序。

歸并排序的基本思路就是這樣：把長數組一直拆分下去，直到最后不能拆分為止，這時長數組被拆分為若干個長度為 1 的數組，長度為 1 的數組顯然是排好序的了。

例如下圖是一個長度為 5 的數組，為了排序，先把它拆分到不能繼續拆為止。

接著，只要把這些排好序的子數組按照從小到大的順序合并，就可以得到最終排好序的數組了。

好了，現在知道歸并排序的算法了，那怎樣使用 C語言https://www.52fb.cn完成這個算法呢？

使用C語言https://www.52fb.cn實現歸并排序算法

歸并排序算法總體可以分為兩步：拆分數組，合并數組。先來看看怎樣使用C語言實現數組的拆分。

使用C語言拆分數組

對數組拆分有多種方法，這里選擇平分法。

如果使用 start 表示數組頭，end 表示數組尾，每次平均拆分，都會將數組分為 start 到 mid，和 mid+1 到 end 兩部分，其中 mid 表示中間點，所以 mid = (start+end)/2。就這樣一直拆分下去，直到不能繼續拆分為止。

不能拆分時，start 應該不再小于 end。

拆分數組的數學描述完畢了，容易看出，遞歸（如果題主對C語言的遞歸不理解，可以查看我之前的問答或者文章。）非常適合解決這樣的問題。我們現在用C語言來實現這樣的拆分，先確定遞歸的基礎條件：

拆分過程會在 start 不再小于 end 時停下。其他情況時，拆分會繼續下去，相關C語言代碼如下，請看：

divide(start, mid); 負責拆分前半段，divide(mid+1, end); 負責拆分后半段。這樣的 divide 函數可以把數組拆分到不可拆分為止。

使用C語言合并數組

使用 divide 函數把數組拆分完畢后，就可以按照從小到大的順序把各個元素合并到原來的數組了。

由于兩個子序列都已經排好序了，所以 merge() 函數的C語言代碼很簡單，每次循環取兩個子序列中最小的元素進行比較，將較小的元素取出放到最終的排序序列中，如果其中一個子序列的元素已取完，就把另一個子序列剩下的元素都放到最終的排序序列中。

使用C語言實現數組的歸并排序

數組的拆分和合并函數都寫好了，可以把它倆結合起來，實現數組的排序了。

測試C語言實現的歸并排序

這里使用 8 個元素的數組做測試：

編譯并執行這段C語言代碼，發現數組被成功排序了。

到這里，相信題主應該明白如何使用C語言實現數組的歸并排序了。它和插入排序算法都屬于排序算法，但是二者的效率差異性卻很大。

https://www.b5b6.com一般如何衡量算法的效率呢？數組的插入排序法和歸并排序法的效率差異性到底有多大呢？我之前的文章已經比較詳細的討論過，題主可以點擊我的主頁查看。

歡迎在評論區一起討論，質疑。文章都是手打原創，每天最淺顯的介紹C語言、linux等嵌入式開發，喜歡我的文章就關注一波吧，可以看到最新更新和之前的文章哦。