1、歸并排序原理

歸并排序的核心思想是：利用分治策略，不斷劃分子序列直到不能劃分為止，此時各個子序列是有序的，合并相鄰有序子序列最終得到一個有序序列。我們利用下圖解釋劃分子序列過程。

現(xiàn)在有原始序列［5， 10， 6， 8， 15， 11， 10， 7］采用遞歸的方式不斷對序列進(jìn)行劃分，最終劃分成單個元素的序列。 有序子序列合并過程如下圖所示：

相鄰有序子序列進(jìn)行合并，得到一個有序的序列。最終所有有序子序列進(jìn)行合并得到一個完整的有序序列。

2、歸并排序?qū)崿F(xiàn)

根據(jù)子序列合并過程圖我們可以看出，本質(zhì)上就是兩個有序子序列進(jìn)行合并成一個有序序列的過程。劃分的過程還是在原始序列里進(jìn)行劃分，所以相鄰的序列必定有邊界進(jìn)行劃分，現(xiàn)假設(shè)兩個相鄰子序列邊界分別是left、mid和right。其中l(wèi)eft~mid構(gòu)成一個子序列，mid+1~right構(gòu)成另外一個子序列，兩個序列相鄰。合并代碼如下：

每次將較小的值放在臨時緩沖區(qū)中，其中一個子序列遍歷完畢則退出循環(huán)，判斷兩個子序列是否都已遍歷完畢，將未遍歷完畢的子序列拷貝到臨時緩沖區(qū)中，最后將臨時緩沖區(qū)里的內(nèi)容再復(fù)制到兩個子序列的所在區(qū)間，這樣兩個子序列合并完畢且有序，為了便于觀察合并過程，每進(jìn)行一次歸并則打印歸并后的序列值。

歸并排序?qū)崿F(xiàn)代碼如下：

3、歸并排序算法驗證

下面我們寫一個小程序驗證算法的正確性。

為了便于觀察，原始數(shù)據(jù)和圖解的一樣，現(xiàn)編譯運行輸出如下：

從輸出結(jié)果中，我們對照圖解歸并排序過程，完全符合。

責(zé)任編輯：lq6