分而治之
從算法設(shè)計(jì)的分類上來說铆遭，插入排序屬于增量方法缘缚。在排序好子數(shù)組A[1 ‥ j-1]后煤痕，再將單個(gè)元素A[j]插入子數(shù)組的適當(dāng)位置虽惭，產(chǎn)生排序好的子數(shù)組A[1 ‥ j]橡类。整個(gè)算法就是不斷以此方法增量插入，直到子數(shù)組包含了所有數(shù)組元素芽唇。
本篇將要介紹的歸并排序顾画，是用另一種思想來解決排序問題的，在算法設(shè)計(jì)分類上屬于分治法匆笤。
分治法思想是研侣，將原問題分解為幾個(gè)規(guī)模較小但類似于原問題的子問題，遞歸的求解這些子問題炮捧，然后在合并這些子問題的解庶诡，最終建立原問題的解。
這里提到一個(gè)詞遞歸咆课，其解釋是：為了解決一個(gè)給定問題灌砖，算法一次或多次的調(diào)用其自身以解決緊密相關(guān)的子問題。遞歸是分治思想的一個(gè)具體實(shí)現(xiàn)傀蚌。
分治模式在每層遞歸時(shí)都有三個(gè)步驟：
- 分解：將原問題分解為若干子問題基显，這些子問題是原問題的規(guī)模較小的實(shí)例；
- 解決：遞歸的求解各子問題善炫；
- 合并：合并子問題的解撩幽，得到原問題的解。
看到這里箩艺，“直覺”上可能會產(chǎn)生一個(gè)極大的疑問：最底層的子問題是在哪里解決的窜醉？產(chǎn)生這個(gè)疑問是正常的，因?yàn)榈诙健敖鉀Q”也僅僅是調(diào)用自身艺谆，其實(shí)就是重新進(jìn)入了下一層的分解榨惰、解決和合并，而沒有看到“如何解決”静汤。
答案是：無需解決琅催。換句話說居凶，層層分解到子問題的規(guī)模足夠小時(shí)，解就自己出現(xiàn)了藤抡。后面還會再提到這一點(diǎn)侠碧。
歸并排序偽碼
歸并排序按照分治法的三個(gè)步驟如下：
- 分解：分解待排序的n個(gè)元素的序列，變成各具n/2個(gè)元素的兩個(gè)子序列缠黍；
- 解決：遞歸的調(diào)用自身排序兩個(gè)子序列弄兜；
- 合并：合并兩個(gè)已排序的子序列以產(chǎn)生最終排序的序列。
上一篇合并算法中已經(jīng)解決了合并算法MERGE瓷式，歸并排序就剩下如何進(jìn)行分解替饿，和遞歸調(diào)用了。
看代碼的確就這三步：
MERGE-SORT(A, p, r)
1 if p < r
2 q = (p + r) / 2
3 MERGE-SORT(A, p, q)
4 MERGE-SORT(A, q+1, r)
5 MERGE(A, p, q, r)
注：(p + r) / 2如果不是整除贸典，則取小于它的最大整數(shù)盛垦。
p < r時(shí)，表明數(shù)組有繼續(xù)拆分的可能瓤漏。當(dāng)p ≥ r時(shí)腾夯，則表示該子數(shù)組最多有一個(gè)元素，所以無需排序就已經(jīng)是排好序了蔬充，這就是分解到足夠小會導(dǎo)致的自動解決蝶俱。換句話說，我們一直把數(shù)組分解下去饥漫，直到分成每個(gè)子數(shù)組只包含1個(gè)元素時(shí)榨呆，即第3行中p = q，第4行中q+1 = r庸队，那么第3和第4行的MERGE-SORT會立即返回积蜻，并執(zhí)行MERGE，然后返回上一層MERGE-SORT彻消，直到最上層竿拆。
一個(gè)例子
一個(gè)有8個(gè)元素的數(shù)組A[5, 2, 4, 7, 1, 3, 2, 6]，采用歸并排序的圖示如下圖宾尚。圖中的下方藍(lán)區(qū)部分是上面白區(qū)的數(shù)組不同時(shí)刻的鏡像丙笋。白區(qū)主要在做“分解”，藍(lán)區(qū)主要在做“合并”煌贴。
歸并排序Java代碼
public static void mergeSortInASC(int [] numbers, int p, int r) throws Exception {
if(p < r){
int q = (int)Math.floor((p + r) / 2);
mergeSortInASC(numbers, p, q);
mergeSortInASC(numbers, q + 1, r);
mergeInASC(numbers, p, q, r);
}
}
共享協(xié)議：署名-非商業(yè)性使用-禁止演繹（CC BY-NC-ND 3.0 CN）
轉(zhuǎn)載請注明：作者黑猿大叔（簡書）
