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

归并排序

一、原理解析

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

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

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

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

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

对于如下数组：

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

假设我们已经写好了我们最终要实现的排序方法 mergeSort。那么 mergeSort(arr) 等价于merge(mergeSort(part1), mergeSort(part2)) 。 即：对数组 arr 的排序，等价于把数组分两部分分别对每部分排序得到两个排序的数组，然后再利用刚刚写好的merge 方法把两个已经排序好的数组合并成一个最终排序好的数组。

那mergeSort(part1) 的结果又怎么计算呢？继续遵循上面的逻辑，对 part1继续分解，直到分解为对长度为1的数组进行排序（直接返回即可）。

总结：要排序一个大数组，可以把这个大数组拆分成两个小数组，把问题转变成分别排序这两个小数组，再把排序后的两个小数组通过简单的处理方式“归并为”最终需要的结果。 如何排序这两个小数组呢？循环刚刚的逻辑，直到数组拆分到极小（数组长度为1，排序的结果就是自己）。

二、代码实现

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

三、复杂度

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

本文作者：若愚。喜欢就点个赞，后续才有动力继续更新。如果或者发现文章中的错误，或者有更好的建议，欢迎算法交流群交流，添加微信:hungervalley 拉入群。

往期文章

前端工程师算法系列(1)-冒泡排序

前端工程师算法系列(2)-选择排序

前端工程师算法系列(3)-插入排序