演算法-資料結構學習筆記 Merge Sort , Quick Sort
一、前言
學過三個比較初階的排序演算法後，由於它們的時間複雜度皆為 O(n²)，雖然在處理較小的資料量時不會有明顯的差異，但如果遇到千、萬級別以上的資料量，這些排序法耗費的執行時間就會冗長到令人難以接受。
因此今天要介紹比較進階的合併排序與快速排序，它們在處理大量資料的排序時，比冒泡排序、插入排序和選擇排序還更有效率，但與此同時，它們的難度也比較高，不像上述三者這麼直觀且易於理解。
二、合併排序
(一)運作原理
合併排序的核心概念在於每個元素數量為 1 或 0 的陣列，即是有序的資料，因此不斷切分大量資料直到每個陣列只剩下 1 或 0 個元素時，再透過比較與合併的方式逐步合併成一個有序的陣列，即完成了資料的排序。
因此，整個合併排序的過程可以分成兩大部分，第一部分就是對切資料直到所有的陣列都剩下 1 個元素，第二部分則是逐步比較每個陣列，並且一層一層地合併成更大的有序陣列，直到所有切分的小陣列都被合併為止。
假設今天要將陣列元素由小到大排序，以下用一個包含 8 個元素的陣列來舉例：
(1) 切分陣列
[4, 3, 2, 7, 1, 6, 5, 8] ↓ ↓[4, 3, 2, 7] [1, 6, 5, 8] ↓ ↓ ↓ ↓[4, 3] [2, 7] [1, 6] [5, 8]↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓[4] [3] [2] [7] [1] [6] [5] [8]
(2) 比較大小與合併陣列
[4] [3] [2] [7] [1] [6] [5] [8] ↓ ↓ ↓ ↓ // 3 < 4， 3 與 4 依序合併[3, 4] [2, 7] [1, 6] [5, 8] ↓ ↓ // 每次比較時從兩個陣列的第一個元
// 素開始比較。
// 比較小的元素就先放入新的合併陣
// 列，直到全都排序完。 [2, 3, 4, 7] [1, 5, 6, 8] ↓ // 重複上述步驟，最後得到一個有序
// 排列的完整陣列。 [1, 2, 3, 4, 5, 6, 7, 8]
(二)實作
這次合併排序的實作，我們會拆成幾個部分，第一個要先實作的是比較與合併陣列的部分，要建立一個函式，以兩個陣列作為參數傳入，透過逐一比對兩個參數的元素大小，回傳一個合併後的有序陣列。
function mergeArray(arr1, arr2) {
// 建立一個空陣列用來儲存排序好的新陣列，以及兩個陣列參數的指標
let result = []
let i = 0
let j = 0
// 建立一個迴圈迭代兩個參數，若其中一個指標的索引值超過陣列元素上限，則跳脫迴圈
while(i < arr1.length && j < arr2.length) {
if (arr1[i] < arr2[j]) {
result.push(arr1[i])
i++
} else {
result.push(arr2[j])
j++
}
} // 跳脫迴圈後，可能另一個陣列仍有元素尚未合併，要分別用兩個 while 迴圈處理
while(i < arr1.length) {
result.push(arr1[i])
i++
}
while(j < arr2.length) {
result.push(arr2[j])
j++
}
// 回傳陣列
return result
}
接著，我們要來寫真正的 merge sort 函式，它會接受一個陣列參數，並且透過遞迴不斷自呼叫 merge sort 函式將陣列對切，直到剩下一個陣列元素，再使用剛才寫好的 mergeArray 函式逐步合併，最終回傳合併好的排序陣列。
首先，要設立遞迴的終止條件，也就是陣列元素數量小於等於 1
再者，要計算切分陣列的斷點，並且搭配 Array.slice() 去切分成兩個小陣列，再把切好的小陣列代入 另一個自呼叫的 mergeSort()，就可以形成遞迴不斷切割，直到達成終止條件，也就是所有小陣列都被切成元素數量小於等於 1
最終，呼叫 mergeArray() 合併兩個小陣列後回傳。由於遞迴自呼叫的緣故，在 Call stack 最上層的會是最後一次被呼叫的 mergeSort()，裡面包含的會是兩個最小的陣列，而它們會最先被執行合併，然後一層一層往下執行，最後被執行到的 mergeSort()，就會是第一次呼叫的 mergeSort()，它所回傳的陣列便會是經過一系列比較與合併後的完整排序陣列。
function mergeSort(arr) {
// 如果陣列元素的數量小於 1，就直接返回該陣列，也是遞迴的 base case
if (arr.length <= 1) return arr
let mid = Math.floor(arr.length / 2)
// 不斷切割成兩個小陣列
let leftArr = mergeSort(arr.slice(0, mid))
let rightArr = mergeSort(arr.slice(mid))
// 呼叫 mergeArray 合併兩個小陣列並且回傳
return mergeArray(leftArr, rightArr)
}從實作合併排序的程式碼來看，它需要花費的切分次數是以 2 為底數的 log n，例如數量為 8 的陣列會需要切分 3 輪。
至於 n 是怎麼來的呢？由於每次切分之後，還需要呼叫 mergeArray 去比較和合併小陣列，而在函式中使用了單層的迴圈去處理，所以這裡的時間複雜度會是 O(n)。
簡單來說，每一輪需要比較 n 次，而總共有 log n 輪，相乘起來就會是 O(n log n) 了。
相較於冒泡排序，合併排序的時間複雜度是 O(n log n)，因此它耗費的執行時間並不會呈現指數上升。在面對比較龐大的資料量時，它是比較有效率的排序演算法。
不過，由於它需要建立一個新陣列去儲存排序的結果，因此空間複雜度為 O(n)，可以說是犧牲空間以換取時間。
三、快速排序
(一)運作原理
快速排序的英文是 Quick Sort，其核心概念也與合併排序非常相似，即是將陣列逐步分割為較小的陣列，直到陣列元素數量為 1 或 0 才停止分割，因為此時的陣列已經可以視作有序的陣列。
它與合併排序最大的不同是，合併排序是將切割後的子陣列比對大小後依序合併，直到從最小單位的陣列逐步合併回原本的陣列；快速排序則是選定一個基準點 ( Pivot )，將小於基準點的元素移至基準點左方，大於基準點的元素則移至右方，然後透過遞迴的方式，在切割後的小陣列重新選一個基準點，並且重複上述排序的過程，直到所有元素排序完成。
這次一樣使用包含八個數字的陣列來舉例，目的是由小排到大：
[4, 3, 2, 7, 1, 6, 5, 8] // 選取第一個元素 4 為基準點
↓ // 讓 4 的左方為小於 4 的元素，右方為大於 4 的
// 元素。
[3, 2, 1, 4, 7, 6, 5, 8] // 4 的位置已排序，但左、右兩個子陣列仍未排序，遞
// 迴左方的子陣列。 ↓ // 選取 3 為基準點重新排序 4 左方的子陣列
[2, 1, 3, 4, 7, 6, 5, 8] // 選取 2 為基準點重新排序 3 左方的子陣列 ↓[1, 2, 3, 4, 7, 6, 5, 8] // 左方排序完成，選取 7 為基準點重新排序 4 右方
// 的子陣列。 ↓[1, 2, 3, 4, 5, 6, 7, 8] // 排序完成
這裡有幾點可以注意：
- 主要是透過選取基準點與遞迴的方式來達到切割陣列的效果，實際上並沒有切割陣列，與合併排序不同。
- 排序的邏輯是以基準點為主，確保基準點左右兩邊的資料符合條件，但並不排序這些子陣列，真正排序的是基準點本身在排序陣列中的正確位置。
- 透過遞迴不斷重新選取基準點並排序，直到陣列的元素數量小於或等於 1，即表示該陣列已經排序，這點與合併排序的概念一致。
(二)實作
從上述的運作原理來看，快速排序的實作可以拆成兩個部分，一個是迭代、遞迴的判斷邏輯，另一個則是選取基準點與交換的邏輯，以下會分開來實作。
第一部分是選取基準點的函式，這個函式要接受一個陣列、起始索引與終點索引作為參數，並且在選取基準點之後，依據該基準點調整陣列內的元素位置，最後回傳調整位置後的基準點索引值。此外，該函式會直接操作原本的陣列，而不會像合併排序那樣另外建立一個新的空陣列處理。
還有一點需要注意的是，快速排序選取基準點的方式並沒有特別限定，通常來說可以選到資料集合裡值相對中間的元素，可以比較有效地排序，但由於我們無法在無序的資料找到比較中間的值，所以這次一律採用陣列的第一個元素，作為基準點。
在與基準點比較大小的過程中，會先以一個變數 swapIndex 儲存交換元素的位置，一開始預設是基準點，也就是 第一個元素，一旦遇到比基準點更小的元素，就先將交換元素的位置往後移一位，再與目前掃描的元素交換，而基準點的位置依然維持在第一個元素。
跑完一個迴圈後，所有小於基準點的元素都會被交換至陣列的左側，而 swapIndex 儲存的值，會是最後一個掃描到小於基準點的元素索引值，再將基準點與該索引值的位置交換後回傳 swapIndex，即完成了一輪的排序。
function findPivot(arr, start = 0, end = arr.length - 1) {
// 交換元素的函式
const swap = (arr, indexOne, indexTwo) => {
[arr[indexOne], arr[indexTwo]] = [arr[indexTwo], arr[indexOne]]
}
// 選取第一個元素作為基準點，並且暫存交換元素的索引值
const pivot = arr[start]
let swapIndex = start // 迭代陣列每一個元素，與基準點比較大小
for (let i = start + 1; i <= end; i++) {
if (pivot > arr[i]) {
swapIndex++
swap(arr, swapIndex, i)
}
}
// 跑完迴圈後再交換基準點與最後一個小於基準點的元素位置
swap(arr, start, swapIndex)
return swapIndex
}
第二階段要來真正實作 Quick Sort 的邏輯，我們會在函式的開頭透過 findPivot() 去找到基準點最終的正確位置，並且透過這個位置將陣列劃分為左右兩側，並在左右兩側自呼叫 Quick Sort 函式，就可以利用遞迴不斷排序陣列。
那麼遞迴的 base case 該如何設立呢？由於 Quick Sort 函式一樣會代入三個參數，除了要排序的陣列以外，也會有起始索引與終點索引值，因此只要起始索引與終點索引值相同，就表示傳入的參數陣列只剩下一個元素，就無須再排序了。
在函式中透過遞迴不斷排序，最終也要回傳排序過的陣列，以上就是 Quick Sort 函式的實作邏輯。
function quickSort(arr, start = 0; end = arr.length - 1) {
if (start < end) {
const pivotIndex = findPivot(arr, start, end)
// 基準點左邊的子陣列
quickSort(arr, start, pivotIndex - 1)
// 基準點右邊的子陣列
quickSort(arr, pivotIndex + 1, end)
}
// 回傳排序陣列
return arr
}實作完快速排序的程式碼後，一樣要來解讀一下它的時間複雜度。
首先，每一輪的排序都需要迭代整個陣列或子陣列的所有元素，所以會是 O(n)，而依據基準點拆分陣列則會有不同的情況。
一般來說，每次選取基準點的時候，陣列都會有一些元素大於小於基準點，所以可以順利拆分成左右兩個子陣列，那麼平均的時間複雜度就是 O(log n) ，總體算起來則是 O(n log n)，與合併排序相似。
但如果每次選取的基準點，都剛好是該次陣列的最大值或最小值，就無法順利拆分成左右兩個子陣列，因為一次只能排序出基準點這個元素，總共會需要拆 n 次，則時間複雜度會提高至 O(n)，總體算起來就會是 O(n²) 了。
不過，由於上述的情況十分極端且罕見，所以快速排序依然會是相對比較快速的排序演算法，畢竟都叫做快速了嘛 XD。
