上篇部落格我們主要聊了堆排序的相關内容，本篇部落格，我們就來聊一下歸并排序的相關内容。歸并排序主要用了分治法的思想，在歸并排序中，将我們需要排序的數組進行拆分，将其拆分的足夠小。當拆分的數組中隻有一個元素時，則這個拆分的數組是有序的。然後我們将這些有序的數組進行兩兩合并，在合并過程中進行比較，合并生成的新的數組仍然是有序的。然後再次将合并的有序數組進行合并，重複這個過程，知道整個數組是有序的。
下方我們先給出兩個有序數組合并的示意圖以及代碼，然後給出歸并排序的相關内容。歸并排序其實就是拆分+合并。廢話少說，開始今天的内容。
一、合并兩個有序數組
在本篇部落格的第一部分我們先給出合并兩個有序數組的示意圖以及相關代碼，在歸并排序時，我們會使用到此部分的内容。下方會給出兩個有數數組的合并，并且會給出相應的代碼實作。
1.有序數組合并的示意圖
因為兩個有序數組在合并後的新的數組仍然是有序的，是以我們需要對有序數組中的元素進行比較。每次從兩個數組中取出最小的那個元素，然後将兩個元素進行比較，将最小的那個元素放入到新的數組中。下方就是有序數組合并的示意圖。
-
首先從兩個有序數組中取出最小的值，如下所示。我們将9和10取出後進行比較，将較小的9存入我們新的數組中。
-
重複上個步驟，如果有一個數組中的元素被取完，将另一個數組中剩餘的元素直接追加到我們的新的數組中即可。
2.代碼實作
根據上述示意圖給出相關的代碼實作并不困難，下方就是上述過程的代碼實作。下方這個mergeArray()函數，就是将兩個有序數組合并成一個新的有序數組的具體代碼實作。mergeArray()的兩個參數就是即将合并的兩個有序數組，而傳回值就是合并後新的有序的數組。代碼比較簡單，在此就不做過多贅述了。
二、歸并排序
上述實作完兩個有序數組合并成新的有序數組完畢後，接下來就該歸并排序出場了。在歸并排序過程中，會使用到上述的内容。因為我們将無序數列進行分割後，就會不斷調用上述的合并代碼，将小的有序的數組合并成較大的有序數組，再次合并，直到我們原始的數組是有序的為止。下方會給出相應的示意圖以及歸并排序的Swift代碼實作。
1.歸并排序示意圖
下方就是我們歸并排序的示意圖，稍後的代碼實作也是根據下方的示意圖來寫的。是以對下方示意圖的充分了解還是很有必要的。在下方示意圖中，從上往下就是我們歸并排序的整個過程。我們需要排序的序列為[62, 88, 58, 47, 62, 35, 73, 51, 99, 37, 93]。下方是對每一步的解析：
- 首先我們将需要排序的序列進行拆分，拆分成足夠小的數組。也就是拆分的數組中隻有一個元素。無序數組拆分的所有數組因為其中隻含有一個元素，是以都是有序的。我們就可以對這些有序的小數組進行合并了。
- 将拆分的多個有序數組調用第一部分實作的mergeArray()函數進行兩兩合并，合并後的新數組仍然是有序的。我們再次對這些合并産生的數組進行兩兩合并，直到所有被拆分的數組有重新被合并成一個大數組位置。這個重新合并生成的數組就是有序的，也就是歸并排序所産生的有序序列。
下方就是拆分+多次合并的詳細過程，最終我們得到的就是一個有序序列。如下所示：
2、上述過程的代碼實作
根據上述的示意圖，我們給出相應的代碼實作應該是比較容易的。就是将我們的無序數組進行拆分，然後進行多次合并，最後合并成一個大的有序數組。下方代碼就是對上述過程的描述。
- 在下方代碼中的第一個框中就是将我們的無序數組進行拆分。被拆分的小的有序的數組存入到tempArray中，便于我們下方周遊進行合并。
- 第二個框就是對tempArray中被拆分的數組進行周遊，在周遊的過程中進行兩兩合并，将合并的數組再次存入到tempArray中，直到tempArray中隻含有一個數組為止。
而tempArray最終的數組就是歸并排序的最終結果。下方是整個過程，代碼并不複雜。
上述代碼的實作在有些資料結構的教程上是使用遞歸實作的，即使是不使用遞歸實作也比上述代碼要麻煩。
三、測試用例
對上述代碼的測試我們仍然會使用到我們之前的測試用例，因為上述排序類仍然遵循我們之前定義的SortType協定。下方就是本篇部落格的測試用例，也是所有排序方式的測試用例。這個MergeSort類就是我們歸并排序的類。
上述用例的輸出結果如下，從輸出結果中，我們就能明顯的看出拆分和合并的整個過程。如下所示：
本篇部落格對堆排序的介紹就先到這兒，下篇部落格我們将會介紹“快速排序”的詳細内容。本篇部落格的相關代碼依然會在github上進行分享，下方是github分享位址，如下所示：
github代碼分享位址：https://github.com/lizelu/DataStruct-Swift/tree/master/AllKindsOfSort
作者：青玉伏案
出處：http://www.cnblogs.com/ludashi/
本文版權歸作者和共部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。
如果文中有什麼錯誤，歡迎指出。以免更多的人被誤導。
收履歷：某網際網路公司，招聘iOS/Android靠譜工程師，入職後，可内部聯系樓主，有小禮品贈送，有意者可郵箱投遞履歷：[email protected]