[小撒學(xué)算法]分治法與合并排序

小撒是一只好學(xué)的小鴨子萍嬉,這天嚎朽,小撒在學(xué)習(xí)算法

分治法

分治法(divide-and-conquer)是一種算法設(shè)計(jì)策略蜗侈。使用分治法的算法在每一層迭代有3個(gè)步驟:

  1. 分解(divide):將原問(wèn)題分解成一系列子問(wèn)題
  2. 解決(conquer):遞歸解決子問(wèn)題鲤拿;在子問(wèn)題足夠小時(shí)蚂四,直接解決子問(wèn)題
  3. 合并(combine):將子問(wèn)題的結(jié)果合并為原問(wèn)題的解

合并排序

合并排序(merge sort)便是使用了分治的策略沥阳。

如果我們有兩個(gè)已經(jīng)排序好的數(shù)組跨琳,要得到兩者合并后的排序數(shù)組,我們只需反復(fù)比較兩個(gè)數(shù)組頭部(最谢ο)的元素湾宙,將更小的取出并放入結(jié)果數(shù)組:

合并排序圖示

我們可以不斷的將規(guī)模為n的問(wèn)題分解為規(guī)模為n / 2的問(wèn)題,直至n/2 <= 1

合并排序的時(shí)間復(fù)雜度

遞歸樹(shù)(recursion tree)每向下一層冈绊,規(guī)模為n的問(wèn)題T(n)被分解為兩個(gè)T(n/2)的問(wèn)題侠鳄,因此樹(shù)的總高度為ln(n)/ln(2)

而合并兩個(gè)T(n/2)死宣,則共需要n次比較并取出較小值伟恶,因此每層的總操作數(shù)為n,由此得到合并排序的時(shí)間復(fù)雜度為θ(n * log(n))毅该。

代碼示例(js)

const merge = (arr, start, mid, end) => {
  const arr1 = arr.slice(start, mid + 1)
  const arr2 = arr.slice(mid + 1, end + 1)
  while (end >= start) {
    if (arr2.length === 0) {
      arr[start] = arr1.shift()
    } else if (arr1[0] < arr2[0]) {
      arr[start] = arr1.shift()
    } else {
      arr[start] = arr2.shift()
    }
    start++
  }
}

const mergeSort = (arr, start, end) => {
  if (end > start) {
    const mid = Math.floor((end + start) / 2)
    mergeSort(arr, start, mid)
    mergeSort(arr, mid + 1, end)
    merge(arr, start, mid, end)
  }
}

小結(jié)

合并排序使用了分治的算法策略博秫,相比插入排序等算法大大提高了時(shí)間復(fù)雜度潦牛,但也引入了O(n)的空間成本。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末挡育,一起剝皮案震驚了整個(gè)濱河市巴碗,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌即寒,老刑警劉巖橡淆,帶你破解...
    沈念sama閱讀 212,383評(píng)論 6 493
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異母赵,居然都是意外死亡逸爵,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,522評(píng)論 3 385
  • 文/潘曉璐 我一進(jìn)店門(mén)凹嘲,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)师倔,“玉大人,你說(shuō)我怎么就攤上這事周蹭∏魉遥” “怎么了?”我有些...
    開(kāi)封第一講書(shū)人閱讀 157,852評(píng)論 0 348
  • 文/不壞的土叔 我叫張陵凶朗,是天一觀(guān)的道長(zhǎng)致稀。 經(jīng)常有香客問(wèn)我,道長(zhǎng)俱尼,這世上最難降的妖魔是什么? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 56,621評(píng)論 1 284
  • 正文 為了忘掉前任萎攒,我火速辦了婚禮遇八,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘耍休。我一直安慰自己刃永,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,741評(píng)論 6 386
  • 文/花漫 我一把揭開(kāi)白布羊精。 她就那樣靜靜地躺著斯够,像睡著了一般。 火紅的嫁衣襯著肌膚如雪喧锦。 梳的紋絲不亂的頭發(fā)上读规,一...
    開(kāi)封第一講書(shū)人閱讀 49,929評(píng)論 1 290
  • 那天,我揣著相機(jī)與錄音燃少,去河邊找鬼束亏。 笑死,一個(gè)胖子當(dāng)著我的面吹牛阵具,可吹牛的內(nèi)容都是我干的碍遍。 我是一名探鬼主播定铜,決...
    沈念sama閱讀 39,076評(píng)論 3 410
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼怕敬!你這毒婦竟也來(lái)了揣炕?” 一聲冷哼從身側(cè)響起,我...
    開(kāi)封第一講書(shū)人閱讀 37,803評(píng)論 0 268
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤东跪,失蹤者是張志新(化名)和其女友劉穎畸陡,沒(méi)想到半個(gè)月后,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體越庇,經(jīng)...
    沈念sama閱讀 44,265評(píng)論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡罩锐,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,582評(píng)論 2 327
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了卤唉。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片涩惑。...
    茶點(diǎn)故事閱讀 38,716評(píng)論 1 341
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖桑驱,靈堂內(nèi)的尸體忽然破棺而出竭恬,到底是詐尸還是另有隱情,我是刑警寧澤熬的,帶...
    沈念sama閱讀 34,395評(píng)論 4 333
  • 正文 年R本政府宣布痊硕,位于F島的核電站,受9級(jí)特大地震影響押框,放射性物質(zhì)發(fā)生泄漏岔绸。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 40,039評(píng)論 3 316
  • 文/蒙蒙 一橡伞、第九天 我趴在偏房一處隱蔽的房頂上張望盒揉。 院中可真熱鬧,春花似錦兑徘、人聲如沸刚盈。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 30,798評(píng)論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)藕漱。三九已至,卻和暖如春崭闲,著一層夾襖步出監(jiān)牢的瞬間肋联,已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 32,027評(píng)論 1 266
  • 我被黑心中介騙來(lái)泰國(guó)打工刁俭, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留牺蹄,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 46,488評(píng)論 2 361
  • 正文 我出身青樓薄翅,卻偏偏與公主長(zhǎng)得像沙兰,于是被迫代替她去往敵國(guó)和親氓奈。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,612評(píng)論 2 350