史上最清晰的「歸并排序」講解

那我們借用 cs50 里的例子布持,比如要把一摞卷子排好序莉炉,那用并歸排序的思想是怎么做的呢钓账?

  1. 首先把一摞卷子分成兩摞碴犬;
  2. 把每一摞排好序;
  3. 把排好序的兩摞再合并起來官扣。

感覺啥都沒說沙峻?
那是因為上面的過程里省略了很多細節(jié)猿挚,我們一個個來看。

  1. 首先分成兩摞的過程,均分拓颓,奇偶數(shù)無所謂竞穷,也就是多一個少一個的問題儡嘶;

  2. 那每一摞是怎么排好序的侧啼?

答案是用同樣的方法排好序。

  1. 排好序的兩摞是怎么合并起來的泪蔫?

這里需要借助兩個指針和額外的空間棒旗,然后左邊畫一個彩虹 ?? 右邊畫個龍 ??,不是撩荣,是左邊拿一個數(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但狭,那么怎么排呢披诗?

  1. wiki 中給出的是讀 100MB 數(shù)據(jù)至內(nèi)存中,我并不贊同立磁,因為無論是歸并排序還是快排都是要費空間的呈队,剛說的空間復(fù)雜度 O(n) 不是,那數(shù)據(jù)把內(nèi)存都占滿了息罗,還怎么運行程序掂咒?那我建議比如就讀取 10MB 的數(shù)據(jù),那就相當于把 900MB 的數(shù)據(jù)分成了 90 份迈喉;
  2. 在內(nèi)存中排序完成后寫入磁盤;
  3. 把這 90 份數(shù)據(jù)都排好序温圆,那就會產(chǎn)生 90 個臨時文件挨摸;
  4. 用 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

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末倍靡,一起剝皮案震驚了整個濱河市猴伶,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌塌西,老刑警劉巖他挎,帶你破解...
    沈念sama閱讀 207,248評論 6 481
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異雨让,居然都是意外死亡雇盖,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 88,681評論 2 381
  • 文/潘曉璐 我一進店門栖忠,熙熙樓的掌柜王于貴愁眉苦臉地迎上來崔挖,“玉大人贸街,你說我怎么就攤上這事±晗啵” “怎么了薛匪?”我有些...
    開封第一講書人閱讀 153,443評論 0 344
  • 文/不壞的土叔 我叫張陵,是天一觀的道長脓鹃。 經(jīng)常有香客問我逸尖,道長,這世上最難降的妖魔是什么瘸右? 我笑而不...
    開封第一講書人閱讀 55,475評論 1 279
  • 正文 為了忘掉前任娇跟,我火速辦了婚禮,結(jié)果婚禮上太颤,老公的妹妹穿的比我還像新娘苞俘。我一直安慰自己,他們只是感情好龄章,可當我...
    茶點故事閱讀 64,458評論 5 374
  • 文/花漫 我一把揭開白布吃谣。 她就那樣靜靜地躺著,像睡著了一般做裙。 火紅的嫁衣襯著肌膚如雪岗憋。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 49,185評論 1 284
  • 那天锚贱,我揣著相機與錄音仔戈,去河邊找鬼。 笑死惋鸥,一個胖子當著我的面吹牛杂穷,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播卦绣,決...
    沈念sama閱讀 38,451評論 3 401
  • 文/蒼蘭香墨 我猛地睜開眼耐量,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了滤港?” 一聲冷哼從身側(cè)響起廊蜒,我...
    開封第一講書人閱讀 37,112評論 0 261
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎溅漾,沒想到半個月后山叮,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 43,609評論 1 300
  • 正文 獨居荒郊野嶺守林人離奇死亡添履,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 36,083評論 2 325
  • 正文 我和宋清朗相戀三年屁倔,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片暮胧。...
    茶點故事閱讀 38,163評論 1 334
  • 序言:一個原本活蹦亂跳的男人離奇死亡锐借,死狀恐怖问麸,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情钞翔,我是刑警寧澤严卖,帶...
    沈念sama閱讀 33,803評論 4 323
  • 正文 年R本政府宣布,位于F島的核電站布轿,受9級特大地震影響哮笆,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜汰扭,卻給世界環(huán)境...
    茶點故事閱讀 39,357評論 3 307
  • 文/蒙蒙 一稠肘、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧萝毛,春花似錦启具、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,357評論 0 19
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽拷沸。三九已至色查,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間撞芍,已是汗流浹背秧了。 一陣腳步聲響...
    開封第一講書人閱讀 31,590評論 1 261
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留序无,地道東北人验毡。 一個月前我還...
    沈念sama閱讀 45,636評論 2 355
  • 正文 我出身青樓,卻偏偏與公主長得像帝嗡,于是被迫代替她去往敵國和親晶通。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 42,925評論 2 344