說(shuō)明：該系列博客整理自《算法導(dǎo)論(原書(shū)第二版)》，但更偏重于實(shí)用，所以晦澀偏理論的內(nèi)容未整理，請(qǐng)見(jiàn)諒。另外本人能力有限，如有問(wèn)題，懇請(qǐng)指正！
1、本節(jié)摘要
????算法設(shè)計(jì)的方法有很多。插入排序?使用的是?增量?（incremental）方法：在排好子數(shù)組?A?[ 1 ..?j?- 1 ]后，將元素?A?[?j?]插入，形成排好序的子數(shù)組?A?[ 1 ..?j?]。
????在本節(jié)中，要介紹另一種設(shè)計(jì)策略，叫做“分治法”。下面要用分治法來(lái)設(shè)計(jì)一個(gè)排序算法，使其性能比插入排序好的多。學(xué)過(guò)第4章就可以知道，分治類(lèi)算法的優(yōu)點(diǎn)之一是可以利用在第4章中介紹的技術(shù)，很容易的確定其運(yùn)行時(shí)間。
2、分治法思想介紹
????有很多算法在結(jié)構(gòu)上是?遞歸?的：為了解決一個(gè)給定的問(wèn)題，算法要一次或多次地遞歸調(diào)用其自身來(lái)解決相關(guān)子問(wèn)題。這些算法通常采用?分治策略?（divide-and-conquer）：將原問(wèn)題劃分成?n?個(gè)規(guī)模較小而結(jié)構(gòu)與原問(wèn)題相似的子問(wèn)題；遞歸地解決這些子問(wèn)題，然后再合并其結(jié)果，就得到原問(wèn)題的解。
? ? 歸并排序、動(dòng)態(tài)規(guī)劃算法、貪心算法這些常用的算法都是在“分治法”思想的基礎(chǔ)上分析出來(lái)的，他們是分治法思想的體現(xiàn)。
????分治模式在每一層遞歸上都有三個(gè)步驟：
????????????分解（Divide）：將原問(wèn)題分解成一系列子問(wèn)題；
????????????解決（Conquer）：遞歸地解各個(gè)子問(wèn)題。若子問(wèn)題足夠小，則直接求解；
????????????合并（Combine）：將子問(wèn)題的結(jié)果合并成原問(wèn)題的解。
3、歸并排序（合并排序）
????歸并排序（merge sort）完全依照了 分治策略，直觀的操作如下：
????????????分解：將?n?個(gè)元素分成各含?n?/ 2個(gè)元素的子序列；
????????????解決：對(duì)兩個(gè)子序列遞歸地排序；若子問(wèn)題足夠小，則直接求解(對(duì)子序列排序時(shí)，其長(zhǎng)度為1時(shí)遞歸結(jié)束，因?yàn)閱蝹€(gè)元素被視為是已排好序的)；
????????????合并：合并兩個(gè)已排序的子序列以得到排序結(jié)果。
????歸并排序的關(guān)鍵步驟在于合并兩個(gè)已排序的子序列。這里引入一個(gè)輔助過(guò)程?MERGE(A, p, q, r)?，其中?A?為數(shù)組，?p?，?q?和?r?都是下標(biāo)，有?p?<=?q?<?r?。該過(guò)程假設(shè)子數(shù)組?A?[?p?..?q?]和?A?[?q?+ 1 ..?r?]都已排好序，并將它們合并成一個(gè)已排好序的子數(shù)組代替當(dāng)前子數(shù)組?A?[?p?..?r?]。
? ??MERGE過(guò)程的時(shí)間代價(jià)為Θ(n)，其中n = r - p + 1是待合并的元素個(gè)數(shù)。下面通過(guò)撲克牌的例子說(shuō)明算法的工作過(guò)程：假設(shè)兩堆牌都面朝上的放在桌上，每一堆都是已排序的，且最小的牌在最上面。我們希望把兩堆牌合并成一個(gè)排好序的輸出堆，且面朝下的放在桌上。合并過(guò)程為，在面朝上的兩堆牌中，選取頂上兩張中較小的一張，將其取出后面朝下的放到輸出堆中。重復(fù)這個(gè)步驟，直到某一輸入堆為空時(shí)為止。這時(shí)把輸入堆中余下的牌 面朝下的放入輸入堆中即可。從計(jì)算的角度來(lái)看，每一個(gè)基本步驟所花時(shí)間是個(gè)常亮，因?yàn)槲覀冎皇遣榭床⒈容^頂上的兩張牌，又因至多進(jìn)行n次比較，所以MERGE過(guò)程的時(shí)間復(fù)雜度為Θ(n)。
? ? 下面的偽代碼實(shí)現(xiàn)了上述思想，但有一個(gè)小的優(yōu)化，即在兩個(gè)子堆中增加了∞這個(gè)哨兵，來(lái)避免檢查兩個(gè)子堆是否為空。一旦出現(xiàn)兩個(gè)哨兵牌同時(shí)出現(xiàn)時(shí)，說(shuō)明兩堆牌中非哨兵的牌都已經(jīng)被放到輸出堆中去了，因?yàn)轭A(yù)先直到只有r - p + 1張牌會(huì)被放到輸出堆中去，因此此時(shí)也是執(zhí)行了r - p + 1個(gè)基本步驟了，循環(huán)可以停止了。
MERGE(A, p, q, r)
1????? n1 = q - p + 1
2? ????n2 = r - q
3? ????//let L[1 .. n1 + 1] and R[1 .. n2 + 1] be new arrays
4? ????for i = 1 to n1
5? ? ? ????L[i] = A[p + i - 1]
6? ????for j = 1 to n2
7? ? ? ????R[j] = A[q + j]
8? ????L[n1 + 1] = MAX
9? ????R[n2 + 1] = MAX
10 ????i = 1
11 ????j = 1
12 ????for k = p to r
13? ? ???? if L[i] <= R[j]
14? ? ? ? ???? A[k] = L[i]
15? ? ? ? ???? i = i + 1
16? ? ???? else
17? ? ? ? ???? A[k] = R[j]
18? ? ? ? ???? j = j + 1
????下面說(shuō)明完整的歸并排序過(guò)程MERGE-SORT，其中 MERGE?過(guò)程作為歸并排序中的一個(gè)子程序來(lái)使用。MERGE-SORT(A, p, r)?對(duì)子數(shù)組?A?[?p?..?r?]排序。如果?p?>=?r?，則該子數(shù)組中至多只有一個(gè)元素，視為已排序。否則，分解步驟就計(jì)算出一個(gè)下標(biāo)?q?，將?A?[?p?..?r?]分成?A?[?p?..?q?]和?A?[?q?+ 1 ..?r?]，各含?FLOOR(n / 2)?1?個(gè)元素。
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)
????下圖自底向上地展示了當(dāng)?n?為2的冪時(shí)，整個(gè)過(guò)程中的操作。算法將兩個(gè)長(zhǎng)度為1的序列合并成已排好序的、長(zhǎng)度為2的序列，接著又將長(zhǎng)度為2的序列合并成長(zhǎng)度為4的序列，直到最終形成排好序的?n?的序列。
4、歸并排序時(shí)間復(fù)雜度分析
? ? 這里只說(shuō)明分析結(jié)果，分析過(guò)程請(qǐng)參考《算法導(dǎo)論(原書(shū)第二版)》。歸并排序?的總代價(jià)為cn(lgn + 1) =?cn * lgn +?cn，忽略低階項(xiàng)和常亮c，即得到結(jié)果Θ(n * lgn)。
????需要說(shuō)明的是，忽略低階項(xiàng)和常亮c的前提是輸入規(guī)模n很大。使用歸并排序時(shí)一般輸入規(guī)模都很大，輸入規(guī)模很小時(shí)一般采用的是插入排序。
5、練習(xí)
二分查找偽碼：
BINARY-SEARCH(A, v)
1? front = 1
2? end = A.length
3? while front < end
4? ? ? middle = (front + end) / 2
5? ? ? if A[middle] < v
6? ? ? ? ? front = middle + 1
7? ? ? else if A[middle] > v
8? ? ? ? ? end = middle - 1
9? ? ? else
10? ? ? ? return middle
11 return -1
6、參考文檔
? ??合并排序，該文章中的兩點(diǎn)改進(jìn)很好：1）、分割為合適長(zhǎng)度的小序列后使用插入排序，然后將經(jīng)過(guò)插入排序的小序列進(jìn)行合并排序；2）、算法中對(duì)兩個(gè)小序列進(jìn)行合并操作之前，先對(duì)其中值點(diǎn)進(jìn)行比對(duì)，如果符合期望的升/降序目標(biāo)，則不用再經(jīng)過(guò)合并操作，直接連接起來(lái)即可。
