跳到主要内容位置

归并排序

归并排序是一种以分治(Divide and Conquer)概念为基础的排序算法。

分治 Divide and Conquer

分治指的是,把一个大的问题递归的分解成若干个较小的子问题,直到它们变得简单到可以直接解决。

归并排序原理

归并排序利用分治思想,大体上的算法实现步骤是这样的:

  1. 把数组分成两半。如果是奇数个,那么可以把多余的元素放到任意一边。
  2. 用相同的方式划分子数组,直到子数组只包含一个元素。
  3. 从这些包含单个元素的数组开始,进行合并。并对每个进行合并的数组元素进行排序。
  4. 重复步骤 3,直到合并完成,就得到了排序好的数组。

归并排序 JavaScript 实现代码

归并排序是效率比较高的一种排序算法,掌握它对于面试算法,或者实现排序功能都很有帮助。接下来我们看一下如何使用 JavaScript 来实现归并排序。

function merge(left, right) {
const result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length) result.push(left.shift());
while (right.length) result.push(right.shift());
return result;
}

function mergeSort(items) {
if (items.length < 2) {
return items;
}
const middle = Math.floor(items.length / 2);
const left = items.slice(0, middle);
const right = items.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}

这个代码是一个比较简单的归并排序算法实现,大体上有这样几个部分:

  • mergeSort 函数是用来递归的把原数组划分成子数组,每次分成左右两部分,直到子数组中只有一个元素。
    • 里边计算数组的中间元素索引,然后使用数组的 slice 方法把它们分成两半,奇数个元素会把多余的元素分到右边。
    • 之后调用 merge 函数,合并左右两个子数组。
  • merge 函数是用来把子数组排序后,合并成一个大数组,最终合并为和原始数组长度一样的结果数组。
    • 在 merge 中,因为左右两个子数组已经是基本有序的,所以只要比对两个数组中的第一个元素,较小的放到结果数组前边,较大的放到右边。
    • 放到结果数组中的元素,会从 left 或者 right 数组中删除,这里使用了 shift() 方法。
    • 如果有的数组元素多,剩余的元素会一次性添加到结果数组中。

完成之后,就会得到排好序的数组。 现在,我们用一个测试数组来看一下代码的执行过程:

const testArr = [3, 1, 6, 7, 2, 4, 5];
const result = mergeSort(testArr);

console.log(result);

测试归并排序代码

假设我们的数组有这样的元素:3, 1, 6, 7, 2, 4, 5。

归并排序就像是遍历树一样,在第一次调用 mergeSort() 函数的时候,数组分成了[3, 1, 6][7, 2, 4, 5] 两部分。

之后 [3, 1, 6] 分成 [3][1, 6]

[3] 不能再分了,最左侧的节点遍历完成,开始遍历右半边。

[1, 6] 再分成 [1][6],这样左子树遍历完毕,开始合并。

[1][6] 因为都只有一个元素,1 比 6 小,把 1 放前边,合并成 [1, 6]。并且没有剩余的元素,merge 函数会返回结果。

[3] 这里只有一个节点,它本身不用合并。

之后 返回上一层,[3][1, 6] 合并,判断 3 比 1 大,先把 1 放到结果数组中,然后 3 比 6 小,把 3 放到结果数组中,最后把剩余的 6 放到结果数组,形成 [1, 3, 6]

接下来继续分割右面的 [7, 2, 4, 5],变成 [7, 2][4, 5]

[7, 2],分成 [7][2]

之后进行合并,7 比 2 大,合并成 [2, 7]

再分割 [4, 5][4][5],之后合并成 [4, 5]

合并 [2, 7][4, 5],2 比 4 小,先放 2,然后 7 比 4 大,放 4,7 比 5 大,放 5,最后放 7,形成 [2, 4, 5, 7]

最后 [1, 3, 6][2, 4, 5, 7] 合并,用同样的比对方法,形成 [1, 2, 3, 4, 5, 6, 7]

这样排序就完成了。

算法复杂度

归并排序的算法复杂度在最坏情况下是 O(Nlog(N))。

小结

好了,这个就是归并排序的原理和 JavaScript 实现代码,当然,归并排序的实现方式不止一种,例如还有更省空间的原地排序,不过理解起来可能会更复杂,有兴趣的小伙伴有时间可以自己研究一下。这节课你学会了吗?如果有帮助请三连并关注,想学更多的开发知识,可以在评论区留言,感谢观看!

提示

《Vue 3.x 全家桶完全指南与实战》课程已上线,包括 Vue 3.x、TypeScript、Vue Router 4.x、Vuex 4.x 所有初级到高级的语法特性详解,让你完全胜任 Vue 前端开发的工作。点击查看详情。

新书《JavaScript 基础语法详解》已上架,可在京东、当当、淘宝等各大电商购买