学惯用 JavaScript 实现归并排序
引荐（免费）：JavaScript（视频）
归并排序背后的逻辑
归并排序使用分而治之的概念对给定的元素列表停止排序。它将问题分解为较小的子问题，直到它们变得足够简便以至可以直接解决为止。
以下是归并排序的步骤：
- 将给定的列表分为两半（假如列表中的元素数为奇数，则使其大致相等）。
- 以雷同的方式连续划分子数组，直到只剩下单个元素数组。
- 从单个元素数组开端，合并子数组，以便对每个合并的子数组停止排序。
- 反复第 3 步单元，直到最后得到一个排好序的数组。
以数组 [4, 8, 7, 2, 11, 1, 3] 为例，让我们看一下归并排序是怎样工作的：
用 JavaScript 实现归并排序
第一实现一个将两个已排序子数组合并为一个已排序数组的函数 merge() 。要留意着两个子数组是已经被排好序的，这一点非常重要， 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 ]
}在这个函数中，通过把两个排好序的子数组（left、right）合并来获得一个排好序的大数组。第一，创立一个空数组。之后在 left 和 right 两个子数组中最小元素中的较小的一个，并将其增加到空数组。我们只需要检查 left 和 right 子数组中的第一个元素，由于它们是已排好序的。
在这个历程中，从子数组中删除了被选中的元素（通过 shift() 函数实现）。连续这个历程，直到其中一个子数组变为空。最后把非空子数组的剩余元素（由于它们已经被排序）插入主数组的最后面。
此刻有了合并两个已排序数组的代码，接下来为实现归并排序算法的终究代码。这意味着要连续分割数组，直到终究只包括一个元素的数组为止：
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))
}在代码中先肯定中点，并用 splice() 函数将数组分为两个子数组。假如元素数目为奇数，则左侧的元素数目会少一个。不竭的划分数组，直到剩下单个元素的数组（array.length < 2）。然后用此前实现的 merge() 函数合并子数组。
代码实现后用前面的用例测试一下：
array = [4, 8, 7, 2, 11, 1, 3]; console.log(mergeSort(array));
输出相符预测：
1,2,3,4,7,8,11
归并排序的效力
归并排序的最差时间复杂度为 $O(n\\log n)$，与快速排序的最好情时间复杂度雷同。归并排序是当前最快的排序算法之一。
与快速排序不一样，归并排序不是in-place排序算法，这意味着除了输入数组之外，它还会占用额外的空间。这是由于我们使用了辅助数组来储备子数组。归并排序的空间复杂度为 $O(n)$。
归并排序的另一个长处是非常适合多线程，由于每个被划分出的一半都可以独自排序。另一种常见的减少归并排序运转时间的办法是在抵达相对较小的子数组时（大约 7 个元素）使用插入排序。这是由于插入排序在处置小型或几乎排好序的数组时展现非常好。
总结
在本文中，我们理解了Merge Sort算法背后的逻辑，并用 JavaScript 实现。它是根本排序算法之一，可以帮忙我们更好的理解分治法战略。
以上就是学惯用 JavaScript 实现归并排序的具体内容，更多请关注百分百源码网其它相关文章！
