排序

JS本身数组的sort方法,可以满足日常业务操作中很多的场景了。
但很多时候我们还需要知道选择排序 冒泡排序 和快速排序 的方式。

冒泡排序

文字例子:

1
2
3
4
5
6
E A D B H //原始序列
A E D B H //经过一次计算(A、E交换)
A D E B H //再次计算(D、E交换)
A D B E H //再次计算(B、E交换)
//将上面所有的循环再循环 arr.length-2次
A B D E H //最终结果

动图:

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function bubleSort(arr) {
var len = arr.length;
//比较多少个循环,内部循环一次少一次
for (let outer = len ; outer >= 2; outer--) {
//前后比较,从第1个开始
for(let inner = 0; inner <=outer - 1; inner++) {
if(arr[inner] > arr[inner + 1]) {
let temp = arr[inner];
arr[inner] = arr[inner + 1];
arr[inner + 1] = temp;
//[arr2[0],arr2[1]] = [arr2[1],arr2[0]] //这一步可用ES6解构赋值实现位置交换
}
}
}
return arr;
}

选择排序

选择排序是从数组的开头开始,将第一个元素和其他元素作比较,检查完所有的元素后,最小的放在第一个位置,接下来再开始从第二个元素开始,重复以上一直到最后。

动图:

外层循环从0开始到length-1, 然后内层比较,最小的放开头,代码:

1
2
3
4
5
6
7
8
9
10
11
12
function selectSort(arr) {
var len = arr.length;
for(let i = 0 ;i < len - 1; i++) {
//从第i个开始,比较第i个和第j个的大小,小于第i个就交换,知道不小于,再累加i
for(let j = i ; j<len; j++) {
if(arr[j] < arr[i]) {
[arr[i],arr[j]] = [arr[j],arr[i]];
}
}
}
return arr
}

插入排序

插入排序核心–扑克牌思想: 就想着自己在打扑克牌,接起来一张,放哪里无所谓,再接起来一张,比第一张小,放左边,继续接,可能是中间数,就插在中间….依次。

动图:

原理:

首先将待排序的第一个记录作为一个有序段。
从第二个开始,到最后一个,依次和前面的有序段进行比较,确定插入位置。

1
2
3
4
5
6
7
8
9
10
11
12
function insertSort(arr) {
for(let i = 1; i < arr.length - 1; i++) { //外循环从1开始,默认arr[0]是有序段
for(let j = i; j > 0; j--) { //j = i,将arr[j]依次插入有序段中进行比较,第j个大于第i个就终端换下一个
if(arr[j] < arr[j-1]) {
[arr[j],arr[j-1]] = [arr[j-1],arr[j]];
} else {
continue;
}
}
}
return 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//所谓深度克隆,就是当对象的某个属性值为object或array的时候,要获得一份copy,而不是直接拿到引用值
function deepClone(origin,target) { //origin是被克隆对象,target是我们获得copy
var target = target || {}; //定义target
for(var key in origin) { //遍历原对象
if(origin.hasOwnProperty(key)) {
if(Array.isArray(origin[key])) { //如果是数组
target[key] = [];
deepClone(origin[key],target[key]) //递归
} else if (typeof origin[key] === 'object' && origin[key] !== null) {
target[key] = {};
deepClone(origin[key],target[key]) //递归
}
target[key] = origin[key];
}
}
return target;
}

这个代码不够简洁,改造一下:

1
2
3
4
5
6
7
function deepClone(source) {
let sourceCopy = source instanceof Array ? [] : {};
for (let item in source) {
sourceCopy[item] = typeof source[item] === 'object' ? deepClone(source[item]) : source[item];
}
return sourceCopy;
}

例子:实现一个Array flat()方法,将嵌套数组扁平化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var arr1 = [1, 2, [3, 4]];
arr1.flat(); // [1, 2, 3, 4]
//实现
Array.prototype.flat = function() {
var arr = [];
this.forEach((item,idx) => {
if(Array.isArray(item)) {
arr = arr.concat(item.flat()); //递归去处理数组元素
} else {
arr.push(item) //非数组直接push进去
}
})
return arr; //递归出口
}

本文中的图片来源:https://visualgo.net/zh