前端工程师算法系列(4)-归并排序

微信扫一扫,分享到朋友圈

前端工程师算法系列(4)-归并排序

归并排序

一、原理解析

归并排序不像前面讲过的几个排序那样直观,为了便于理解,我们先做个问题分解。

假设有两个 已经排序好
的数组:

let arrLeft = [1, 3, 4, 7]
let arrRight = [2, 5, 6, 9]

如何把这 两个已排序好的数组
合并成 一个排序好
的数组呢?

可以新建一个空数组arrResult,比较arrLeft 第一位和 arrRight 第一位,哪个小就把这个数组的第一位拿出来push到空数组里。然后反复执行上面的逻辑,直到arrLeft或者arrRight其中一个变为空数组。最后再把另一个不为空的全部拿出来 push 到arrResult。 以下是代码:

function merge(leftArr, rightArr) {
    var resultArr = []
    while(leftArr.length && rightArr.length) {
      resultArr.push(leftArr[0] <= rightArr[0] ? leftArr.shift() : rightArr.shift())
    }
    return resultArr.concat(leftArr).concat(rightArr)
  }

那回头看看我们要真实解决的问题,如何对一个未排序的数组进行排序呢?

对于如下数组:

let arr = [4, 1, 2, 6, 9, 7, 3, 5]

我们可以把数组分成两部分:

let part1 = [4, 1, 2, 6]
let part2 = [9, 7, 3, 5]

假设我们已经写好了我们最终要实现的排序方法 mergeSort。那么
mergeSort(arr)

等价于
merge(mergeSort(part1), mergeSort(part2))

。 即:对数组 arr 的排序,等价于把数组分两部分分别对每部分排序得到两个排序的数组,然后再利用刚刚写好的merge 方法把两个已经排序好的数组合并成一个最终排序好的数组。

function mergeSort() {
  //待补充
}

mergeSort(arr) 
//等价于
merge(mergeSort(part1), mergeSort(part2))

要排序一个大数组,可以把这个大数组拆分成两个小数组,把问题转变成分别排序这两个小数组,再把排序后的小数组通过简单的方式合并已排序的大数组。 可是如何排序这两个小数组呢?循环刚刚的逻辑,直到数组拆分到极小(数组长度为1,排序的结果就是自己)。

二、代码实现

以下是 JavaScript 版本的的代码实现:

function mergeSort(arr) {
  var merge = function(leftArr, rightArr) {
    var resultArr = []
    while(leftArr.length && rightArr.length) {
      resultArr.push(leftArr[0] <= rightArr[0] ? leftArr.shift() : rightArr.shift())
    }
    return resultArr.concat(leftArr).concat(rightArr)
  }
  if(arr.length > 1  //取数组的中位下标,也可以用 parseInt(arr.length/2)
  return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)))
}

三、复杂度

平均时间复杂度为 O(nlogn),性能极好。

四、参考

维基百科-归并排序

本文作者:若愚。如果你觉得不错,或者发现文章中的错误,或者有更好的建议,欢迎算法交流群交流,扫码进群(如无法扫描进群,加微信:hungervalley 拉入群)。

点击扫码进微信群

微信扫一扫,分享到朋友圈

前端工程师算法系列(4)-归并排序

iPhone XS Max玩游戏掉帧?实测给你看

上一篇

TCL将进军半导体设备领域? | 半导体行业观察

下一篇

你也可能喜欢

前端工程师算法系列(4)-归并排序

长按储存图像,分享给朋友