關於Merge Sort排序方法與示意圖

    AllenLi
    Coding

    Merge Sort
    Traversal in Binary Tree：

    合併排序是將陣列拆分成兩個幾乎等長的數列，直到每個群組只剩下一個數值時，在合併各組數列。

    MargeSort

    Input: nums = [1, 2, 3, 2, 1, 6]

let mergeSort = (nums) => {
//當陣列只有一個數值時，則不需執行合併，故回傳 nums。
  if (nums.length <= 1) return nums
  
//宣告陣列項目，運用 Math.floor 取得中間值得整數，再透過 slice() 拆分兩個陣列。
  let middleIndex = Math.floor(nums.length / 2)
  let firstHalf = nums.slice(0, middleIndex)
  let secondHalf = nums.slice(middleIndex)

//透過 mergeSort() 來執行每一輪的陣列拆分，。
  return sortBeforeMerge(mergeSort(firstHalf), mergeSort(secondHalf))
  
  function sortBeforeMerge(nums1, nums2) {
    let sortNums = []
//當 nums1 和 nums2 的皆有長度時，執行迴圈內容。
    while (nums1.length && nums2.length) {
//如果 nums1 < num2 ，則運用 shift() 移除 nums1陣列中第一個數值，否則移除 nums2 陣列中第一個數值。
      let minElement = (nums1[0] < nums2[0]) ? nums1.shift() : nums2.shift()
//將取出的數值推入 sortNums 的空陣列中。
      sortNums.push(minElement)
    }
//跳出迴圈代表 nums1 或 nums2 其中一個為空陣列，則將之放入 sortNums 中。
    sortNums = nums1.length ? sortNums.concat(nums1) : sortNums.concat(nums2)
    return sortNums
  }
}

console.log(mergeSort([1, 2, 3, 2, 1, 6]))

Output: newNums = [1, 1, 2, 2, 3, 6]

    Flow Chart:

    Input: nums = [1, 2, 3, 2, 1, 6]

(middleIndex, nums)
3, [1, 2, 3, 2, 1 ,6]
1, [1, 2, 3], [2, 1 ,6]

firstHalf(middleIndex, nums) | secondHalf(middleIndex, nums)
1, [1], [2, 3]               | 1, [2], [1, 6]
1, [2], [3]                  | 1, [1], [6]

sortNums = firstHalf + secondHalf = [1, 1, 2, 2, 3, 6]

    Example：[演算法] 合併排序法（Merge Sort）

    Related Posts