歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序演算法，該演算法是采用分治法（Divide and Conquer）的一個非常典型的應用，
作為一種典型的分而治之思想的演算法應用，歸并排序的實作由兩種方法：
- 自上而下的遞回（所有遞回的方法都可以用迭代重寫，所以就有了第 2 種方法）；
- 自下而上的迭代；
在《資料結構與演算法 JavaScript 描述》中，作者給出了自下而上的迭代方法，但是對于遞回法，作者卻認為：
However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.
然而，在 JavaScript 中這種方式不太可行，因為這個演算法的遞回深度對它來講太深了，
和選擇排序一樣，歸并排序的性能不受輸入資料的影響，但表現比選擇排序好的多，因為始終都是 O(nlogn) 的時間復雜度，代價是需要額外的記憶體空間，
2. 演算法步驟
歸并排序使用分而治之的概念對給定的元素串列進行排序，它將問題分解為較小的子問題，直到它們變得足夠簡單以至可以直接解決為止，
以下是歸并排序的步驟：
- 將給定的串列分為兩半（如果串列中的元素數為奇數，則使其大致相等），
- 以相同的方式繼續劃分子陣列，直到只剩下單個元素陣列，
- 從單個元素陣列開始，合并子陣列，以便對每個合并的子陣列進行排序，
- 重復第 3 步單元，直到最后得到一個排好序的陣列，
3. 動圖演示
代碼實作
將兩個已排序子陣列合并為一個已排序陣列的函式 merge()
function merge(left, right) {
let arr = []
// 如果任何一個陣列為空，就退出回圈
while (left.length && right.length) {
// 從左右子陣列的最小元素中選擇較小的元素
if (left[0] < right[0]) {
arr.push(left.shift())
} else {
arr.push(right.shift())
}
}
// 連接剩余的元素，防止沒有把兩個陣列遍歷完整
return [ ...arr, ...left, ...right ]
}更完整的實作
function mergeSort(array) {
const half = array.length / 2
if(array.length < 2){
return array
}
const left = array.splice(0, half)
return merge(mergeSort(left),mergeSort(array))
}轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/289881.html
標籤：其他
上一篇：基于jq的倒計時案例