首先,在切入正题之前,先提一下某同事前段时间的面试。前段时间某同事去某大厂面试,面的不好。面试问到的好多深入的问题,没答上来或者答得不全。大厂就是大厂,要求面试者不仅在广度上,而且在深度上也都要有一定的积累,个人理解就是你不仅要知道这是什么,而且还要知道这是为什么,甚至还要知道这样有什么好处和不好之处。一路面下来,各种被鄙视。比如,前端的优化方法有哪些,说说你在工作中做了哪些优化?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;
}

二、选择排序

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;
}

三、插入排序

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;
}

四、希尔排序

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;
}

五、归并排序

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;
}

六、快速排序

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)));
}
}

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