关于javascript:用-JavaScript-实现归并排序

作者：Abhilash Kakumanu

翻译：疯狂的技术宅

原文：https://stackabuse.com/merge-…

未经容许严禁转载

在本文中，咱们学习 Merge Sort 背地的逻辑，并用 JavaScript 实现。最初，在空间和工夫复杂度方面将归并排序与其余算法进行比拟。

归并排序背地的逻辑

归并排序应用 分而治之 的概念对给定的元素列表进行排序。它将问题合成为较小的子问题，直到它们变得足够简略以至能够间接解决为止。

以下是归并排序的步骤：

1. 将给定的列表分为两半（如果列表中的元素数为奇数，则使其大抵相等）。
2. 以雷同的形式持续划分子数组，直到只剩下单个元素数组。
3. 从单个元素数组开始，合并 子数组，以便对每个合并的子数组进行排序。
4. 反复第 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 实现。它是根本排序算法之一，能够帮忙咱们更好的理解分治法策略。

本文首发微信公众号：前端先锋

欢送扫描二维码关注公众号，每天都给你推送陈腐的前端技术文章

欢送持续浏览本专栏其它高赞文章：

• 深刻了解 Shadow DOM v1
• 一步步教你用 WebVR 实现虚拟现实游戏
• 13 个帮你进步开发效率的古代 CSS 框架
• 疾速上手 BootstrapVue
• JavaScript 引擎是如何工作的？从调用栈到 Promise 你须要晓得的所有
• WebSocket 实战：在 Node 和 React 之间进行实时通信
• 对于 Git 的 20 个面试题
• 深刻解析 Node.js 的 console.log
• Node.js 到底是什么？
• 30 分钟用 Node.js 构建一个 API 服务器
• Javascript 的对象拷贝
• 程序员 30 岁前月薪达不到 30K，该何去何从
• 14 个最好的 JavaScript 数据可视化库
• 8 个给前端的顶级 VS Code 扩大插件
• Node.js 多线程齐全指南
• 把 HTML 转成 PDF 的 4 个计划及实现

• 更多文章 …