排序（下）：如何用開(kāi)排思想在O（n）內(nèi)查找第K大元素
上一節(jié)我講了冒泡排序、插入排序、選擇排序這三種排序算法，它們的時(shí)間復(fù)雜度都是 O(n2)，比較高，適合小規(guī)模數(shù)據(jù)的排序。今天，我講兩種時(shí)間復(fù)雜度為 O(nlogn) 的排序算法，歸并排序和快速排序。這兩種排序算法適合大規(guī)模的數(shù)據(jù)排序，比上一節(jié)講的那三種排序算法要更常用。
歸并排序和快速排序都用到了分治思想，非常巧妙。我們可以借鑒這個(gè)思想，來(lái)解決非排序的問(wèn)題，比如：如何在 O(n) 的時(shí)間復(fù)雜度內(nèi)查找一個(gè)無(wú)序數(shù)組中的第 K 大元素？ 這就要用到我們今天要講的內(nèi)容。
歸并排序的原理
我們先來(lái)看歸并排序（Merge Sort）。
歸并排序的核心思想還是蠻簡(jiǎn)單的。如果要排序一個(gè)數(shù)組，我們先把數(shù)組從中間分成前后兩部分，然后對(duì)前后兩部分分別排序，再將排好序的兩部分合并在一起，這樣整個(gè)數(shù)組就都有序了。
歸并排序使用的就是分治思想。分治，顧名思義，就是分而治之，將一個(gè)大問(wèn)題分解成小的子問(wèn)題來(lái)解決。小的子問(wèn)題解決了，大問(wèn)題也就解決了。
從我剛才的描述，你有沒(méi)有感覺(jué)到，分治思想跟我們前面講的遞歸思想很像。是的，分治算法一般都是用遞歸來(lái)實(shí)現(xiàn)的。分治是一種解決問(wèn)題的處理思想，遞歸是一種編程技巧，這兩者并不沖突。分治算法的思想我后面會(huì)有專(zhuān)門(mén)的一節(jié)來(lái)講，現(xiàn)在不展開(kāi)討論，我們今天的重點(diǎn)還是排序算法。
前面我通過(guò)舉例讓你對(duì)歸并有了一個(gè)感性的認(rèn)識(shí)，又告訴你，歸并排序用的是分治思想，可以用遞歸來(lái)實(shí)現(xiàn)。我們現(xiàn)在就來(lái)看看如何用遞歸代碼來(lái)實(shí)現(xiàn)歸并排序。
我在第 10 節(jié)講的遞歸代碼的編寫(xiě)技巧你還記得嗎？寫(xiě)遞歸代碼的技巧就是，分析得出遞推公式，然后找到終止條件，最后將遞推公式翻譯成遞歸代碼。所以，要想寫(xiě)出歸并排序的代碼，我們先寫(xiě)出歸并排序的遞推公式。
遞推公式：
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))
終止條件：
p >= r 不用再繼續(xù)分解
我來(lái)解釋一下這個(gè)遞推公式。
merge_sort(p…r) 表示，給下標(biāo)從 p 到 r 之間的數(shù)組排序。我們將這個(gè)排序問(wèn)題轉(zhuǎn)化為了兩個(gè)子問(wèn)題，merge_sort(p…q) 和 merge_sort(q+1…r)，其中下標(biāo) q 等于 p 和 r 的中間位置，也就是 (p+r)/2。當(dāng)下標(biāo)從 p 到 q 和從 q+1 到 r 這兩個(gè)子數(shù)組都排好序之后，我們?cè)賹蓚€(gè)有序的子數(shù)組合并在一起，這樣下標(biāo)從 p 到 r 之間的數(shù)據(jù)就也排好序了。
有了遞推公式，轉(zhuǎn)化成代碼就簡(jiǎn)單多了。為了閱讀方便，我這里只給出偽代碼，你可以翻譯成你熟悉的編程語(yǔ)言。
// 歸并排序算法, A 是數(shù)組，n 表示數(shù)組大小
merge_sort(A, n) {
merge_sort_c(A, 0, n-1)
}
// 遞歸調(diào)用函數(shù)
merge_sort_c(A, p, r) {
// 遞歸終止條件
if p >= r then return
// 取 p 到 r 之間的中間位置 q
q = (p+r) / 2
// 分治遞歸
merge_sort_c(A, p, q)
merge_sort_c(A, q+1, r)
// 將 A[p...q] 和 A[q+1...r] 合并為 A[p...r]
merge(A[p...r], A[p...q], A[q+1...r])
}
你可能已經(jīng)發(fā)現(xiàn)了，merge(A[p…r], A[p…q], A[q+1…r]) 這個(gè)函數(shù)的作用就是，將已經(jīng)有序的 A[p…q] 和 A[q+1…r] 合并成一個(gè)有序的數(shù)組，并且放入 A[p…r]。那這個(gè)過(guò)程具體該如何做呢？
如圖所示，我們申請(qǐng)一個(gè)臨時(shí)數(shù)組 tmp，大小與 A[p…r] 相同。我們用兩個(gè)游標(biāo) i 和 j，分別指向 A[p…q] 和 A[q+1…r] 的第一個(gè)元素。比較這兩個(gè)元素 A[i] 和 A[j]，如果 A[i]<=A[j]，我們就把 A[i] 放入到臨時(shí)數(shù)組 tmp，并且 i 后移一位，否則將 A[j] 放入到數(shù)組 tmp，j 后移一位。
繼續(xù)上述比較過(guò)程，直到其中一個(gè)子數(shù)組中的所有數(shù)據(jù)都放入臨時(shí)數(shù)組中，再把另一個(gè)數(shù)組中的數(shù)據(jù)依次加入到臨時(shí)數(shù)組的末尾，這個(gè)時(shí)候，臨時(shí)數(shù)組中存儲(chǔ)的就是兩個(gè)子數(shù)組合并之后的結(jié)果了。最后再把臨時(shí)數(shù)組 tmp 中的數(shù)據(jù)拷貝到原數(shù)組 A[p…r] 中。
我們把 merge() 函數(shù)寫(xiě)成偽代碼，就是下面這樣：
merge(A[p...r], A[p...q], A[q+1...r]) {
var i := p，j := q+1，k := 0 // 初始化變量 i, j, k
var tmp := new array[0...r-p] // 申請(qǐng)一個(gè)大小跟 A[p...r] 一樣的臨時(shí)數(shù)組
while i<=q AND j<=r do {
if A[i] <= A[j] {
tmp[k++] = A[i++] // i++ 等于 i:=i+1
} else {
tmp[k++] = A[j++]
}
}
// 判斷哪個(gè)子數(shù)組中有剩余的數(shù)據(jù)
var start := i，end := q
if j<=r then start := j, end:=r
// 將剩余的數(shù)據(jù)拷貝到臨時(shí)數(shù)組 tmp
while start <= end do {
tmp[k++] = A[start++]
}
// 將 tmp 中的數(shù)組拷貝回 A[p...r]
for i:=0 to r-p do {
A[p+i] = tmp[i]
}
}
你還記得第 7 講講過(guò)的利用哨兵簡(jiǎn)化編程的處理技巧嗎？merge() 合并函數(shù)如果借助哨兵，代碼就會(huì)簡(jiǎn)潔很多，這個(gè)問(wèn)題留給你思考。
歸并排序的性能分析
這樣跟著我一步一步分析，歸并排序是不是沒(méi)那么難啦？還記得上節(jié)課我們分析排序算法的三個(gè)問(wèn)題嗎？接下來(lái)，我們來(lái)看歸并排序的三個(gè)問(wèn)題。
第一，歸并排序是穩(wěn)定的排序算法嗎？
結(jié)合我前面畫(huà)的那張圖和歸并排序的偽代碼，你應(yīng)該能發(fā)現(xiàn)，歸并排序穩(wěn)不穩(wěn)定關(guān)鍵要看 merge() 函數(shù)，也就是兩個(gè)有序子數(shù)組合并成一個(gè)有序數(shù)組的那部分代碼。
在合并的過(guò)程中，如果 A[p…q] 和 A[q+1…r] 之間有值相同的元素，那我們可以像偽代碼中那樣，先把 A[p…q] 中的元素放入 tmp 數(shù)組。這樣就保證了值相同的元素，在合并前后的先后順序不變。所以，歸并排序是一個(gè)穩(wěn)定的排序算法。
第二，歸并排序的時(shí)間復(fù)雜度是多少？
歸并排序涉及遞歸，時(shí)間復(fù)雜度的分析稍微有點(diǎn)復(fù)雜。我們正好借此機(jī)會(huì)來(lái)學(xué)習(xí)一下，如何分析遞歸代碼的時(shí)間復(fù)雜度。
在遞歸那一節(jié)我們講過(guò)，遞歸的適用場(chǎng)景是，一個(gè)問(wèn)題 a 可以分解為多個(gè)子問(wèn)題 b、c，那求解問(wèn)題 a 就可以分解為求解問(wèn)題 b、c。問(wèn)題 b、c 解決之后，我們?cè)侔?b、c 的結(jié)果合并成 a 的結(jié)果。
如果我們定義求解問(wèn)題 a 的時(shí)間是 T(a)，求解問(wèn)題 b、c 的時(shí)間分別是 T(b) 和 T( c)，那我們就可以得到這樣的遞推關(guān)系式：
T(a) = T(b) + T(c) + K
其中 K 等于將兩個(gè)子問(wèn)題 b、c 的結(jié)果合并成問(wèn)題 a 的結(jié)果所消耗的時(shí)間。
從剛剛的分析，我們可以得到一個(gè)重要的結(jié)論：不僅遞歸求解的問(wèn)題可以寫(xiě)成遞推公式，遞歸代碼的時(shí)間復(fù)雜度也可以寫(xiě)成遞推公式。
套用這個(gè)公式，我們來(lái)分析一下歸并排序的時(shí)間復(fù)雜度。
我們假設(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ì)算公式就是：
T(1) = C； n=1 時(shí)，只需要常量級(jí)的執(zhí)行時(shí)間，所以表示為 C。
T(n) = 2*T(n/2) + n； n>1
通過(guò)這個(gè)公式，如何來(lái)求解 T(n) 呢？還不夠直觀？那我們?cè)龠M(jìn)一步分解一下計(jì)算過(guò)程。
T(n) = 2*T(n/2) + n
= 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
= 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
= 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
......
= 2^k * T(n/2^k) + k * n
......
通過(guò)這樣一步一步分解推導(dǎo)，我們可以得到 T(n) = 2kT(n/2k)+kn。當(dāng) T(n/2^k)=T(1) 時(shí)，也就是 n/2^k=1，我們得到 k=log2n 。我們將 k 值代入上面的公式，得到 T(n)=Cn+nlog2n 。如果我們用大 O 標(biāo)記法來(lái)表示的話，T(n) 就等于 O(nlogn)。所以歸并排序的時(shí)間復(fù)雜度是 O(nlogn)。
從我們的原理分析和偽代碼可以看出，歸并排序的執(zhí)行效率與要排序的原始數(shù)組的有序程度無(wú)關(guān)，所以其時(shí)間復(fù)雜度是非常穩(wěn)定的，不管是最好情況、最壞情況，還是平均情況，時(shí)間復(fù)雜度都是 O(nlogn)。
第三，歸并排序的空間復(fù)雜度是多少？
歸并排序的時(shí)間復(fù)雜度任何情況下都是 O(nlogn)，看起來(lái)非常優(yōu)秀。（待會(huì)兒你會(huì)發(fā)現(xiàn)，即便是快速排序，最壞情況下，時(shí)間復(fù)雜度也是 。）但是，歸并排序并沒(méi)有像快排那樣，應(yīng)用廣泛，這是為什么呢？因?yàn)樗幸粋€(gè)致命的“弱點(diǎn)”，那就是歸并排序不是原地排序算法。
這是因?yàn)闅w并排序的合并函數(shù)，在合并兩個(gè)有序數(shù)組為一個(gè)有序數(shù)組時(shí)，需要借助額外的存儲(chǔ)空間。這一點(diǎn)你應(yīng)該很容易理解。那我現(xiàn)在問(wèn)你，歸并排序的空間復(fù)雜度到底是多少呢？是 O(n)，還是 O(nlogn)，應(yīng)該如何分析呢？
如果我們繼續(xù)按照分析遞歸時(shí)間復(fù)雜度的方法，通過(guò)遞推公式來(lái)求解，那整個(gè)歸并過(guò)程需要的空間復(fù)雜度就是 O(nlogn)。不過(guò)，類(lèi)似分析時(shí)間復(fù)雜度那樣來(lái)分析空間復(fù)雜度，這個(gè)思路對(duì)嗎？
實(shí)際上，遞歸代碼的空間復(fù)雜度并不能像時(shí)間復(fù)雜度那樣累加。剛剛我們忘記了最重要的一點(diǎn)，那就是，盡管每次合并操作都需要申請(qǐng)額外的內(nèi)存空間，但在合并完成之后，臨時(shí)開(kāi)辟的內(nèi)存空間就被釋放掉了。在任意時(shí)刻，CPU 只會(huì)有一個(gè)函數(shù)在執(zhí)行，也就只會(huì)有一個(gè)臨時(shí)的內(nèi)存空間在使用。臨時(shí)內(nèi)存空間最大也不會(huì)超過(guò) n 個(gè)數(shù)據(jù)的大小，所以空間復(fù)雜度是 O(n)。
快速排序的原理
我們?cè)賮?lái)看快速排序算法（Quicksort），我們習(xí)慣性把它簡(jiǎn)稱(chēng)為“快排”?？炫爬玫囊彩欠种嗡枷?。乍看起來(lái)，它有點(diǎn)像歸并排序，但是思路其實(shí)完全不一樣。我們待會(huì)會(huì)講兩者的區(qū)別?，F(xiàn)在，我們先來(lái)看下快排的核心思想。
快排的思想是這樣的：如果要排序數(shù)組中下標(biāo)從 p 到 r 之間的一組數(shù)據(jù)，我們選擇 p 到 r 之間的任意一個(gè)數(shù)據(jù)作為 pivot（分區(qū)點(diǎn)）。
我們遍歷 p 到 r 之間的數(shù)據(jù)，將小于 pivot 的放到左邊，將大于 pivot 的放到右邊，將 pivot 放到中間。經(jīng)過(guò)這一步驟之后，數(shù)組 p 到 r 之間的數(shù)據(jù)就被分成了三個(gè)部分，前面 p 到 q-1 之間都是小于 pivot 的，中間是 pivot，后面的 q+1 到 r 之間是大于 pivot 的。
根據(jù)分治、遞歸的處理思想，我們可以用遞歸排序下標(biāo)從 p 到 q-1 之間的數(shù)據(jù)和下標(biāo)從 q+1 到 r 之間的數(shù)據(jù)，直到區(qū)間縮小為 1，就說(shuō)明所有的數(shù)據(jù)都有序了。
如果我們用遞推公式來(lái)將上面的過(guò)程寫(xiě)出來(lái)的話，就是這樣：
遞推公式：
quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1, r)
終止條件：
p >= r
我將遞推公式轉(zhuǎn)化成遞歸代碼。跟歸并排序一樣，我還是用偽代碼來(lái)實(shí)現(xiàn)，你可以翻譯成你熟悉的任何語(yǔ)言。
// 快速排序，A 是數(shù)組，n 表示數(shù)組的大小
quick_sort(A, n) {
quick_sort_c(A, 0, n-1)
}
// 快速排序遞歸函數(shù)，p,r 為下標(biāo)
quick_sort_c(A, p, r) {
if p >= r then return
q = partition(A, p, r) // 獲取分區(qū)點(diǎn)
quick_sort_c(A, p, q-1)
quick_sort_c(A, q+1, r)
}
歸并排序中有一個(gè) merge() 合并函數(shù)，我們這里有一個(gè) partition() 分區(qū)函數(shù)。partition() 分區(qū)函數(shù)實(shí)際上我們前面已經(jīng)講過(guò)了，就是隨機(jī)選擇一個(gè)元素作為 pivot（一般情況下，可以選擇 p 到 r 區(qū)間的最后一個(gè)元素），然后對(duì) A[p…r] 分區(qū)，函數(shù)返回 pivot 的下標(biāo)。
如果我們不考慮空間消耗的話，partition() 分區(qū)函數(shù)可以寫(xiě)得非常簡(jiǎn)單。我們申請(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)思路非常巧妙，我寫(xiě)成了偽代碼，我們一起來(lái)看一下。
partition(A, p, r) {
pivot := A[r]
i := p
for j := p to r-1 do {
if A[j] < pivot {
swap A[i] with A[j]
i := i+1
}
}
swap A[i] with A[r]
return i
這里的處理有點(diǎn)類(lèi)似選擇排序。我們通過(guò)游標(biāo) i 把 A[p…r-1] 分成兩部分。A[p…i-1] 的元素都是小于 pivot 的，我們暫且叫它“已處理區(qū)間”，A[i…r-1] 是“未處理區(qū)間”。我們每次都從未處理的區(qū)間 A[i…r-1] 中取一個(gè)元素 A[j]，與 pivot 對(duì)比，如果小于 pivot，則將其加入到已處理區(qū)間的尾部，也就是 A[i] 的位置。
數(shù)組的插入操作還記得嗎？在數(shù)組某個(gè)位置插入元素，需要搬移數(shù)據(jù)，非常耗時(shí)。當(dāng)時(shí)我們也講了一種處理技巧，就是交換，在 O(1) 的時(shí)間復(fù)雜度內(nèi)完成插入操作。這里我們也借助這個(gè)思想，只需要將 A[i] 與 A[j] 交換，就可以在 O(1) 時(shí)間復(fù)雜度內(nèi)將 A[j] 放到下標(biāo)為 i 的位置。
文字不如圖直觀，所以我畫(huà)了一張圖來(lái)展示分區(qū)的整個(gè)過(guò)程。
因?yàn)榉謪^(qū)的過(guò)程涉及交換操作，如果數(shù)組中有兩個(gè) 8，其中一個(gè)是 pivot，經(jīng)過(guò)分區(qū)處理之后，后面的 8 就有可能被放到了另一個(gè) 8 的前面，先后順序就顛倒了。所以，快速排序并不是一個(gè)穩(wěn)定的排序算法。
到此，快速排序的原理你應(yīng)該也掌握了?，F(xiàn)在，我再來(lái)看另外一個(gè)問(wèn)題：快排和歸并用的都是分治思想，遞推公式和遞歸代碼也非常相似，那它們的區(qū)別在哪里呢？
可以發(fā)現(xiàn)，歸并排序的處理過(guò)程是由下到上的，先處理子問(wèn)題，然后再合并。而快排正好相反，它的處理過(guò)程是由上到下的，先分區(qū)，然后再處理子問(wèn)題。歸并排序雖然是穩(wěn)定的、時(shí)間復(fù)雜度為 O(nlogn) 的排序算法，但是它是非原地排序算法。我們前面講過(guò)，歸并之所以是非原地排序算法，主要原因是合并函數(shù)無(wú)法在原地執(zhí)行?？焖倥判蛲ㄟ^(guò)設(shè)計(jì)巧妙的原地分區(qū)函數(shù)，可以實(shí)現(xiàn)原地排序，解決了歸并排序占用太多內(nèi)存的問(wèn)題。
快速排序的性能分析
現(xiàn)在，我們來(lái)分析一下快速排序的性能。我在講解快排的實(shí)現(xiàn)原理的時(shí)候，已經(jīng)分析了穩(wěn)定性和空間復(fù)雜度。快排是一種原地、不穩(wěn)定的排序算法。現(xiàn)在，我們集中精力來(lái)看快排的時(shí)間復(fù)雜度。
快排也是用遞歸來(lái)實(shí)現(xiàn)的。對(duì)于遞歸代碼的時(shí)間復(fù)雜度，我前面總結(jié)的公式，這里也還是適用的。如果每次分區(qū)操作，都能正好把數(shù)組分成大小接近相等的兩個(gè)小區(qū)間，那快排的時(shí)間復(fù)雜度遞推求解公式跟歸并是相同的。所以，快排的時(shí)間復(fù)雜度也是 O(nlogn)。
T(1) = C； n=1 時(shí)，只需要常量級(jí)的執(zhí)行時(shí)間，所以表示為 C。
T(n) = 2*T(n/2) + n； n>1
但是，公式成立的前提是每次分區(qū)操作，我們選擇的 pivot 都很合適，正好能將大區(qū)間對(duì)等地一分為二。但實(shí)際上這種情況是很難實(shí)現(xiàn)的。
我舉一個(gè)比較極端的例子。如果數(shù)組中的數(shù)據(jù)原來(lái)已經(jīng)是有序的了，比如 1，3，5，6，8。如果我們每次選擇最后一個(gè)元素作為 pivot，那每次分區(qū)得到的兩個(gè)區(qū)間都是不均等的。我們需要進(jìn)行大約 n 次分區(qū)操作，才能完成快排的整個(gè)過(guò)程。每次分區(qū)我們平均要掃描大約 n/2 個(gè)元素，這種情況下，快排的時(shí)間復(fù)雜度就從 O(nlogn) 退化成了 O(n2)。
我們剛剛講了兩個(gè)極端情況下的時(shí)間復(fù)雜度，一個(gè)是分區(qū)極其均衡，一個(gè)是分區(qū)極其不均衡。它們分別對(duì)應(yīng)快排的最好情況時(shí)間復(fù)雜度和最壞情況時(shí)間復(fù)雜度。那快排的平均情況時(shí)間復(fù)雜度是多少呢？
我們假設(shè)每次分區(qū)操作都將區(qū)間分成大小為 9:1 的兩個(gè)小區(qū)間。我們繼續(xù)套用遞歸時(shí)間復(fù)雜度的遞推公式，就會(huì)變成這樣：
T(1) = C； n=1 時(shí)，只需要常量級(jí)的執(zhí)行時(shí)間，所以表示為 C。
T(n) = T(n/10) + T(9*n/10) + n； n>1
這個(gè)公式的遞推求解的過(guò)程非常復(fù)雜，雖然可以求解，但我不推薦用這種方法。實(shí)際上，遞歸的時(shí)間復(fù)雜度的求解方法除了遞推公式之外，還有遞歸樹(shù)，在樹(shù)那一節(jié)我再講，這里暫時(shí)不說(shuō)。我這里直接給你結(jié)論：T(n) 在大部分情況下的時(shí)間復(fù)雜度都可以做到 O(nlogn)，只有在極端情況下，才會(huì)退化到 O(n2)。而且，我們也有很多方法將這個(gè)概率降到很低，如何來(lái)做？我們后面章節(jié)再講。
解答開(kāi)篇
快排核心思想就是分治和分區(qū)，我們可以利用分區(qū)的思想，來(lái)解答開(kāi)篇的問(wèn)題：O(n) 時(shí)間復(fù)雜度內(nèi)求無(wú)序數(shù)組中的第 K 大元素。比如，4， 2， 5， 12， 3 這樣一組數(shù)據(jù)，第 3 大元素就是 4。
我們選擇數(shù)組區(qū)間 A[0…n-1] 的最后一個(gè)元素 A[n-1] 作為 pivot，對(duì)數(shù)組 A[0…n-1] 原地分區(qū)，這樣數(shù)組就分成了三部分，A[0…p-1]、A[p]、A[p+1…n-1]。
如果 p+1=K，那 A[p] 就是要求解的元素；如果 K>p+1, 說(shuō)明第 K 大元素出現(xiàn)在 A[p+1…n-1] 區(qū)間，我們?cè)侔凑丈厦娴乃悸愤f歸地在 A[p+1…n-1] 這個(gè)區(qū)間內(nèi)查找。同理，如果 K<p+1，那我們就在 A[0…p-1] 區(qū)間查找。
我們?cè)賮?lái)看，為什么上述解決思路的時(shí)間復(fù)雜度是 O(n)？
第一次分區(qū)查找，我們需要對(duì)大小為 n 的數(shù)組執(zhí)行分區(qū)操作，需要遍歷 n 個(gè)元素。第二次分區(qū)查找，我們只需要對(duì)大小為 n/2 的數(shù)組執(zhí)行分區(qū)操作，需要遍歷 n/2 個(gè)元素。依次類(lèi)推，分區(qū)遍歷元素的個(gè)數(shù)分別為、n/2、n/4、n/8、n/16.……直到區(qū)間縮小為 1。
如果我們把每次分區(qū)遍歷的元素個(gè)數(shù)加起來(lái)，就是：n+n/2+n/4+n/8+…+1。這是一個(gè)等比數(shù)列求和，最后的和等于 2n-1。所以，上述解決思路的時(shí)間復(fù)雜度就為 O(n)。
你可能會(huì)說(shuō)，我有個(gè)很笨的辦法，每次取數(shù)組中的最小值，將其移動(dòng)到數(shù)組的最前面，然后在剩下的數(shù)組中繼續(xù)找最小值，以此類(lèi)推，執(zhí)行 K 次，找到的數(shù)據(jù)不就是第 K 大元素了嗎？
不過(guò)，時(shí)間復(fù)雜度就并不是 O(n) 了，而是 O(K * n)。你可能會(huì)說(shuō)，時(shí)間復(fù)雜度前面的系數(shù)不是可以忽略嗎？O(K * n) 不就等于 O(n) 嗎？
這個(gè)可不能這么簡(jiǎn)單地劃等號(hào)。當(dāng) K 是比較小的常量時(shí)，比如 1、2，那最好時(shí)間復(fù)雜度確實(shí)是 O(n)；但當(dāng) K 等于 n/2 或者 n 時(shí)，這種壞情下的況時(shí)間復(fù)雜度就是 O(n2) 了。
內(nèi)容小結(jié)
歸并排序和快速排序是兩種稍微復(fù)雜的排序算法，它們用的都是分治的思想，代碼都通過(guò)遞歸來(lái)實(shí)現(xiàn)，過(guò)程非常相似。理解歸并排序的重點(diǎn)是理解遞推公式和 merge() 合并函數(shù)。同理，理解快排的重點(diǎn)也是理解遞推公式，還有 partition() 分區(qū)函數(shù)。
歸并排序算法是一種在任何情況下時(shí)間復(fù)雜度都比較穩(wěn)定的排序算法，這也使它存在致命的缺點(diǎn)，即歸并排序不是原地排序算法，空間復(fù)雜度比較高，是 O(n)。正因?yàn)榇?，它也沒(méi)有快排應(yīng)用廣泛。
快速排序算法雖然最壞情況下的時(shí)間復(fù)雜度是 O(n2)，但是平均情況下時(shí)間復(fù)雜度都是 O(nlogn)。不僅如此，快速排序算法時(shí)間復(fù)雜度退化到 O(n2) 的概率非常小，我們可以通過(guò)合理地選擇 pivot 來(lái)避免這種情況。
課后思考
現(xiàn)在你有 10 個(gè)接口訪問(wèn)日志文件，每個(gè)日志文件大小約 300MB，每個(gè)文件里的日志都是按照時(shí)間戳從小到大排序的。你希望將這 10 個(gè)較小的日志文件，合并為 1 個(gè)日志文件，合并之后的日志仍然按照時(shí)間戳從小到大排列。如果處理上述排序任務(wù)的機(jī)器內(nèi)存只有 1GB，你有什么好的解決思路，能“快速”地將這 10 個(gè)日志文件合并嗎？
