1、歸并排序原理

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

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

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

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

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

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

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

3、歸并排序算法驗(yàn)證

下面我們寫(xiě)一個(gè)小程序驗(yàn)證算法的正確性。

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

從輸出結(jié)果中，我們對(duì)照?qǐng)D解歸并排序過(guò)程，完全符合。

責(zé)任編輯：lq6