排序
JS本身数组的sort方法,可以满足日常业务操作中很多的场景了。
但很多时候我们还需要知道选择排序 冒泡排序 和快速排序 的方式。
冒泡排序
文字例子:
1 | E A D B H //原始序列 |
动图:
代码实现
1 | function bubleSort(arr) { |
选择排序
选择排序是从数组的开头开始,将第一个元素和其他元素作比较,检查完所有的元素后,最小的放在第一个位置,接下来再开始从第二个元素开始,重复以上一直到最后。
动图:
外层循环从0开始到length-1, 然后内层比较,最小的放开头,代码:
1 | function selectSort(arr) { |
插入排序
插入排序核心–扑克牌思想: 就想着自己在打扑克牌,接起来一张,放哪里无所谓,再接起来一张,比第一张小,放左边,继续接,可能是中间数,就插在中间….依次。
动图:
原理:
首先将待排序的第一个记录作为一个有序段。
从第二个开始,到最后一个,依次和前面的有序段进行比较,确定插入位置。
1 | function insertSort(arr) { |
其实和冒泡排序很相似,只是将换位置放到了最后一步。
乍一看,好像插入排序速度还不慢,但是要知道: 当序列正好逆序的时候,每次插入都要一次次交换,这个速度和冒泡排序是一样的,时间复杂度O(n²); 当然运气好,前面是有序的,那时间复杂度就只有O(n)了,直接插入即可。
|排序算法|平均时间复杂度|最坏时间复杂度|空间复杂度|否稳定|
|–|–|–|–|–|–|–|
|冒泡排序|O(n²)|O(n²)|O(1)|是|
|选择排序|O(n²)|O(n²)|O(1)|不是|
|插入排序|O(n²)|O(n²)|O(1)|是
还有一些更高级的排序算法,但是稳定性并不高,这里就不在写了。
递归
递归,其实就是自己调用自己。
递归步骤:
寻找出口,递归一定有一个出口,锁定出口,保证不会死循环
递归条件,符合递归条件,自己调用自己。
例子:
实现对一个对象(object)的深度克隆:
1 | //所谓深度克隆,就是当对象的某个属性值为object或array的时候,要获得一份copy,而不是直接拿到引用值 |
这个代码不够简洁,改造一下:
1 | function deepClone(source) { |
例子:实现一个Array flat()方法,将嵌套数组扁平化。
1 | var arr1 = [1, 2, [3, 4]]; |
本文中的图片来源:https://visualgo.net/zh