前端开发必会的JS算法之归并排序
上一篇我们说了经典排序中的插入排序,本文我们来看一下归并排序,“归并”二字就是“递归”加“合并”。它是典型的分而治之算法。
上图中,先把数组一分为二,然后递归地排序好每部分,最后合并。
其中,分和归相对容易些(后面会说),该算法的核心是:如何合并两个已经排好序的数组?
解决办法很容易想到,两权相较取其轻。
如上图所示,每次比较取出一个相对小的元素放入结果数组中。
翻译成代码:
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 分别是两个数组的下标。遍历结束后,某个数组可能会有剩余,全部追加到结果数组中就可以了:、
if (i < left.length) { result.push(...left.slice(i)) } if (j < right.length){ result.push(...right.slice(j)) }
说明:为了清晰表达二者谁都可能剩余,这里没有直接使用 if...else。事实上不会出现二者都有剩余情况的(while 循环保证的)。另外,这里使用了数组相关 API(concat 也可以),也可以直接使用循环来做。
并,这个核心问题解决了,接下来我们来看看分和归。
关于分,只要把数组从中间劈成两半就行:
let m = Math.floor(array.length / 2) let left = array.slice(0, m) let right = array.slice(m)
至于递归,虽然它不符合线性思维,但其实也没啥难的。
只要有递归步骤(递归公式),很容翻译成代码的。
我们再回忆一下归并算法的步骤:
- 数组分成两半,left 和 right
- 递归处理 left
- 递归处理 right
- 合并二者结果
轻松翻译成代码:
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 时,就是已经是排好序的,不需要再递归调用了。
因此需要在前面加入代码:
if (array.length < 2) { return array }
查看完整代码:
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 算法之插入排序》
码云笔记 » 前端开发必会的JS算法之归并排序
前端正在学习中 头晕啊
加油,小伙伴,有啥不明白的可以互相讨论
前端开发却是非常的牛逼的了