JavaScript 中的合併排序
簡介
排序是指以特定順序（數字或字母）排列列表中的項目。排序一般與搜索結合使用。
如果列表在視覺上和算法上都已排序，則通常更容易在給定列表中搜索元素（稱為鍵）。
有很多方法（算法）可以對給定的元素列表進行排序。 合併排序 是一種更流行、更有效的方法。
在本文中，我們將看到 Merge Sort 背後的邏輯，在 JavaScript 中實現它，並將其可視化。最後，從空間複雜度和時間複雜度上，我們將 Merge Sort 與其他算法進行比較。
理解歸併排序背後的邏輯
歸併排序使用分而治之的概念 對給定的元素列表進行排序。它將問題分解為更小的子問題，直到它們變得簡單到可以直接解決。
以下是合併排序的步驟：
- 將給定的列表分成兩半（如果列表具有奇數個元素，則大致相等的兩半）。
- 繼續以相同的方式劃分子數組，直到只剩下單個元素數組。
- 從單元素數組開始，合併 子數組，以便對每個合併的子數組進行排序。
- 重複第 3 步單元，最終得到一個排序數組。
讓我們看看合併排序是如何在 [4, 8, 7, 2, 11, 1, 3] 這樣的數組上工作的 ：
JavaScript 中合併排序的實現
我們先寫代碼到merge() 兩個排序後的子數組組成一個排序數組。記住這兩個子數組已經排序非常重要，我們只是使用 merge() 對它們進行組合 功能。
我們可以通過遍歷這兩個子數組來做到這一點，並一個接一個地添加元素，以便結果數組也被排序：
function merge(left, right) {
let arr = []
// Break out of loop if any one of the array gets empty
while (left.length && right.length) {
// Pick the smaller among the smallest element of left and right sub arrays
if (left[0] < right[0]) {
arr.push(left.shift())
} else {
arr.push(right.shift())
}
}
// Concatenating the leftover elements
// (in case we didn't go through the entire left or right array)
return [ ...arr, ...left, ...right ]
}
在這個函數中，我們採用兩個排序的子數組（left , right ) 並合併它們以獲得單個排序數組。首先，我們創建一個空數組。稍後，我們選擇 left 中最小的未選擇元素中的較小者 和 right 子數組並將它們推入空數組。我們只需要檢查 left 中的第一個元素 和 right 子數組，因為它們都已排序。
在執行此操作時，我們從子數組中刪除選取的元素（這是使用 shift() 功能）。我們繼續這個過程，直到其中一個子數組變為空。之後，我們將非空子數組的剩餘元素（因為它們已經排序）推入主數組。
因為我們現在有了合併兩個排序數組的代碼（conquer 分而治之的一部分 )，讓我們為合併排序算法編寫最終代碼。這意味著我們需要不斷拆分數組，直到我們最終得到只包含一個元素的數組：
function mergeSort(array) {
const half = array.length / 2
// Base case or terminating case
if(array.length < 2){
return array
}
const left = array.splice(0, half)
return merge(mergeSort(left),mergeSort(array))
}
在這裡，我們確定中點並使用 splice() 將數組拆分為兩個子數組 功能。如果有奇數個元素，則左邊的元素數量較少。我們一直在分割，直到剩下單元素數組（array.length < 2 ）。之後，我們開始使用之前編寫的 merge() 組合子數組 功能。
現在我們已經有了代碼，讓我們看看在前面的示例中運行函數的輸出：
免費電子書：Git Essentials
查看我們的 Git 學習實踐指南，其中包含最佳實踐、行業認可的標準以及隨附的備忘單。停止谷歌搜索 Git 命令並真正學習 它！
array = [4, 8, 7, 2, 11, 1, 3];
console.log(mergeSort(array));
這給了我們預期的輸出：
1,2,3,4,7,8,11
歸併排序的效率
合併排序的最壞情況時間複雜度是O(nlogn) ，與快速排序的最佳情況時間複雜度相同。就速度而言，合併排序是目前最快的排序算法之一。
與快速排序不同，合併排序不是就地 排序算法，這意味著它需要輸入數組以外的額外空間。這是因為我們使用輔助（輔助）數組來存儲子數組。歸併排序的空間複雜度為O(n) .
合併排序的另一個優點是它非常適合多線程，因為每一半都可以自行排序。另一種減少合併排序運行時間的常用方法是在我們到達相對較小的子數組（~7）時停止並使用插入排序對它們進行排序。
這樣做是因為插入排序在小型或接近排序的數組上表現得非常好。比全球效率更高的同類產品要好得多。
結論
在本文中，我們看到了 Merge Sort 算法背後的邏輯，如何在 JavaScript 中實現它，並了解了它的性能。它是基本的排序算法之一，對於給出一個清晰的分治法示例非常有用 戰略。
