首先,在切入正题之前,先提一下某同事前段时间的面试。前段时间某同事去某大厂面试,面的不好。面试问到的好多深入的问题,没答上来或者答得不全。大厂就是大厂,要求面试者不仅在广度上,而且在深度上也都要有一定的积累,个人理解就是你不仅要知道这是什么,而且还要知道这是为什么,甚至还要知道这样有什么好处和不好之处。一路面下来,各种被鄙视。比如,前端的优化方法有哪些,说说你在工作中做了哪些优化?Web 安全有哪些,又是如何去防御或者规避?HTTP 缓存的原理,缓存的过程是什么样子的?等等……当然,也问到了一些简单的算法问题,当时有点懵逼了,虽然大学的时候学过,但是时间久了,统统还给老师了,尴尬。对于算法,虽然相对后端语言来说,前端工作中还是比较少接触算法的,就算会接触,大都不会太复杂,但是一些简单的算法也是不得不知道的,大厂们都比较重视这个。

排序。排序是我们最常见的算法题目,当然工作中也会遇到(前端 js API 里面已经有封装一个叫 sort 的方法),但,后面将要介绍几种排序是用 js 实现的方法。在这里整理一下,需要的时候可以翻看一下;

查找。顺便总结一下常见的一些查找,如二分查找。

一、冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
function BubbleSort(arr) {
var len = arr.length;
for (var i = len - 1; i > 0; i--) {
for (var j = 0; j < i; j++) {
if (arr[j] > arr[j+1]) {
var temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}

复杂度:

平均时间复杂度 最好情况 最坏情况 空间复杂度 稳定性
O(n^2) O(n) O(n^2) O(1) 稳定

二、选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function SelectionSort(arr) {
var len = arr.length;
for (var i = 0; i < len; i++) {
var min = arr[i];
var index = i;
for (var j = i + 1; j < len; j++) {
if (arr[j] < min) {
min = arr[j];
index = j;
}
}
if (index != i) {
var temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
}
}
return arr;
}

复杂度:

平均时间复杂度 最好情况 最坏情况 空间复杂度 稳定性
O(n^2) O(n^2) O(n^2) O(1) 不稳定

三、插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function InsertionSort(arr) {
var len = arr.length;
for (var i = 0; i < len - 1; i++) {
var insert = arr[i+1];
var index = i + 1;
for (var j = i; j >= 0; j--) {
if (insert < arr[j]) {
arr[j+1] = arr[j];
index = j;
}
}
arr[index] = insert;
}
return arr;
}

复杂度:

平均时间复杂度 最好情况 最坏情况 空间复杂度 稳定性
O(n^2) O(n) O(n^2) O(1) 稳定

四、希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function ShellSort(arr) {
var len = arr.length;
var gap = Math.round(len / 2);
while (gap > 0) {
for (var i = gap; i < len; i++) {
var insert = arr[i];
var index = i;
for (var j = i; j >= 0; j -= gap) {
if (insert < arr[j]) {
arr[j + gap] = arr[j];
index = j;
}
}
arr[index] = insert;
}
gap = Math.round(gap/2 - 0.1);
}
return arr;
}

复杂度:

平均时间复杂度 最好情况 最坏情况 空间复杂度 稳定性
O(n^1.3) O(n) O(n^2) O(1) 不稳定

五、归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function MergeSort(arr) {
var len = arr.length;
if (len <= 1) {
return arr;
} else {
var num = Math.ceil(len / 2);
var left = MergeSort(arr.slice(0, num));
var right = MergeSort(arr.slice(num, len));
return merge(left, right);
}
}

function merge(left, right) {
var arr = [];
while (left.len > 0 && right.length > 0) {
if (left[0] <= right[0]) {
var temp = left.shift();
arr.push(temp);
} else {
var temp = right.shift();
arr.push(temp);
}
}
if (left.length > 0) {
arr = arr.concat(left);
}
if (right.length > 0) {
arr = arr.concat(right);
}
return arr;
}

复杂度:

平均时间复杂度 最好情况 最坏情况 空间复杂度 稳定性
O(n*log(n)) (n乘以n的以2为底的对数) O(n*log(n)) O(N*log(n)) O(n) 稳定

六、快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function QuickSort(arr) {
var len = arr.length;
if (len <= 1) {
return arr;
} else {
var smaller = [];
var bigger = [];
var base = [arr[0]];
for (var i = 1; i < len; i++) {
if (arr[i] <= base[0]) {
smaller.push(arr[i]);
} else {
bigger.push(arr[i]);
}
}
return QuickSort(smaller).concat(base.concat(QuickSort(bigger)));
}
}

复杂度:

平均时间复杂度 最好情况 最坏情况 空间复杂度 稳定性
O(n*log(n)) (n乘以n的以2为底的对数) O(n*log(n)) O(n^2) O(log(n))~O(n) 不稳定

七、二分查找

二分查找,也称为折半查找,是指在有序的数组里找出指定的值,返回该值在数组中的索引。

  1. 递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 递归实现的js代码
// 查找值为 key 所在数组中的下标
function binary_search2(arr, low, high, key) {
if (low > high) {
return -1;
}
var mid = parseInt((high + low) / 2);
if (arr[mid] === key) {
return mid;
} else if (arr[mid] > key) {
high = mid -1;
return binary_search2(arr, low, high, key);
} else if (arr[mid] < key) {
low = mid +1;
return binary_search2(arr, low, high, key);
}
}

var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 23, 44, 86];
var result2 = binary_search2(arr, 0, 13, 10);
console.log(result2); // 9
  1. 非递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 非递归实现的js代码
// 查找值为 key 所在数组中的下标
function binary_search(arr, key) {
var low = 0;
var high = arr.length - 1;
// 遍历
while (low <= high) {
var mid = parseInt((high + low) / 2);
if (key === arr[mid]) {
return mid;
} else if (key > arr[mid]) {
low = mid + 1;
} else if (key < arr[mid]) {
high = mid -1;
} else {
return -1;
}
}
}

var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 23, 44, 86];
var result = binary_search(arr, 10);
console.log(result); // 9

以上代码是笔者参考网上,经过整理而成,有遗漏之处,欢迎指正。