JavaScript算法之归并排序算法（详解）(2)-木庄网络博客

在这个过程中，从子数组中删除了被选择的元素（通过 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() 函数合并子数组。

代码实现后用前面的用例测试一下：

1 2	`array = [4, 8, 7, 2, 11, 1, 3];` `console.log(mergeSort(array));`

输出符合预期：

1	`1,2,3,4,7,8,11`

归并排序的效率

归并排序的最差时间复杂度为 $O(n\\log n)$，与快速排序的最佳情时间复杂度相同。归并排序是目前最快的排序算法之一。

与快速排序不同，归并排序不是in-place排序算法，这意味着除了输入数组之外，它还会占用额外的空间。这是因为我们使用了辅助数组来存储子数组。归并排序的空间复杂度为 $O(n)$。

归并排序的另一个优点是非常适合多线程，因为每个被划分出的一半都可以单独排序。另一种常见的减少归并排序运行时间的方法是在到达相对较小的子数组时（大约 7 个元素）使用插入排序。这是因为插入排序在处理小型或几乎排好序的数组时表现非常好。

总结

在本文中，我们了解了Merge Sort算法背后的逻辑，并用 JavaScript 实现。它是基本排序算法之一，可以帮助我们更好的了解分治法策略。

更多编程相关知识，请访问：编程视频课程！！

以上就是JavaScript算法之归并排序算法（详解）的详细内容，更多文章请关注木庄网络博客！

返回前面的内容

Vue.js 设计与实现基于Vue.js 3 深入解析Vue.js 设计细节

￥83.86元 人民邮电出版社

本书对 Vue.js 3 技术细节的分析非常可靠，对于需要深入理解 Vue.js 3 的用户会有很大的帮助。——尤雨溪，Vue.js作者

转载请注明出处：木庄网络博客 » JavaScript算法之归并排序算法（详解）

JavaScript算法之归并排序算法（详解）

归并排序的效率

总结

Vue.js 设计与实现基于Vue.js 3 深入解析Vue.js 设计细节

相关推荐

评论