本文將介紹排序算法中的歸并排序，學習歸并排序需要很好地理解計算機中的分治思想和遞歸思想。

1 分治思想

歸并排序，利用分而治之的思想，將大的問題，轉(zhuǎn)換成簡單的，小的問題來解決。分治，字面上的解釋是“分而治之”，就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。在計算機科學中，分治法就是運用分治思想的一種很重要的算法。它的核心思想可以用一句話來概括：大事化小，小事化了。

使用分治法解決問題，需要有兩部分內(nèi)容，一部分是分解，將問題不停分解成更小的子問題，當問題小到一定規(guī)模時，可以比較容易地解決。一部分是合并，當子問題被解決時，要通過一定的方法，合并出原問題的解。

2 歸并排序

歸并排序是怎么分的呢？我們要對n個數(shù)排序，直接排太麻煩，拆成對兩部分，對n/2個數(shù)排序，把它們合并成一個有序數(shù)組，就是答案。對n/2個數(shù)排序還是太復雜，繼續(xù)二分下去，n/4，n/8，n/16……直到分到最小，也就是長度為1為止。這個時候就不用分了。因為長度為1本身已經(jīng)有序了。

image

如圖是歸并排序的一個例子，前四行是對問題進行分解，后四行是對子問題進行合并，最終得到原始問題的解。

使用分治的思想解決計算機的問題，分解的部分是比較簡單的，合并的部分是比較難的，并且這部分的效率也影響到了算法的整體效率。

對于歸并排序來說，合并部分的任務是，把有序序列合并成一個完整的有序序列。怎么合并呢？

image

我們把有序序列1和2進行合并，需要另外一片新的空間，用來存放合并后的數(shù)組。我們首先比較序列1和2的開頭，由于是有序序列，開頭就是最小的元素。比較兩個元素看誰更小，把最小的那個元素添加到合并序列中。添加完之后，把該元素從序列里移除（實際代碼中并不會移除，而是指針直接指向下一個位置）。以上面圖①為例，2和3比較，2比較小，填入到合并序列中。然后把2去掉。變成②中的情況。再把3和5比較，3比較小，加入到合并序列中，把3從原始序列中去掉。如此反復，直到序列1和2都合并完畢。

如果出現(xiàn)一個序列已經(jīng)空了，另一個序列還有多個元素，直接把這些元素添加到合并序列最后面即可。

3 代碼解析

image

merge_sort函數(shù)定義了長度為n的輔助數(shù)組，用于歸并排序中合并的過程。

sort函數(shù)，對數(shù)組進行分割，將問題劃分為左半部分和右半部分兩個子問題，之后將兩個子問題進行合并。注意到這里使用了遞歸，使得問題不斷分解，直到left>=right，此時子問題的數(shù)組長度為1。

對遞歸不了解的可以查看

圖標

merge函數(shù)是歸并排序中合并的部分。它對兩個有序序列進行合并，合并成大的有序序列。這部分看代碼不難理解。

4 效率分析

歸并排序的時間復雜度T(n),每次可以分解出相同規(guī)模的子問題，并且這兩個子問題合并的復雜度為O(n)，則T(n)=2T(n/2)+O(n)，根據(jù)主定理可以得到T(n)=O(nlogn)。需要注意的是，合并部分的時間復雜度如果過高，比如為O(n^2)，會導致整體時間復雜度變大。