归并排序
归并排序是一种以分治(Divide and Conquer)概念为基础的排序算法。
分治 Divide and Conquer
分治指的是,把一个大的问题递归的分解成若干个较小的子问题,直到它们变得简单到可以直接解决。
归并排序原理
归并排序利用分治思想,大体上的算法实现步骤是这样的:
- 把数组分成两半。如果是奇数个,那么可以把多余的元素放到任意一边。
- 用相同的方式划分子数组,直到子数组只包含一个元素。
- 从这些包含单个元素的数组开始,进行合并。并对每个进行合并的数组元素进行排序。
- 重复步骤 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 实现代码,当然,归并排序的实现方式不止一种,例如还有更省空间的原地排序,不过理解起来可能会更复杂,有兴趣的小伙伴有时间可以自己研究一下。这节课你学会了吗?如果有帮助请三连并关注,想学更多的开发知识,可以在评论区留言,感谢观看!
一系列的课程让你成为高级前端工程师。课程覆盖工作中所有常用的知识点和背后的使用逻辑,示例全部都为工作项目简化而来,学完即可直接上手开发!
即使你已经是高级前端工程师,在课程里也可能会发现新的知识点和技巧,让你的工作更加轻松!
《React 完全指南》课程,连载中现只需 48 元(领取优惠券)点击查看详情。
《Vue 3.x 全家桶完全指南与实战》课程,包括 Vue 3.x、TypeScript、Vue Router 4.x、Vuex 4.x 所有初级到高级的语法特性详解,让你完全胜任 Vue 前端开发的工作。点击查看详情。
《React即时通信UI实战》课程,利用 Storybook、Styled-components、React-Spring 打造属于自己的组件库。
《JavaScript 基础语法详解》本人所著图书,包含 JavaScript 全面的语法知识和新特性, 可在京东、当当、淘宝等各大电商购买