? ? ? ? 本節(jié)講兩個(gè)時(shí)間復(fù)雜度為O(nlogn)的排序算法：歸并排序和快速排序，它們都用到了分治的思想。分治，顧名思義，就是分而治之，將一個(gè)大問題分解成小的子問題來解決，小的子問題解決了，大問題也就解決了。

????????這兩種排序算法適合大規(guī)模的數(shù)據(jù)排序，比上節(jié)課講的三種排序方法要更常用。

? ? 1歸并排序

? ? ? ? 歸并排序的核心思想是將要排序的數(shù)組從中間分成前后兩部分，然后對(duì)兩部分分別排序，再將排好序的兩部分合并在一起，這樣整個(gè)數(shù)組就都有序了。如下圖所示：

? ? ? ? 分治思想和我們前面講的遞歸很像，其實(shí)，分治算法一般都是用遞歸來實(shí)現(xiàn)的。分治是一種解決問題的處理思想，遞歸是一種編程技巧。（后面再展開來講分治算法的思想，這節(jié)課還是以排序算法為主）

? ? ? ? 如何用遞歸代碼來實(shí)現(xiàn)歸并排序呢？

? ? ? ? 1）寫出遞推公式：merge_sort(p...r)=merge(merge_sort(p...q),merge_sort(q+1...r))

? ? ? ? 2）找到終止條件：p>=r

? ? ? ? 3）將遞推公式翻譯成遞歸代碼。

? ? ? ? Merge函數(shù)的實(shí)現(xiàn)思路：

? ? ? ? 代碼如下：

? ? ? ? 運(yùn)行結(jié)果：

? ? ? ? 總結(jié)一下：

? ? ? ? 第一，歸并排序是穩(wěn)定的排序算法。歸并排序穩(wěn)不穩(wěn)定關(guān)鍵要看Merge函數(shù)，在合并的過程中，如果 A[p…q] 和 A[q+1…r] 之間有值相同的元素，那我們可以像偽代碼中那樣，先把 A[p…q] 中的元素放入tmp數(shù)組，這樣就保證了值相同的元素，在合并前后的先后順序不變。

? ? ? ? 第二，歸并排序的時(shí)間復(fù)雜度是O(nlogn)。一個(gè)問題a分解為多個(gè)子問題b和c，如果我們定義求解a問題的時(shí)間是T(a)，求解b、c問題的時(shí)間是T(b)和T(c)，那我們就可以得到這樣的遞推公式：T(a)=T(b)+T(c)+K,其中K等于將兩個(gè)子問題b、c的結(jié)果合并成問題a的結(jié)果所消耗的時(shí)間。

? ? ? ? 我們假設(shè)對(duì)n個(gè)元素進(jìn)行歸并排序需要的時(shí)間是 T(n)，那分解成兩個(gè)子數(shù)組排序的時(shí)間都是 T(n/2)。我們知道，merge() 函數(shù)合并兩個(gè)有序子數(shù)組的時(shí)間復(fù)雜度是 O(n)。所以，套用前面的公式，歸并排序的時(shí)間復(fù)雜度的計(jì)算公式就是：

????????我們?cè)龠M(jìn)一步分解一下計(jì)算過程。

????????通過這樣一步一步分解推導(dǎo)，我們可以得到 T(n) = 2^kT(n/2^k)+kn。當(dāng) T(n/2^k)=T(1) 時(shí)，也就是 n/2^k=1，我們得到 k=log2n 。我們將k 值代入上面的公式，得到 T(n)=Cn+nlog2n。如果我們用大 O 標(biāo)記法來表示的話，T(n) 就等于 O(nlogn)。所以歸并排序的時(shí)間復(fù)雜度是 O(nlogn)。

? ? ? ? 歸并排序的執(zhí)行效率與要排序的原始數(shù)組的有序成都無關(guān)，所以它的時(shí)間復(fù)雜度是非常穩(wěn)定的，不管最好情況、最壞情況、還是平均情況，時(shí)間復(fù)雜度都是O(nlogn)。

? ? ? ? 第三，歸并排序的空間復(fù)雜度是O(n)。歸并排序有一個(gè)致命的弱點(diǎn)，就是它不是原地排序算法。它在合并兩個(gè)有序數(shù)組為一個(gè)有序數(shù)組時(shí)，需要借助額外的存儲(chǔ)空間，但是，盡管每次合并操作都需要申請(qǐng)額外的存儲(chǔ)空間，但是在合并完成之后，臨時(shí)開辟的內(nèi)存空間就被釋放掉了，在任意時(shí)刻，CPU只會(huì)有一個(gè)函數(shù)在執(zhí)行，也就是只會(huì)有一個(gè)臨時(shí)的內(nèi)存空間在使用，而這個(gè)臨時(shí)內(nèi)存空間最大也不會(huì)超過n，所以空間復(fù)雜度是O(n)。

? ? 2快速排序

? ? ? ? 快排的思想是這樣的：如果要排序數(shù)組中下標(biāo)從p到r之間的一組數(shù)據(jù)，我們選擇p到r之間的任意一個(gè)數(shù)據(jù)作為pivot（分區(qū)點(diǎn)），我們遍歷p到r之間的數(shù)據(jù)，將小于pivot的放在左邊，將大于pivot的放在右邊，將pivot放在中間。這樣數(shù)組p到r之間的數(shù)據(jù)就被分成了三個(gè)部分，前面p到q-1之間都是小于pivot的，中間是pivot，后面的q+1到r之間是大于pivot的，如下圖所示：

