关闭

JavaScript 实现归并排序

时间: 2020-10-04阅读: 101标签: 算法

在本文中,我们学习 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 实现。它是基本排序算法之一,可以帮助我们更好的了解分治法策略。

原文:https://stackabuse.com/merge-sort-in-javascript/


    站长推荐

    1.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

    2.广告联盟: 整理了目前主流的广告联盟平台,如果你有流量,可以作为参考选择适合你的平台点击进入

    链接: http://www.fly63.com/article/detial/9812

    关闭

    原生Js获取数组中最长的连续数字序列的方法

    给定一个无序的整数序列, 找最长的连续数字序列。例如:给定[100, 4, 200, 1, 3, 2],最长的连续数字序列是[1, 2, 3, 4]。此方法不会改变传入的数组,会返回一个包含最大序列的新数组。

    React 中 Virtual DOM 与 Diffing 算法的关系

    Virtual DOM 是一种编程理念。UI 信息被特定语言描述并保存到内存中,再通过特定的库,例如 ReactDOM 与真实的 DOM 同步信息。这一过程成为 协调 (Reconciliation)。上述只是 协调算法

    轻松搞定时间复杂度

    通过学习本文,你可以掌握以下三点内容:为什么需要时间复杂度;时间复杂度怎么表示;怎样分析一段代码的时间复杂度,相信认真阅读过本文,面对一些常见的算法复杂度分析,一定会游刃有余

    JavaScript实现获取两个排序数组的中位数算法示例

    给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。你可以假设 nums1 和 nums2 不同时为空。

    RSA 背后的算法

    随着科技发展,计算能力越来越强,特别是量子计算的兴起,我们对超大质数的位数要求也越来越高,512 bit 的 RSA 已经被破解,而 1024 bit 也已经摇摇欲坠,现阶段 2048 bit 长度还是安全的,可是未来,谁又知道呢?

    从js讲解时间复杂度和空间复杂度

    今天有同事在检查代码的时候,由于函数写的性能不是很好,被打回去重构了,细思极恐,今天和大家分享一篇用js讲解的时间复杂度和空间复杂度的博客;复杂度的表示方式之前有看过的,你可能会看到这么一串东西

    不懂算法,还想进大厂?做梦吧

    学算法,刷题蛮干是不行的,需要遵循科学的方法。以下的经验技巧,对于算法新手,或大学没有搞过ACM,想利用业余时间提升算法能力的同学比较有帮助,对于算法高手和ACM大牛

    JS常见算法题目

    JS常见算法题目:xiaoshuo-ss-sfff-fe 变为驼峰xiaoshuoSsSfffFe、数组去重、统计字符串中出现最多的字母、字符串反序、深拷贝、合并多个有序数组、约瑟夫环问题

    JavaScript字符串压缩_js实现字符串压缩

    设计一种方法,通过给重复字符计数来进行基本的字符串压缩。例如,字符串 aabcccccaaa 可压缩为 a2b1c5a3 。而如果压缩后的字符数不小于原始的字符数,则返回原始的字符串。 可以假设字符串仅包括a-z的字母

    Js实现首字母大写

    一小段字母文本可以手动输入进行字母大小写的改变,如果是一大段文本只好借助程序来实现,中字母大小写转换是基本功能。 返回一个字符串,确保字符串的每个单词首字母都大写,其余部分小写

    点击更多...

    内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!