iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 20
1
Software Development

使用JavaScript學習資料結構與演算法系列 第 20

Day20-排序法系列(四)-合併排序法

今天要介紹的是合併排序法 Merge Sort,合併排序法採用分治法(Divide and Conquer),它將資料列不斷分割成兩個資料列,這兩個資料列也不斷分割成兩個...持續到所有的資料列都只有一個元素。

接著會開始兩個兩個合併,而且合併的元素會依照大小進行排序,不斷兩兩合併,直到最後就變成一個已經排序好的資料列。

此網頁有小動畫可以參考看看,非常淺顯易懂:
http://notepad.yehyeh.net/Content/Algorithm/Sort/Merge/Merge.php

接著我們來實作吧!完成後會討論其時間複雜度~

  1. 首先建立一個 mergeSort(data) 的函式,用於將資料列分開並且最後回傳一個排序好的資料列。
    再建立一個 mergeData(left, right) 的函式,用於將資料列排序並合併。
function mergeSort(data) {
  
}

function mergeData(left, right) {
  
}

console.log(mergeSort([1, 234, -5, 78, -182, 45]));
  1. 先完成 mergeSort(data) 的部分,這邊的想法就是取中間值然後將資料列分成兩個子資料列,並且透過函式最後一行的遞迴將資料列分解到只剩一個元素,只要資料列只剩一個元素,就直接回傳該資料列。

  2. 因此假如有一個資料列 [1, 2, 3, 4] ,第一次分解會分解成 [1, 2][3, 4]console.log會跳出 split: [1, 2] [3, 4],進入 mergeData(mergeSort(leftPart), mergeSort(rightPart)) 會變成 mergeData(mergeSort([1, 2]), mergeSort([3, 4]))

  3. 此時會再次呼叫 mergeSort(data)一次,分解 mergeSort([1, 2] ,變成 [1][2] 兩個資料列,它們進入 mergeData(mergeSort(leftPart), mergeSort(rightPart)) 會變成 mergeData(mergeSort([1]), mergeSort([2])),不過兩個 mergeSort() 的呼叫由於其資料長度不超過2,因此不再繼續遞迴,反倒是傳了兩個陣列給 mergeData()了,變成這樣 mergeData([1], [2])。之後的 [3, 4] 的分解也是同理。

function mergeSort(data) {
  // 假如資料長度小於兩個元素,就可以不用排序了
  if (data.length < 2) {
    return data;
  }

  // 取中間值
  const middle = Math.floor(data.length / 2); // Math.floor() 函式會回傳無條件捨去後的最大整數。

  // 取得分開的左邊資料和右邊資料
  const leftPart = data.slice(0, middle);
  const rightPart = data.slice(middle, data.length);
  console.log('split:', leftPart, rightPart);

  // 透過遞迴不斷將資料做分裂,最後回傳重新合併並排序過的資料列
  return mergeData(mergeSort(leftPart), mergeSort(rightPart));
}
  1. 元素傳入 mergeData() 後,我們要把資料排序後合併並回傳。
    由於此兩個資料列都是排序好的狀態或是都只有一個元素,我們可以比較左右兩邊的資料列最前面的值(資料列最小的值),將比較小的推入 result 空陣列,透過 shift(),較小的值會從資料列移除,直到某邊沒有元素就停止迴圈。

  2. 某邊沒有元素就停止迴圈後,另一邊可能還有剩餘的元素,因此再用兩個 while 迴圈做檢查,並把它們推入 result 陣列。最後回傳排序好的 result 陣列。

function mergeData(left, right) {
  // 建立一個可儲存排序後資料的空陣列
  let result = [];

  // 比較左右兩邊的資料列的值
  while(left.length && right.length) {
    if(left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }

  // 有時經過以上的迴圈之後,若某邊資料列的元素先shift完則另一個資料列會有剩下的元素(且是全部資料中的最大值),將它們推入result陣列
  while (left.length) result.push(left.shift());
  while (right.length) result.push(right.shift());

  console.log('result:', result);
  return result;
}

運行過程如下,可以觀察是怎麼運作的:

2021/02/18 更新: 遞迴解法

function mergeSort(arr) {
  if(arr.length === 1) {
    return arr;
  } else {
    const splitIndex = Math.floor(arr.length / 2);
    return merge(mergeSort(arr.slice(0, splitIndex)), mergeSort(arr.slice(splitIndex)))
  }
  
  function merge(arr1, arr2) {
    let merged = [];
    while(arr1.length && arr2.length) {
      if(arr1[0] < arr2[0]) {
        merged.push(arr1.shift());
      } else if(arr1[0] > arr2[0]) {
        merged.push(arr2.shift());
      } else {
        merged.push(arr1.shift(), arr2.shift());
      }
    }
    return [...merged, ...arr1, ...arr2];
  }
}

時間複雜度:

最佳/平均/最差時間複雜度都是:O(nlog n)

本次程式碼在以下連結:
https://github.com/a90100/javascript-data-structure/blob/master/day20-merge-sort.js

明天將會介紹最後一種排序法,快速排序法!


上一篇
Day19-排序法系列(三)-插入排序法
下一篇
Day21-排序法系列(五)-快速排序法
系列文
使用JavaScript學習資料結構與演算法30

尚未有邦友留言

立即登入留言