fbpx

合併排序法 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 次步驟。

 

如圖所示,總共4個元素的小陣列,因為每次都是比較最左邊的元素,將較小的一項加到新陣列中,因此總共需要 4 個步驟。

接著要考量的是需要經過幾個回合的合併,從上圖的例子可以發現,原先 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);

完整程式碼連結

 


結語

合併排序法一樣使用了遞迴的概念,一開始看也許會沒有那麼直覺,而整個演算法的流程如果跟著本篇文章的內容走的話,要了解程式碼應該不會有太大的問題,就留給讀者自行吸收領會了。如果你對這個系列有興趣,也想跟我一起透過 JavaScript 強化自己對於資料結構與演算法的基礎,歡迎訂閱我,如果覺得這篇文章對你有幫助,也不要吝嗇幫我拍拍手吧!

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

JS 學資料結構與演算法JS 學資料結構與演算法全系列:

(1) 快速排序法 Quick Sort 

(2) 合併排序法 Merge Sort (本篇)

(3) 氣泡排序法 Bubble Sort

(4) 選擇排序法 & 插入排序法

 

「好文轉自莫力全 Kyle Mo–JS 學資料結構與演算法 (排序篇) — 合併排序法 Merge Sort,如果你喜歡他的文章歡迎回到他的部落格看更多:)」

希望以上能幫助到你藉由JS 更了解資料結構與演算法。如果想要對JavaScript本身有更多的瞭解,Udemy這裡開課囉!老師從基礎手把手的帶你實作,教你主流寫法提升 JS 開發能力!

如果你的入門還在單打獨鬥,歡迎來到快樂學程式找到志同道合的夥伴,你的自學之路不孤單。