那我們借用 cs50 里的例子布持,比如要把一摞卷子排好序莉炉,那用并歸排序的思想是怎么做的呢钓账?
- 首先把一摞卷子分成兩摞碴犬;
- 把每一摞排好序;
- 把排好序的兩摞再合并起來官扣。
感覺啥都沒說沙峻?
那是因為上面的過程里省略了很多細節(jié)猿挚,我們一個個來看。
首先分成兩摞的過程,均分拓颓,奇偶數(shù)無所謂竞穷,也就是多一個少一個的問題儡嘶;
那每一摞是怎么排好序的侧啼?
答案是用同樣的方法排好序。
- 排好序的兩摞是怎么合并起來的泪蔫?
這里需要借助兩個指針和額外的空間棒旗,然后左邊畫一個彩虹 ?? 右邊畫個龍 ??,不是撩荣,是左邊拿一個數(shù)铣揉,右邊拿一個數(shù),兩個比較大小之后排好序放回到數(shù)組里(至于放回原數(shù)組還是新數(shù)組稍后再說)餐曹。
這其實就是分治法 divide-and-conquer 的思想逛拱。
歸并排序是一個非常典型的例子。
分治法
顧名思義:分而治之台猴。
就是把一個大問題分解成相似的小問題朽合,通過解決這些小問題,再用小問題的解構(gòu)造大問題的解饱狂。
聽起來是不是和之前講遞歸的時候很像曹步?
沒錯,分治法基本都是可以用遞歸來實現(xiàn)的休讳。
在之前讲婚,我們沒有加以區(qū)分,當然現(xiàn)在我也認為不需要加以區(qū)分俊柔,但你如果非要問它們之間是什么區(qū)別磺樱,我的理解是:
- 遞歸是一種編程技巧,一個函數(shù)自己調(diào)用自己就是遞歸婆咸;
-
分治法是一種解決問題的思想:
- 把大的問題分解成小問題的這個過程就叫“分”,
- 解決小問題的過程就叫“治”芜辕,
- 解決小問題的方法往往是遞歸尚骄。
所以分治法的三大步驟是:
「分」:大問題分解成小問題;
「治」:用同樣的方法解決小問題侵续;
「合」:用小問題的解構(gòu)造大問題的解倔丈。
那回到我們的歸并排序上來:
「分」:把一個數(shù)組拆成兩個憨闰;
「治」:用歸并排序去排這兩個小數(shù)組;
「合」:把兩個排好序的小數(shù)組合并成大數(shù)組需五。
這里還有個問題鹉动,就是什么時候能夠解決小問題了?
答:當只剩一個元素的時候宏邮,直接返回就好了泽示,分解不了了。
這就是遞歸的 base case蜜氨,是要直接給出答案的械筛。
老例子:{5, 2, 1, 0}
暗示著齊姐對你們的愛啊~ ??
Step1.
先拆成兩半,
分成兩個數(shù)組:{5, 2} 和 {1, 0}
Step2.
沒到 base case飒炎,所以繼續(xù)把大問題分解成小問題:
當然了埋哟,雖然左右兩邊的拆分我都叫它 Step2,但是它們并不是同時發(fā)生的郎汪,我在遞歸那篇文章里有說原因赤赊,本質(zhì)上是由馮諾伊曼體系造成的,一個 CPU 在某一時間只能處理一件事煞赢,但我之所以都寫成 Step2抛计,是因為它們發(fā)生在同一層 call stack,這里就不在 IDE 里演示了耕驰,不明白的同學(xué)還是去看遞歸那篇文章里的演示吧爷辱。
Step3.
這一層都是一個元素了,是 base case朦肘,可以返回并合并了饭弓。
Step4.
合并的過程就是按大小順序來排好,這里借助兩個指針來比較媒抠,以及一個額外的數(shù)組來輔助完成弟断。
比如在最后一步時,數(shù)組已經(jīng)變成了:
{2, 5, 0, 1}趴生,
那么通過兩個指針 i 和 j阀趴,比較指針所指向元素的大小,把小的那個放到一個新的數(shù)組苍匆?里刘急,然后指針相應(yīng)的向右移動。
其實這里我們有兩個選擇:
- 一種是從新數(shù)組往原數(shù)組合并浸踩,
- 另一種就是從原數(shù)組往新數(shù)組里合并叔汁。
這個取決于題目要求的返回值類型是什么;以及在實際工作中,我們往往是希望改變當前的這個數(shù)組据块,把當前的這個數(shù)組排好序码邻,而不是返回一個新的數(shù)組,所以我們采取從新數(shù)組往原數(shù)組合并的方式另假,而不是把結(jié)果存在一個新的數(shù)組里像屋。
那具體怎么合并的,大家可以看下 15 秒的小動畫:
擋板左右兩邊是分別排好序的边篮,那么合并的過程就是利用兩個指針己莺,誰指的數(shù)字小,就把這個數(shù)放到結(jié)果里苟耻,然后移動指針篇恒,直到一方到頭(出界)。
public class MergeSort {
public void mergeSort(int[] array) {
if(array == null || array.length <= 1) {
return;
}
int[] newArray = new int[array.length];
mergeSort(array, 0, array.length-1, newArray);
}
private void mergeSort(int[] array, int left, int right, int[] newArray) {
// base case
if(left >= right) {
return;
}
// 「分」
int mid = left + (right - left)/2;
// 「治」
mergeSort(array, left, mid, newArray);
mergeSort(array, mid + 1, right, newArray);
// 輔助的 array
for(int i = left; i <= right; i++) {
newArray[i] = array[i];
}
// 「合」
int i = left;
int j = mid + 1;
int k = left;
while(i <= mid && j <= right) {
if(newArray[i] <= newArray[j]) { // 等號會影響算法的穩(wěn)定性
array[k++] = newArray[i++];
} else {
array[k++] = newArray[j++];
}
}
if(i <= mid) {
array[k++] = newArray[i++];
}
}
}
寫的不錯凶杖,我再來講一下:
首先定義 base case胁艰,否則就會成無限遞歸死循環(huán),那么這里是當未排序區(qū)間里只剩一個元素的時候返回智蝠,即左右擋板重合的時候腾么,或者沒有元素的時候返回。
「分」
然后定義小問題杈湾,先找到中點解虱,
- 那這里能不能寫成 (left+right)/2 呢?
- 注意 ??漆撞,是不可以的哦殴泰。
雖然數(shù)學(xué)上是一樣的,
但是這樣寫浮驳,
有可能出現(xiàn) integer overflow.
「治」
這樣我們拆好了左右兩個小問題悍汛,然后用“同樣的方法”解決這兩個自問題,這樣左右兩邊就都排好序了~
- 為什么敢說這兩邊都排好序了呢至会?
- 因為有數(shù)學(xué)歸納法在后面撐著~
那在這里离咐,能不能把它寫成:
mergeSort(array, left, mid-1, newArray);
mergeSort(array, mid, right, newArray);
也就是說,
- 左邊是 [left, mid-1]奉件,
- 右邊是 [mid, right]宵蛀,
這樣對不對呢?
答案是否定的县貌。
因為會造成無限遞歸术陶。
最簡單的,舉個兩個數(shù)的例子煤痕,比如數(shù)組為{1, 2}.
那么 left = 0, right = 1, mid = 0.
用這個方法拆分的數(shù)組就是:
- [0, -1], [0, 1] 即:
- 空集瞳别,{1, 2}
所以這樣來分并沒有縮小問題征候,沒有把大問題拆解成小問題,這樣的“分”是錯誤的祟敛,會出現(xiàn) stack overflow.
再深一層,究其根本原因兆解,是因為 Java 中的小數(shù)是「向零取整」
馆铁。
所以這里必須要寫成:
- 左邊是 [left, mid],
- 右邊是 [mid + 1, right]锅睛。
「合」
接下來就是合并的過程了埠巨。
在這里我們剛才說過了,要新開一個數(shù)組用來幫助合并现拒,那么最好是在上面的函數(shù)里開辣垒,然后把引用往下傳。開一個印蔬,反復(fù)用勋桶,這樣節(jié)省空間。
我們用兩個指針:i 和 j 指向新數(shù)組侥猬,指針 k 指向原數(shù)組例驹,開始剛才動畫里的移動過程。
要注意退唠,這里的等于號跟哪邊鹃锈,會影響這個排序算法的穩(wěn)定性。不清楚穩(wěn)定性的同學(xué)快去翻一下上一篇文章啦~
那像我代碼中這種寫法瞧预,指針 i 指的是左邊的元素屎债,遇到相等的元素也會先拷貝下來,所以左邊的元素一直在左邊垢油,維持了相對順序盆驹,所以就是穩(wěn)定的。
最后我們來分析下時空復(fù)雜度:
時間復(fù)雜度
歸并排序的過程涉及到遞歸秸苗,所以時空復(fù)雜度的分析稍微有點復(fù)雜召娜,在之前「遞歸」的那篇文章里我有提到,求解大問題的時間就是把所有求解子問題的時間加起來惊楼,再加上合并的時間玖瘸。
我們在遞歸樹中具體來看:
這里我右邊已經(jīng)寫出來了:
「分」的過程,每次的時間取決于有多少個小問題檀咙,可以看出來是
1雅倒,2,4弧可,8...這樣遞增的蔑匣,
那么加起來就是 O(n).
「合」的過程,每次都要用兩個指針走完全程,每一層的 call stack 加起來用時是 O(n)裁良,總共有 logn 層凿将,所以是 O(nlogn).
那么總的時間,就是 O(nlogn).
空間復(fù)雜度
其實歸并排序的空間復(fù)雜度和代碼怎么寫的有很大的關(guān)系价脾,所以我這里分析的空間復(fù)雜度是針對我上面這種寫法的牧抵。
要注意的是,遞歸的空間復(fù)雜度的分析并不能像時間復(fù)雜度那樣直接累加侨把,因為空間復(fù)雜度的定義是在程序運行過程中的使用空間的峰值犀变,本身就是一個峰值而非累加值的概念。
那也就是 call stack 中秋柄,所使用空間最高的時刻获枝,其實就是遞歸樹中最右邊的這條路線:它既要存著左邊排好序的那半邊結(jié)果,還要把右邊這半邊繼續(xù)排骇笔,總共是 O(n).
那有同學(xué)說 call stack 有 logn 層省店,為什么不是 O(logn),因為每層的使用的空間不是 O(1) 呀蜘拉。
擴展:外排序
這兩節(jié)介紹的排序算法都屬于內(nèi)部排序算法萨西,也就是排序的過程都是在內(nèi)存中完成。
但在實際工作中旭旭,當數(shù)據(jù)量特別大時谎脯,或者說比內(nèi)存容量還要大時,數(shù)據(jù)就無法一次性放入內(nèi)存中持寄,只能放在硬盤等外存儲器上源梭,這就需要用到外部排序算法算法來完成。一個典型的外排序算法就是外歸并排序(External Merge Sort)稍味。
這才是一道有意思的面試題废麻,在經(jīng)典算法的基礎(chǔ)上,加上實際工作中的限制條件模庐,和面試官探討的過程中烛愧,就能看出 candidate 的功力。
要解決這個問題掂碱,其實是要明確這里的限制條件是什么:
首先是內(nèi)存不夠怜姿。那除此之外,我們還想盡量少的進行硬盤的讀寫疼燥,因為很慢啊沧卢。
比如就拿wiki上的例子,要對 900MB 的數(shù)據(jù)進行排序醉者,但是內(nèi)存只有 100MB但狭,那么怎么排呢披诗?
- wiki 中給出的是讀 100MB 數(shù)據(jù)至內(nèi)存中,我并不贊同立磁,因為無論是歸并排序還是快排都是要費空間的呈队,剛說的空間復(fù)雜度 O(n) 不是,那數(shù)據(jù)把內(nèi)存都占滿了息罗,還怎么運行程序掂咒?那我建議比如就讀取 10MB 的數(shù)據(jù),那就相當于把 900MB 的數(shù)據(jù)分成了 90 份迈喉;
- 在內(nèi)存中排序完成后寫入磁盤;
- 把這 90 份數(shù)據(jù)都排好序温圆,那就會產(chǎn)生 90 個臨時文件挨摸;
- 用 k-way merge 對著 90 個文件進行合并,比如每次讀取每個文件中的 1MB 拿到內(nèi)存里來 merge岁歉,保證加起來是小于內(nèi)存容量且能保證程序能夠運行的得运。
那這是在一臺機器上的,如果數(shù)據(jù)量再大锅移,比如在一個分布式系統(tǒng)熔掺,那就需要用到 Map-Reduced 去做歸并排序,感興趣的同學(xué)就繼續(xù)關(guān)注我吧~
如果你喜歡這篇文章非剃,記得給我點贊留言哦~你們的支持和認可置逻,就是我創(chuàng)作的最大動力,我們下篇文章見备绽!
我是小齊券坞,紐約程序媛,終生學(xué)習(xí)者肺素,每天晚上 9 點恨锚,云自習(xí)室里不見不散!
更多干貨文章見我的 Github: https://github.com/xiaoqi6666/NYCSDE