JS 學資料結構與演算法 (排序篇) — 合併排序法 Merge Sort

合併排序法 Merge Sort

合併排序法定義

合併演算法與上一篇介紹的快速排序法一樣,都運用了 Devide and Conquer 的概念,基本上分為兩個步驟:分割與整合。首先利用遞迴把原先未排序的陣列平均分割成兩半,直到各邊都只剩下一個元素(上圖紫色方塊),接著排序後再一一整合起來,最後會合併成一個排序後的陣列(上圖綠色區塊)。

分割 (紫色區塊)

  1. 把大陣列分一半成為兩個小陣列
  2. 把從上一步驟切好的兩個小陣列再各自分一半
  3. 重複步驟 2 直到每個小陣列都只剩一個元素

整合 (綠色區塊)

  1. 排序兩個只剩一個元素的小陣列並將其合併
  2. 把上一步驟排序好的小陣列合併並排序成一個陣列
  3. 重複步驟二直到所有小陣列都合併成一個大陣列

讀者比較有疑問的也許會是這個部分:

Q: [2,3,7,16] 跟 [4,9,11,24] 這兩個陣列是如何合併成最終的已排序陣列呢?

A: 因為這兩個陣列在合併前就已經各自完成排序了,因此只要比較各自最左邊的元素的大小,將比較小的元素放進新陣列中,最後就能完成排序囉!其實從一開始只有一個元素要進行合併時就是運用這個方法喔(只有一個元素的陣列視為已排序)!

時間複雜度

最佳:O(n log n)最差:O(n log n)平均:O(n log n)

時間複雜度的部分,我們依然可以分為 “分割” 與 “整合” 兩個步驟來看。

分割:分割含有 n 個元素的陣列需要 (n-1) 次步驟。

合併:若要合併的兩陣列共用 n 個元素,每次排序與合併必須經過 n 次步驟。

接著要考量的是需要經過幾個回合的合併,從上圖的例子可以發現,原先 8 個獨立的元素經過一次合併後變成 4 個小陣列,再經過一次合併後成為兩個陣列,最後兩個陣列再合併形成最終排序過後的一個陣列,如此每次合併都讓下回需要合併的陣列數減少一半,這表示總共需要合併的回合數會是以 2 為底的 log n 次。

因此合併排序法的時間複雜度為:

時間複雜度 = 分割步驟數 + 合併步驟數 = 分割步驟數 + 每回合合併所花步驟數 * 回合總數 = (n-1) + log n * n

而由於時間複雜度只看最高項係數且忽略常數,因此得出的時間複雜度為 O(n log n)。

程式碼範例

const numbers = [27, 34,16, 4, 1, 5, 69, 65, 223, 7, 0];function mergeSort (array) {  if (array.length === 1) {    return array;  };  const length = array.length;  const middle = Math.floor(length / 2);  const left = array.slice(0, middle);  const right = array.slice(middle);  return merge(    mergeSort(left),mergeSort(right)  );}
function merge(left, right){ const result = []; let leftIndex = 0; let rightIndex = 0; while(leftIndex < left.length && rightIndex < right.length){ if(left[leftIndex] < right[rightIndex]){ result.push(left[leftIndex]); leftIndex++; } else{ result.push(right[rightIndex]); rightIndex++; }}return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));}const answer = mergeSort(numbers);

完整程式碼連結

合併排序法一樣使用了遞迴的概念,一開始看也許會沒有那麼直覺,而整個演算法的流程如果跟著本篇文章的內容走的話,要了解程式碼應該不會有太大的問題,就留給讀者自行吸收領會了。

下回預告: 氣泡排序法 (Bubble Sort)

--

--

什麼都想學的雜食性軟體工程師 🇹🇼 (https://github.com/kylemocode) 合作與聯繫 📪 oldmo860617@gmail.com

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
莫力全 Kyle Mo

莫力全 Kyle Mo

什麼都想學的雜食性軟體工程師 🇹🇼 (https://github.com/kylemocode) 合作與聯繫 📪 oldmo860617@gmail.com