您的位置是:网站首页>Javascript编程Javascript编程

JavaScript算法之归并排序算法(详解)

少儿编程网2020-11-19 13:20:32Javascript编程 人已围观 来源:少儿编程 -用户投稿

简介在本文中,我们学习MergeSort背后的逻辑,并用JavaScript实现。最后,在空间和时间复杂度方面将归并排序与其他算法进行比较。归并排序背后的逻辑归并排序使用分而治之的概念对给定的元素列表进行排序。它将问题分解为较小的子问题,直到它们变得足够简单以至可以直接解决为止。以下是归并排序的步骤:1

al0少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

在本文中,我们学习 Merge Sort 背后的逻辑,并用 JavaScript 实现。**后,在空间和时间复杂度方面将归并排序与其他算法进行比较。al0少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

归并排序背后的逻辑

归并排序使用分而治之的概念对给定的元素列表进行排序。它将问题分解为较小的子问题,直到它们变得足够简单以至可以直接解决为止。al0少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

以下是归并排序的步骤:al0少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

1、将给定的列表分为两半(如果列表中的元素数为奇数,则使其大致相等)。al0少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

2、以相同的方式继续划分子数组,直到只剩下单个元素数组。al0少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

3、从单个元素数组开始,合并子数组,以便对每个合并的子数组进行排序。al0少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

4、重复第 3 步单元,直到**后得到一个排好序的数组。al0少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

以数组 [4, 8, 7, 2, 11, 1, 3] 为例,让我们看一下归并排序是如何工作的:al0少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

al0少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

用 JavaScript 实现归并排序

首先实现一个将两个已排序子数组合并为一个已排序数组的函数 merge() 。要注意着两个子数组是已经被排好序的,这一点非常重要, merge() 函数只用于其进行合并。【推荐教程:《JavaScript视频教程》】al0少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

可以通过遍历这两个子数组来实现:al0少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

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 ]
}

在这个函数中,通过把两个排好序的子数组(leftright)合并来获得一个排好序的大数组。首先,创建一个空数组。之后在 leftright 两个子数组中**小元素中的较小的一个,并将其添加到空数组。我们只需要检查 leftright 子数组中的第一个元素,因为它们是已排好序的。al0少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

在这个过程中,从子数组中删除了被选择的元素(通过 shift() 函数实现)。继续这个过程,直到其中一个子数组变为空。**后把非空子数组的剩余元素(因为它们已经被排序)插入主数组的**后面。al0少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

现在有了合并两个已排序数组的代码,接下来为实现归并排序算法的**终代码。这意味着要继续分割数组,直到**终只包含一个元素的数组为止:al0少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

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() 函数合并子数组。al0少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

代码实现后用前面的用例测试一下:al0少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

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

输出符合预期:al0少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

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

归并排序的效率

归并排序的**差时间复杂度为 $O(n\log n)$,与快速排序的**佳情时间复杂度相同。归并排序是目前**快的排序算法之一。al0少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

与快速排序不同,归并排序不是in-place排序算法,这意味着除了输入数组之外,它还会占用额外的空间。这是因为我们使用了辅助数组来存储子数组。归并排序的空间复杂度为 $O(n)$。al0少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

归并排序的另一个优点是非常适合多线程,因为每个被划分出的一半都可以单独排序。另一种常见的减少归并排序运行时间的方法是在到达相对较小的子数组时(大约 7 个元素)使用插入排序。这是因为插入排序在处理小型或几乎排好序的数组时表现非常好。al0少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

总结

在本文中,我们了解了Merge Sort算法背后的逻辑,并用 JavaScript 实现。它是基本排序算法之一,可以帮助我们更好的了解分治法策略。al0少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

更多编程相关知识,请访问:编程视频课程!!

以上就是JavaScript算法之归并排序算法(详解)的详细内容,更多请关注少儿编程网其它相关文章!al0少儿编程网-Scratch_Python_教程_免费儿童编程学习平台

来源:php中文网al0少儿编程网-Scratch_Python_教程_免费儿童编程学习平台


相关文章:

支持一下 ( )

JavaScript算法之归并排序算法(详解)

      匿名评论
    • 评论
    人参与,条评论
    JavaScript算法之归并排序算法(详解)

微信公众号

免费视频教程

先知道