[演算法] 合併排序法(Merge Sort)
此系列筆記主要依照 [Udemy] Learning Algorithms in JavaScript from Scratch by Eric Traub 的課程脈絡加以整理,但部分程式碼是消化後以自己較易理解的方式重新撰寫,因此和原課程內容有些出入。
問題描述
透過函式將陣列中的數值加以排序。
前置知識:Merge Sort
Merge Sort 和 Bubble Sort 一樣,都是一種用來排序的演算法。
Merge Sort 的演算法主要包含兩個部分:
1. 將陣列對半拆分
Merge Sort 的第一步是要將陣列兩兩對半拆分,直到拆到每個陣列只剩一個元素:
// 原本的陣列
[3, 20, 8, 5, 1, 12, 17, 2][
// 進行對半拆分
(3, 20, 8, 5)
],
[1, 12, 17, 2][
// 再拆分
(3, 20)
],
[8, 5],
[1, 12],
[17, 2][3], // 再拆分
[20],
[8],
[5],
[1],
[12],
[17],
[2];
2.將陣列排序後加以合併
我們把上面拆分好的陣列,兩兩一組開始進行排序,每次排序時都是取該陣列的++第一個元素++進行比較:
// 拆分好的陣列
[3],
[20],
[8],
[5],
[1],
[12],
[17],
[2][
// [3] vs [20]; [8] vs [5]; [1] vs [12]; [17] vs [2]
// 兩兩比較排序後合併,每次比較都是取當時陣列中的第一個元素進行比較
(3, 20)
],
[5, 8],
[1, 12],
[2, 17][
// 再一次兩兩比較後排序後合併,每次比較都是取當時陣列中的第一個元素進行比較
(3, 5, 8, 20)
],
[1, 2, 12, 17][
// 再一次兩兩比較後排序後合併,每次比較都是取當時陣列中的第一個元素進行比較
(1, 2, 3, 5, 8, 12, 17, 20)
];
兩兩比較後排序的方式可以參考下圖,每次比較都是取各陣列的第一個元素來進行比較:
圖片來源:Learning Algorithms in JavaScript from Scratch by Eric Traub @ Udemy
整個合併排序法如下圖所示:
圖片來源:合併排序 @ wikipedia
因此我們一共需要兩個函式,並且一樣會透過遞回函式的方式來處理:
function mergeSort(arr) {
// 接受一組尚未排序的陣列當作參數,將它們對半切分
}
function sortBeforeMerge(arr1, arr2) {
/**
* 代入兩個已經各自排序過的陣列
* 每次都取這兩個陣列中當時的第一個元素進行比較
* 把數值小的放前面,最後合併成一個陣列
**/
}
Merge Sort 這個演算法我覺得稍微有一點點小小複雜,非常需要圖像化來幫助思考,但我們可以先看 code ,看完之後會更瞭解它實際上的運作方式。