? ? ? ? 根據(jù)分治、遞歸的處理思想，我們可以用遞歸排序下表從p到q-1之間的數(shù)據(jù)和下標(biāo)從q+1到r之間的數(shù)據(jù)，直到區(qū)間縮小為1，就說明所有的數(shù)據(jù)都有序了。

? ? ? ? 1）遞推公式：quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1, r)

? ? ? ? 2）終止條件：p >= r

? ? ? ? 代碼：

? ? ? ? 其中的partition()分區(qū)函數(shù)就是隨機(jī)選擇一個(gè)元素作為pivot（一般情況下，可以選擇p到r區(qū)間的最后一個(gè)元素），然后對(duì)A[p...r]分區(qū)，函數(shù)返回pivot的下標(biāo)。

????????如果我們不考慮空間消耗的話，partition() 分區(qū)函數(shù)可以寫得非常簡單。我們申請(qǐng)兩個(gè)臨時(shí)數(shù)組 X 和 Y，遍歷 A[p…r]，將小于 pivot 的元素都拷貝到臨時(shí)數(shù)組 X，將大于 pivot 的元素都拷貝到臨時(shí)數(shù)組 Y，最后再將數(shù)組X 和數(shù)組 Y 中數(shù)據(jù)順序拷貝到 A[p…r]。

????????但是，如果按照這種思路實(shí)現(xiàn)的話，partition() 函數(shù)就需要很多額外的內(nèi)存空間，所以快排就不是原地排序算法了。如果我們希望快排是原地排序算法，那它的空間復(fù)雜度得是 O(1)，那 partition() 分區(qū)函數(shù)就不能占用太多額外的內(nèi)存空間，我們就需要在 A[p…r] 的原地完成分區(qū)操作。

? ? ? ? 原地分區(qū)函數(shù)的實(shí)現(xiàn)思路的偽代碼，也就是我們最后的實(shí)現(xiàn)思路：

? ? ? ? 圖片版的思路：

? ? ? ? 總結(jié)一下：

? ? ? ? 第一，快速排序是一種原地排序算法。

? ? ? ? 第二，快速排序是一種不穩(wěn)定的排序算法。

? ? ? ? 第三，快速排序的時(shí)間復(fù)雜度是O(nlogn)。如果每次分區(qū)操作，都能正好把數(shù)組分成大小接近相等的兩個(gè)小區(qū)間，那么快排的時(shí)間復(fù)雜度遞推求解公式跟歸并是相同的，但是這種情況是很難實(shí)現(xiàn)的。舉一個(gè)極端情況的例子，如果數(shù)組中的數(shù)據(jù)原來已經(jīng)是有序的了，比如，1,3,5,7,9，如果我們每次都選擇最后一個(gè)元素作為pivot，那么每次分區(qū)得到的兩個(gè)區(qū)間都是不均等的，我們需要進(jìn)行大約n次分區(qū)操作，才能完成整個(gè)快排的過程。每次分區(qū)我們平均要掃描大約n/2個(gè)元素，這種情況下快排的時(shí)間復(fù)雜度就退化成了O(n^2)。但是，快排在大部分情況下的時(shí)間復(fù)雜度都可以做到O(nlogn)，只有在極端情況下才會(huì)退化成O(n^2)。

? ? 3歸并排序和快速排序有什么區(qū)別？

? ? ? ? 可以發(fā)現(xiàn)，歸并排序的處理過程是由下到上的，先處理子問題，然后再合并。而快排的處理過程是由上到下的，先分區(qū)，再處理子問題。歸并雖然是穩(wěn)定的、時(shí)間復(fù)雜度也和快排相同，但是它不是原地排序算法，因?yàn)樗暮喜⒑瘮?shù)無法在原地執(zhí)行。而快排可以實(shí)現(xiàn)原地排序，解決了歸并排序占用太多內(nèi)存的問題。

? ? ? ? （遺留了一個(gè)怎樣找到一個(gè)數(shù)組中第K大元素的問題，下次復(fù)習(xí)的時(shí)候解決~）

????內(nèi)容小結(jié)

? ? ? ? 歸并排序和快速排序是兩種稍微復(fù)雜的排序算法，它們用的都是分治的思想，代碼都是通過遞歸來實(shí)現(xiàn)，過程非常相似。理解歸并排序的重點(diǎn)是理解遞推公式和merge()合并函數(shù)，理解快排的重點(diǎn)是理解遞推公式和partition()分區(qū)函數(shù)。歸并排序在任何情況下時(shí)間復(fù)雜度都比較穩(wěn)定，但它不是原地排序算法，空間復(fù)雜度比較高，所以沒有快排應(yīng)用廣泛。快排雖然最快情況下的時(shí)間復(fù)雜度比較高，但是平均情況下時(shí)間復(fù)雜度和歸并排序一樣，而且它退化到最壞情況時(shí)間復(fù)雜度的概率非常小，并且有避免的辦法。

? ? ? ? 戳這里查看源代碼。