排序（下）：如何用開排思想在O（n）內(nèi)查找第K大元素
上一節(jié)我講了冒泡排序滨巴、插入排序思灌、選擇排序這三種排序算法，它們的時間復(fù)雜度都是 O(n2)恭取，比較高泰偿，適合小規(guī)模數(shù)據(jù)的排序。今天蜈垮，我講兩種時間復(fù)雜度為 O(nlogn) 的排序算法耗跛，歸并排序和快速排序。這兩種排序算法適合大規(guī)模的數(shù)據(jù)排序窃款，比上一節(jié)講的那三種排序算法要更常用课兄。
歸并排序和快速排序都用到了分治思想，非常巧妙晨继。我們可以借鑒這個思想烟阐，來解決非排序的問題，比如：如何在 O(n) 的時間復(fù)雜度內(nèi)查找一個無序數(shù)組中的第 K 大元素紊扬？ 這就要用到我們今天要講的內(nèi)容蜒茄。
歸并排序的原理
我們先來看歸并排序（Merge Sort）。
歸并排序的核心思想還是蠻簡單的餐屎。如果要排序一個數(shù)組檀葛，我們先把數(shù)組從中間分成前后兩部分，然后對前后兩部分分別排序腹缩，再將排好序的兩部分合并在一起屿聋，這樣整個數(shù)組就都有序了空扎。
歸并排序使用的就是分治思想。分治润讥，顧名思義转锈，就是分而治之，將一個大問題分解成小的子問題來解決楚殿。小的子問題解決了撮慨，大問題也就解決了。
從我剛才的描述脆粥，你有沒有感覺到砌溺，分治思想跟我們前面講的遞歸思想很像。是的变隔，分治算法一般都是用遞歸來實現(xiàn)的规伐。分治是一種解決問題的處理思想，遞歸是一種編程技巧弟胀，這兩者并不沖突楷力。分治算法的思想我后面會有專門的一節(jié)來講，現(xiàn)在不展開討論孵户，我們今天的重點還是排序算法萧朝。
前面我通過舉例讓你對歸并有了一個感性的認識，又告訴你夏哭，歸并排序用的是分治思想检柬，可以用遞歸來實現(xiàn)。我們現(xiàn)在就來看看如何用遞歸代碼來實現(xiàn)歸并排序竖配。
我在第 10 節(jié)講的遞歸代碼的編寫技巧你還記得嗎何址？寫遞歸代碼的技巧就是，分析得出遞推公式进胯，然后找到終止條件用爪，最后將遞推公式翻譯成遞歸代碼。所以胁镐，要想寫出歸并排序的代碼偎血，我們先寫出歸并排序的遞推公式。
遞推公式：
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))
終止條件：
p >= r 不用再繼續(xù)分解
我來解釋一下這個遞推公式盯漂。
merge_sort(p…r) 表示颇玷，給下標從 p 到 r 之間的數(shù)組排序。我們將這個排序問題轉(zhuǎn)化為了兩個子問題就缆，merge_sort(p…q) 和 merge_sort(q+1…r)帖渠，其中下標 q 等于 p 和 r 的中間位置，也就是 (p+r)/2竭宰。當下標從 p 到 q 和從 q+1 到 r 這兩個子數(shù)組都排好序之后空郊，我們再將兩個有序的子數(shù)組合并在一起份招，這樣下標從 p 到 r 之間的數(shù)據(jù)就也排好序了。
有了遞推公式渣淳，轉(zhuǎn)化成代碼就簡單多了脾还。為了閱讀方便，我這里只給出偽代碼入愧，你可以翻譯成你熟悉的編程語言。
// 歸并排序算法, 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]) 這個函數(shù)的作用就是，將已經(jīng)有序的 A[p…q] 和 A[q+1…r] 合并成一個有序的數(shù)組巩步，并且放入 A[p…r]旁赊。那這個過程具體該如何做呢？
如圖所示椅野，我們申請一個臨時數(shù)組 tmp终畅，大小與 A[p…r] 相同。我們用兩個游標 i 和 j竟闪，分別指向 A[p…q] 和 A[q+1…r] 的第一個元素离福。比較這兩個元素 A[i] 和 A[j]，如果 A[i]<=A[j]炼蛤，我們就把 A[i] 放入到臨時數(shù)組 tmp妖爷，并且 i 后移一位，否則將 A[j] 放入到數(shù)組 tmp理朋，j 后移一位絮识。
繼續(xù)上述比較過程，直到其中一個子數(shù)組中的所有數(shù)據(jù)都放入臨時數(shù)組中嗽上，再把另一個數(shù)組中的數(shù)據(jù)依次加入到臨時數(shù)組的末尾次舌，這個時候，臨時數(shù)組中存儲的就是兩個子數(shù)組合并之后的結(jié)果了兽愤。最后再把臨時數(shù)組 tmp 中的數(shù)據(jù)拷貝到原數(shù)組 A[p…r] 中彼念。
我們把 merge() 函數(shù)寫成偽代碼，就是下面這樣：
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] // 申請一個大小跟 A[p...r] 一樣的臨時數(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++]
}
}
// 判斷哪個子數(shù)組中有剩余的數(shù)據(jù)
var start := i，end := q
if j<=r then start := j, end:=r
// 將剩余的數(shù)據(jù)拷貝到臨時數(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 講講過的利用哨兵簡化編程的處理技巧嗎惯殊？merge() 合并函數(shù)如果借助哨兵酱吝，代碼就會簡潔很多，這個問題留給你思考土思。
歸并排序的性能分析
這樣跟著我一步一步分析务热，歸并排序是不是沒那么難啦忆嗜？還記得上節(jié)課我們分析排序算法的三個問題嗎？接下來崎岂，我們來看歸并排序的三個問題捆毫。
第一，歸并排序是穩(wěn)定的排序算法嗎冲甘？
結(jié)合我前面畫的那張圖和歸并排序的偽代碼绩卤，你應(yīng)該能發(fā)現(xiàn)，歸并排序穩(wěn)不穩(wěn)定關(guān)鍵要看 merge() 函數(shù)江醇，也就是兩個有序子數(shù)組合并成一個有序數(shù)組的那部分代碼濒憋。
在合并的過程中，如果 A[p…q] 和 A[q+1…r] 之間有值相同的元素陶夜，那我們可以像偽代碼中那樣凛驮，先把 A[p…q] 中的元素放入 tmp 數(shù)組。這樣就保證了值相同的元素条辟，在合并前后的先后順序不變黔夭。所以，歸并排序是一個穩(wěn)定的排序算法羽嫡。
第二本姥，歸并排序的時間復(fù)雜度是多少？
歸并排序涉及遞歸厂僧，時間復(fù)雜度的分析稍微有點復(fù)雜扣草。我們正好借此機會來學(xué)習(xí)一下，如何分析遞歸代碼的時間復(fù)雜度颜屠。
在遞歸那一節(jié)我們講過辰妙，遞歸的適用場景是，一個問題 a 可以分解為多個子問題 b甫窟、c密浑，那求解問題 a 就可以分解為求解問題 b、c粗井。問題 b尔破、c 解決之后，我們再把 b浇衬、c 的結(jié)果合并成 a 的結(jié)果懒构。
如果我們定義求解問題 a 的時間是 T(a)，求解問題 b耘擂、c 的時間分別是 T(b) 和 T( c)胆剧，那我們就可以得到這樣的遞推關(guān)系式：
T(a) = T(b) + T(c) + K
其中 K 等于將兩個子問題 b、c 的結(jié)果合并成問題 a 的結(jié)果所消耗的時間。
從剛剛的分析秩霍，我們可以得到一個重要的結(jié)論：不僅遞歸求解的問題可以寫成遞推公式篙悯，遞歸代碼的時間復(fù)雜度也可以寫成遞推公式。
套用這個公式铃绒，我們來分析一下歸并排序的時間復(fù)雜度鸽照。
我們假設(shè)對 n 個元素進行歸并排序需要的時間是 T(n)，那分解成兩個子數(shù)組排序的時間都是 T(n/2)颠悬。我們知道矮燎，merge() 函數(shù)合并兩個有序子數(shù)組的時間復(fù)雜度是 O(n)。所以赔癌，套用前面的公式漏峰，歸并排序的時間復(fù)雜度的計算公式就是：
T(1) = C； n=1 時届榄，只需要常量級的執(zhí)行時間，所以表示為 C倔喂。
T(n) = 2*T(n/2) + n铝条； n>1
通過這個公式，如何來求解 T(n) 呢席噩？還不夠直觀班缰？那我們再進一步分解一下計算過程。
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
......
通過這樣一步一步分解推導(dǎo)悼枢，我們可以得到 T(n) = 2kT(n/2k)+kn埠忘。當 T(n/2^k)=T(1) 時，也就是 n/2^k=1馒索，我們得到 k=log2n 莹妒。我們將 k 值代入上面的公式，得到 T(n)=Cn+nlog2n 绰上。如果我們用大 O 標記法來表示的話旨怠，T(n) 就等于 O(nlogn)。所以歸并排序的時間復(fù)雜度是 O(nlogn)蜈块。
從我們的原理分析和偽代碼可以看出鉴腻，歸并排序的執(zhí)行效率與要排序的原始數(shù)組的有序程度無關(guān)，所以其時間復(fù)雜度是非常穩(wěn)定的百揭，不管是最好情況爽哎、最壞情況，還是平均情況器一，時間復(fù)雜度都是 O(nlogn)课锌。
第三，歸并排序的空間復(fù)雜度是多少盹舞？
歸并排序的時間復(fù)雜度任何情況下都是 O(nlogn)产镐，看起來非常優(yōu)秀隘庄。（待會兒你會發(fā)現(xiàn)，即便是快速排序癣亚，最壞情況下丑掺，時間復(fù)雜度也是 。）但是述雾，歸并排序并沒有像快排那樣街州，應(yīng)用廣泛，這是為什么呢玻孟？因為它有一個致命的“弱點”唆缴，那就是歸并排序不是原地排序算法。
這是因為歸并排序的合并函數(shù)黍翎，在合并兩個有序數(shù)組為一個有序數(shù)組時面徽，需要借助額外的存儲空間。這一點你應(yīng)該很容易理解匣掸。那我現(xiàn)在問你趟紊，歸并排序的空間復(fù)雜度到底是多少呢？是 O(n)碰酝，還是 O(nlogn)霎匈，應(yīng)該如何分析呢？
如果我們繼續(xù)按照分析遞歸時間復(fù)雜度的方法送爸，通過遞推公式來求解铛嘱，那整個歸并過程需要的空間復(fù)雜度就是 O(nlogn)。不過袭厂，類似分析時間復(fù)雜度那樣來分析空間復(fù)雜度墨吓，這個思路對嗎？
實際上嵌器，遞歸代碼的空間復(fù)雜度并不能像時間復(fù)雜度那樣累加肛真。剛剛我們忘記了最重要的一點，那就是爽航，盡管每次合并操作都需要申請額外的內(nèi)存空間蚓让，但在合并完成之后，臨時開辟的內(nèi)存空間就被釋放掉了讥珍。在任意時刻历极，CPU 只會有一個函數(shù)在執(zhí)行，也就只會有一個臨時的內(nèi)存空間在使用衷佃。臨時內(nèi)存空間最大也不會超過 n 個數(shù)據(jù)的大小趟卸，所以空間復(fù)雜度是 O(n)。
快速排序的原理
我們再來看快速排序算法（Quicksort），我們習(xí)慣性把它簡稱為“快排”锄列⊥荚疲快排利用的也是分治思想。乍看起來邻邮，它有點像歸并排序竣况，但是思路其實完全不一樣。我們待會會講兩者的區(qū)別⊥惭希現(xiàn)在丹泉，我們先來看下快排的核心思想。
快排的思想是這樣的：如果要排序數(shù)組中下標從 p 到 r 之間的一組數(shù)據(jù)鸭蛙，我們選擇 p 到 r 之間的任意一個數(shù)據(jù)作為 pivot（分區(qū)點）摹恨。
我們遍歷 p 到 r 之間的數(shù)據(jù)，將小于 pivot 的放到左邊娶视，將大于 pivot 的放到右邊晒哄，將 pivot 放到中間。經(jīng)過這一步驟之后肪获，數(shù)組 p 到 r 之間的數(shù)據(jù)就被分成了三個部分揩晴，前面 p 到 q-1 之間都是小于 pivot 的，中間是 pivot贪磺，后面的 q+1 到 r 之間是大于 pivot 的。
根據(jù)分治诅愚、遞歸的處理思想寒锚，我們可以用遞歸排序下標從 p 到 q-1 之間的數(shù)據(jù)和下標從 q+1 到 r 之間的數(shù)據(jù)，直到區(qū)間縮小為 1违孝，就說明所有的數(shù)據(jù)都有序了刹前。
如果我們用遞推公式來將上面的過程寫出來的話，就是這樣：
遞推公式：
quick_sort(p…r) = quick_sort(p…q-1) + quick_sort(q+1, r)
終止條件：
p >= r
我將遞推公式轉(zhuǎn)化成遞歸代碼雌桑。跟歸并排序一樣喇喉，我還是用偽代碼來實現(xiàn)，你可以翻譯成你熟悉的任何語言校坑。
// 快速排序拣技，A 是數(shù)組，n 表示數(shù)組的大小
quick_sort(A, n) {
quick_sort_c(A, 0, n-1)
}
// 快速排序遞歸函數(shù)耍目，p,r 為下標
quick_sort_c(A, p, r) {
if p >= r then return
q = partition(A, p, r) // 獲取分區(qū)點
quick_sort_c(A, p, q-1)
quick_sort_c(A, q+1, r)
}
歸并排序中有一個 merge() 合并函數(shù)膏斤，我們這里有一個 partition() 分區(qū)函數(shù)。partition() 分區(qū)函數(shù)實際上我們前面已經(jīng)講過了邪驮，就是隨機選擇一個元素作為 pivot（一般情況下莫辨，可以選擇 p 到 r 區(qū)間的最后一個元素），然后對 A[p…r] 分區(qū)，函數(shù)返回 pivot 的下標沮榜。
如果我們不考慮空間消耗的話盘榨，partition() 分區(qū)函數(shù)可以寫得非常簡單。我們申請兩個臨時數(shù)組 X 和 Y蟆融，遍歷 A[p…r]草巡，將小于 pivot 的元素都拷貝到臨時數(shù)組 X，將大于 pivot 的元素都拷貝到臨時數(shù)組 Y振愿，最后再將數(shù)組 X 和數(shù)組 Y 中數(shù)據(jù)順序拷貝到 A[p…r]捷犹。
但是，如果按照這種思路實現(xiàn)的話冕末，partition() 函數(shù)就需要很多額外的內(nèi)存空間萍歉，所以快排就不是原地排序算法了。如果我們希望快排是原地排序算法档桃，那它的空間復(fù)雜度得是 O(1)枪孩，那 partition() 分區(qū)函數(shù)就不能占用太多額外的內(nèi)存空間，我們就需要在 A[p…r] 的原地完成分區(qū)操作藻肄。
原地分區(qū)函數(shù)的實現(xiàn)思路非常巧妙蔑舞，我寫成了偽代碼，我們一起來看一下嘹屯。
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
這里的處理有點類似選擇排序攻询。我們通過游標 i 把 A[p…r-1] 分成兩部分。A[p…i-1] 的元素都是小于 pivot 的州弟，我們暫且叫它“已處理區(qū)間”钧栖，A[i…r-1] 是“未處理區(qū)間”。我們每次都從未處理的區(qū)間 A[i…r-1] 中取一個元素 A[j]婆翔，與 pivot 對比拯杠，如果小于 pivot，則將其加入到已處理區(qū)間的尾部啃奴，也就是 A[i] 的位置潭陪。
數(shù)組的插入操作還記得嗎？在數(shù)組某個位置插入元素最蕾，需要搬移數(shù)據(jù)依溯，非常耗時。當時我們也講了一種處理技巧瘟则，就是交換誓沸，在 O(1) 的時間復(fù)雜度內(nèi)完成插入操作。這里我們也借助這個思想壹粟，只需要將 A[i] 與 A[j] 交換拜隧，就可以在 O(1) 時間復(fù)雜度內(nèi)將 A[j] 放到下標為 i 的位置宿百。
文字不如圖直觀，所以我畫了一張圖來展示分區(qū)的整個過程洪添。
因為分區(qū)的過程涉及交換操作拭宁，如果數(shù)組中有兩個 8镇匀，其中一個是 pivot男翰，經(jīng)過分區(qū)處理之后糯彬，后面的 8 就有可能被放到了另一個 8 的前面，先后順序就顛倒了忿峻。所以薄啥，快速排序并不是一個穩(wěn)定的排序算法。
到此逛尚，快速排序的原理你應(yīng)該也掌握了÷⒕澹現(xiàn)在，我再來看另外一個問題：快排和歸并用的都是分治思想绰寞，遞推公式和遞歸代碼也非常相似到逊，那它們的區(qū)別在哪里呢？
可以發(fā)現(xiàn)滤钱，歸并排序的處理過程是由下到上的觉壶，先處理子問題，然后再合并件缸。而快排正好相反铜靶，它的處理過程是由上到下的，先分區(qū)他炊，然后再處理子問題旷坦。歸并排序雖然是穩(wěn)定的、時間復(fù)雜度為 O(nlogn) 的排序算法佑稠，但是它是非原地排序算法。我們前面講過旗芬，歸并之所以是非原地排序算法舌胶，主要原因是合并函數(shù)無法在原地執(zhí)行〈裕快速排序通過設(shè)計巧妙的原地分區(qū)函數(shù)幔嫂，可以實現(xiàn)原地排序，解決了歸并排序占用太多內(nèi)存的問題誊薄。
快速排序的性能分析
現(xiàn)在履恩，我們來分析一下快速排序的性能。我在講解快排的實現(xiàn)原理的時候呢蔫，已經(jīng)分析了穩(wěn)定性和空間復(fù)雜度切心§快排是一種原地、不穩(wěn)定的排序算法≌阑瑁現(xiàn)在协屡，我們集中精力來看快排的時間復(fù)雜度。
快排也是用遞歸來實現(xiàn)的全谤。對于遞歸代碼的時間復(fù)雜度肤晓，我前面總結(jié)的公式，這里也還是適用的认然。如果每次分區(qū)操作补憾，都能正好把數(shù)組分成大小接近相等的兩個小區(qū)間，那快排的時間復(fù)雜度遞推求解公式跟歸并是相同的卷员。所以盈匾，快排的時間復(fù)雜度也是 O(nlogn)。
T(1) = C子刮； n=1 時威酒，只需要常量級的執(zhí)行時間，所以表示為 C挺峡。
T(n) = 2*T(n/2) + n葵孤； n>1
但是，公式成立的前提是每次分區(qū)操作橱赠，我們選擇的 pivot 都很合適尤仍，正好能將大區(qū)間對等地一分為二。但實際上這種情況是很難實現(xiàn)的狭姨。
我舉一個比較極端的例子宰啦。如果數(shù)組中的數(shù)據(jù)原來已經(jīng)是有序的了，比如 1饼拍，3赡模，5，6师抄，8漓柑。如果我們每次選擇最后一個元素作為 pivot，那每次分區(qū)得到的兩個區(qū)間都是不均等的叨吮。我們需要進行大約 n 次分區(qū)操作辆布，才能完成快排的整個過程。每次分區(qū)我們平均要掃描大約 n/2 個元素茶鉴，這種情況下锋玲，快排的時間復(fù)雜度就從 O(nlogn) 退化成了 O(n2)。
我們剛剛講了兩個極端情況下的時間復(fù)雜度涵叮，一個是分區(qū)極其均衡惭蹂，一個是分區(qū)極其不均衡伞插。它們分別對應(yīng)快排的最好情況時間復(fù)雜度和最壞情況時間復(fù)雜度。那快排的平均情況時間復(fù)雜度是多少呢剿干？
我們假設(shè)每次分區(qū)操作都將區(qū)間分成大小為 9:1 的兩個小區(qū)間蜂怎。我們繼續(xù)套用遞歸時間復(fù)雜度的遞推公式，就會變成這樣：
T(1) = C置尔； n=1 時杠步，只需要常量級的執(zhí)行時間，所以表示為 C榜轿。
T(n) = T(n/10) + T(9*n/10) + n幽歼； n>1
這個公式的遞推求解的過程非常復(fù)雜，雖然可以求解谬盐，但我不推薦用這種方法甸私。實際上，遞歸的時間復(fù)雜度的求解方法除了遞推公式之外飞傀，還有遞歸樹皇型，在樹那一節(jié)我再講，這里暫時不說砸烦。我這里直接給你結(jié)論：T(n) 在大部分情況下的時間復(fù)雜度都可以做到 O(nlogn)弃鸦，只有在極端情況下，才會退化到 O(n2)幢痘。而且唬格，我們也有很多方法將這個概率降到很低，如何來做颜说？我們后面章節(jié)再講购岗。
解答開篇
快排核心思想就是分治和分區(qū)，我們可以利用分區(qū)的思想门粪，來解答開篇的問題：O(n) 時間復(fù)雜度內(nèi)求無序數(shù)組中的第 K 大元素喊积。比如，4玄妈， 2乾吻， 5， 12措近， 3 這樣一組數(shù)據(jù)，第 3 大元素就是 4女淑。
我們選擇數(shù)組區(qū)間 A[0…n-1] 的最后一個元素 A[n-1] 作為 pivot瞭郑，對數(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, 說明第 K 大元素出現(xiàn)在 A[p+1…n-1] 區(qū)間，我們再按照上面的思路遞歸地在 A[p+1…n-1] 這個區(qū)間內(nèi)查找场绿。同理剖效，如果 K<p+1，那我們就在 A[0…p-1] 區(qū)間查找焰盗。
我們再來看璧尸，為什么上述解決思路的時間復(fù)雜度是 O(n)？
第一次分區(qū)查找熬拒，我們需要對大小為 n 的數(shù)組執(zhí)行分區(qū)操作爷光，需要遍歷 n 個元素澎粟。第二次分區(qū)查找徐裸，我們只需要對大小為 n/2 的數(shù)組執(zhí)行分區(qū)操作宫补，需要遍歷 n/2 個元素健民。依次類推秉犹，分區(qū)遍歷元素的個數(shù)分別為崇堵、n/2也搓、n/4幔摸、n/8驱负、n/16.……直到區(qū)間縮小為 1。
如果我們把每次分區(qū)遍歷的元素個數(shù)加起來，就是：n+n/2+n/4+n/8+…+1。這是一個等比數(shù)列求和咧七，最后的和等于 2n-1。所以，上述解決思路的時間復(fù)雜度就為 O(n)墨辛。
你可能會說，我有個很笨的辦法，每次取數(shù)組中的最小值，將其移動到數(shù)組的最前面嗽元，然后在剩下的數(shù)組中繼續(xù)找最小值翰绊，以此類推谐檀，執(zhí)行 K 次，找到的數(shù)據(jù)不就是第 K 大元素了嗎？
不過，時間復(fù)雜度就并不是 O(n) 了厨钻，而是 O(K * n)惶傻。你可能會說涂佃，時間復(fù)雜度前面的系數(shù)不是可以忽略嗎抓狭？O(K * n) 不就等于 O(n) 嗎？
這個可不能這么簡單地劃等號。當 K 是比較小的常量時癌佩，比如 1木缝、2，那最好時間復(fù)雜度確實是 O(n)围辙；但當 K 等于 n/2 或者 n 時我碟，這種壞情下的況時間復(fù)雜度就是 O(n2) 了。
內(nèi)容小結(jié)
歸并排序和快速排序是兩種稍微復(fù)雜的排序算法姚建，它們用的都是分治的思想矫俺，代碼都通過遞歸來實現(xiàn)，過程非常相似掸冤。理解歸并排序的重點是理解遞推公式和 merge() 合并函數(shù)恳守。同理，理解快排的重點也是理解遞推公式贩虾，還有 partition() 分區(qū)函數(shù)催烘。
歸并排序算法是一種在任何情況下時間復(fù)雜度都比較穩(wěn)定的排序算法，這也使它存在致命的缺點缎罢，即歸并排序不是原地排序算法伊群，空間復(fù)雜度比較高，是 O(n)策精。正因為此舰始，它也沒有快排應(yīng)用廣泛。
快速排序算法雖然最壞情況下的時間復(fù)雜度是 O(n2)咽袜，但是平均情況下時間復(fù)雜度都是 O(nlogn)丸卷。不僅如此，快速排序算法時間復(fù)雜度退化到 O(n2) 的概率非常小询刹，我們可以通過合理地選擇 pivot 來避免這種情況谜嫉。
課后思考
現(xiàn)在你有 10 個接口訪問日志文件，每個日志文件大小約 300MB凹联，每個文件里的日志都是按照時間戳從小到大排序的沐兰。你希望將這 10 個較小的日志文件，合并為 1 個日志文件蔽挠，合并之后的日志仍然按照時間戳從小到大排列住闯。如果處理上述排序任務(wù)的機器內(nèi)存只有 1GB，你有什么好的解決思路，能“快速”地將這 10 個日志文件合并嗎比原？
