1、歸并排序原理
歸并排序的核心思想是:利用分治策略,不斷劃分子序列直到不能劃分為止,此時各個子序列是有序的,合并相鄰有序子序列最終得到一個有序序列。我們利用下圖解釋劃分子序列過程。
現在有原始序列[5, 10, 6, 8, 15, 11, 10, 7]采用遞歸的方式不斷對序列進行劃分,最終劃分成單個元素的序列。 有序子序列合并過程如下圖所示:
相鄰有序子序列進行合并,得到一個有序的序列。最終所有有序子序列進行合并得到一個完整的有序序列。
2、歸并排序實現
根據子序列合并過程圖我們可以看出,本質上就是兩個有序子序列進行合并成一個有序序列的過程。劃分的過程還是在原始序列里進行劃分,所以相鄰的序列必定有邊界進行劃分,現假設兩個相鄰子序列邊界分別是left、mid和right。其中left~mid構成一個子序列,mid+1~right構成另外一個子序列,兩個序列相鄰。合并代碼如下:
每次將較小的值放在臨時緩沖區中,其中一個子序列遍歷完畢則退出循環,判斷兩個子序列是否都已遍歷完畢,將未遍歷完畢的子序列拷貝到臨時緩沖區中,最后將臨時緩沖區里的內容再復制到兩個子序列的所在區間,這樣兩個子序列合并完畢且有序,為了便于觀察合并過程,每進行一次歸并則打印歸并后的序列值。
歸并排序實現代碼如下:
3、歸并排序算法驗證
下面我們寫一個小程序驗證算法的正確性。
為了便于觀察,原始數據和圖解的一樣,現編譯運行輸出如下:
從輸出結果中,我們對照圖解歸并排序過程,完全符合。
責任編輯:lq6
-
代碼
+關注
關注
30文章
4779瀏覽量
68526 -
序列
+關注
關注
0文章
70瀏覽量
19555
原文標題:圖解歸并排序
文章出處:【微信號:AndroidPush,微信公眾號:Android編程精選】歡迎添加關注!文章轉載請注明出處。
發布評論請先 登錄
相關推薦
評論