码云笔记前端博客
Home > JavaScript > 前端开发必会的JS算法之归并排序

前端开发必会的JS算法之归并排序

2019-11-04 分类:JavaScript 作者:管理员 阅读(67)

本文共计1484个字,阅读时间预计4分钟,干货满满,记得点赞加收藏哦

上一篇我们说了经典排序中的插入排序,本文我们来看一下归并排序,“归并”二字就是“递归”加“合并”。它是典型的分而治之算法。
前端开发必会的JS算法之归并排序
上图中,先把数组一分为二,然后递归地排序好每部分,最后合并。

其中,分和归相对容易些(后面会说),该算法的核心是:如何合并两个已经排好序的数组?

解决办法很容易想到,两权相较取其轻。
前端开发必会的JS算法之归并排序
如上图所示,每次比较取出一个相对小的元素放入结果数组中。

翻译成代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
let left = [2, 4, 6], i = 0
let right = [1, 3, 5], j = 0
let result = []
while(i < left.length && j < right.length) {
  if (left[i] < right[j]) {
    result.push(left[i])
    i++
  } else {
    result.push(right[j])
    j++
  }
}
console.log(result) // [ 1, 2, 3, 4, 5 ]

代码中,i和j分别是两个数组的下标。遍历结束后,某个数组可能会有剩余,全部追加到结果数组中就可以了:、

1
2
3
4
5
6
if (i < left.length) {
  result.push(...left.slice(i))
}
if (j < right.length){
  result.push(...right.slice(j))
}

说明:为了清晰表达二者谁都可能剩余,这里没有直接使用if...else。事实上不会出现二者都有剩余情况的(while循环保证的)。另外,这里使用了数组相关API(concat也可以),也可以直接使用循环来做。

并,这个核心问题解决了,接下来我们来看看分和归。

关于分,只要把数组从中间劈成两半就行:

1
2
3
let m = Math.floor(array.length / 2)
let left = array.slice(0, m)
let right = array.slice(m)

至于递归,虽然它不符合线性思维,但其实也没啥难的。

只要有递归步骤(递归公式),很容翻译成代码的。

我们再回忆一下归并算法的步骤:

  • 数组分成两半,left和right
  • 递归处理left
  • 递归处理right
  • 合并二者结果

轻松翻译成代码:

1
2
3
4
5
6
function mergeSort(array) {
  let m = Math.floor(array.length / 2)
  let left = mergeSort(array.slice(0, m))
  let right = mergeSort(array.slice(m))
  return merge(left, right)
}

递归是自身调用自身,不能无限次的调用下去,因此需要有递归出口(初始条件)。

它的递归出口是,当数组元素个数为小于2时,就是已经是排好序的,不需要再递归调用了。

因此需要在前面加入代码:

1
2
3
if (array.length < 2) {
  return array
}

查看完整代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
const utils = {
  randomNum() {
    return Math.floor(Math.random() * 100)
  },
  randomArray() {
    return Array.from(Array(this.randomNum()), _ => this.randomNum())
  }
}

function merge(left, right) {
  let result = []
  let i = 0, j = 0
  while(i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++])
    } else {
      result.push(right[j++])
    }
  }
  if (i < left.length) {
    result.push(...left.slice(i))
  } else {
    result.push(...right.slice(j))
  }
  return result
}

function mergeSort(array) {
  if (array.length < 2) {
    return array
  }
  let m = Math.floor(array.length / 2)
  let left = mergeSort(array.slice(0, m))
  let right = mergeSort(array.slice(m))
  return merge(left, right)
}

let array = utils.randomArray()
console.log(mergeSort(array))

至此,归并排序原理和实现已经说完了。

这里总结一下,归并排序需要额外空间,空间复杂度为O(n),不是本地排序,相等元素是不会交换前后顺序,因而是稳定排序。时间复杂度为O(nlogn),是比较优秀的算法,在面试题中出现的概率也很高。

归并排序和下一篇要讲的快速排序,都是分而治之算法,都需要分、归、并。前者重头戏在于如何去并,而后者重头戏在于如何去分。

归并排序,要做到能分分钟手写出来,是需要掌握其排序原理的。其关键在于,通过比较取小来合并两个已递归排好序的数组。至于递归,只要能说清楚递归步骤和出口,就能很容易写出来,不需要死记硬背的。

以上就是前端开发必会的JS算法之归并排序的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持码云笔记!

本系列已经发表文章:
前端开发必会的JS算法之冒泡排序
前端开发必会的JS算法之选择排序
前端开发必会的JS算法之插入排序

「除特别注明外,本站所有文章均为码云笔记原创,转载请保留出处!」

赞(7) 打赏

觉得文章有用就打赏一下文章作者

支付宝
微信
7

觉得文章有用就打赏一下文章作者

支付宝
微信

上一篇:

下一篇:

你可能感兴趣

共有 3 条评论 - 前端开发必会的JS算法之归并排序

  1. vultr Windows NT Chrome 63.0.3239.132

    前端正在学习中 头晕啊

    1. 码云 Windows NT Chrome 69.0.3497.100

      @vultr加油,小伙伴,有啥不明白的可以互相讨论

  2. 超人下拉系统 Windows 7 Chrome 55.0.2883.87

    前端开发却是非常的牛逼的了

博客简介

码云笔记 mybj123.com,一个专注Web前端开发技术的博客,主要记录和总结博主在前端开发工作中常用的实战技能及前端资源分享,分享各种科普知识和实用优秀的代码,以及分享些热门的互联网资讯和福利!码云笔记有你更精彩!
更多博客详情请看关于博客

精彩评论

站点统计

  • 文章总数: 476 篇
  • 分类数目: 13 个
  • 独立页面: 8 个
  • 评论总数: 228 条
  • 链接总数: 15 个
  • 标签总数: 1050 个
  • 建站时间: 525 天
  • 访问总量: 8648071 次
  • 最近更新: 2019年11月21日