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

合併排序法示意圖

合併排序法 Merge Sort

分割 (紫色區塊)

整合 (綠色區塊)

最佳:O(n log n)最差:O(n log n)平均:O(n log n)
如圖所示,總共4個元素的小陣列,因為每次都是比較最左邊的元素,將較小的一項加到新陣列中,因此總共需要 4 個步驟。
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

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