因为之前面试有问到快排，昨天笔试又有做到关于排序算法的题，所以特地看了一下关于排序算法。前端对算法的要求不高，但是下面这几种易理解的排序算法还是要掌握。
简单介绍及实现
以下的排序均是升序。
冒泡排序
冒泡排序是最简单的排序，即比较前后两个数的大小。
function bubble(arr) {
for(let i = 0, len = arr.length; i < len; i++) {
for(let j = 0; j < len; j++) {
if(arr[j] > arr[j + 1]) {
[arr[j], arr[j+1]] = [arr[j+1], arr[j]];
}
}
}
return arr;
}
选择排序
选择排序首先要选择一个最小值，拿这个最小值与后面未排序的数进行比较，比它更小则调换位置。
function selection(arr) {
let min;
for(let i = 0, len =arr.length; i < len; i++) {
min = arr[i];
for(let j = i+1; j < len; j++) {
if(arr[j] < min) {
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
}
return arr;
}
插入排序
插入排序原理与打扑克时候把牌按顺序插入差不多：从第二张牌开始往前看，数字是否小于第二张牌，处理完以后从第三张牌看，以此类推，从第 n 张牌往前看 n 前面的牌是否小于第 n 个位置的牌。
function insert(arr) {
for(let i = 1, len = arr.length; i < len; i++) {
let target = arr[i];
for(let j = i; j >=0; j--) {
if(arr[j-1] > target) {
arr[j] = arr[j-1];
} else {
arr[j] = target;
break;
}
}
}
return arr;
}
希尔排序
希尔排序是在插入排序的基础上改进的，它会设定一个间隔，而不是每次只有 1 的距离，间隔由大到小，最后为1。
在《算法（第四版）》中 Robert Sedgewick 提出了动态定义间隔序列。（为了方便理解，这里没有动态定义）
function shell(arr) {
let gaps = [5, 3, 1];
gaps.forEach((gap) => {
for(let i = gap, len = arr.length; i < len; i++) {
let target = arr[i];
for(let j = i; j >=0; j -= gap) {
if(arr[j - gap] > target) {
arr[j] = arr[j - gap];
} else {
arr[j] = target;
break;
}
}
}
});
return arr;
}
快速排序
快速排序就是选定一个基准，然后把大于这个基准的作为一边，小于这个基准的作为另一边，再把这两边以相同的规则处理。类似于二分法。
function quick(arr) {
if(arr <= 1) {
return arr;
}
// 假定基准 mid 为 arr 的第一个数
var mid = arr.shift();
var left = [];
var right = [];
arr.forEach((value) => {
if(value <= mid) {
left.push(value);
} else {
right.push(value);
}
});
return quick(left).concat(mid, quick(right));
}
归并排序
这个我也不好解释，复制官方的说法：
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
下面是我找的一个比较形象的演示了归并排序的图：
这里是一个图片演示
function merge(arr) {
var len = arr.length;
if(len <= 1) {
return arr;
}
var midIndex = Math.floor(len/2);
var left = arr.slice(0, midIndex);
var right = arr.slice(midIndex);
return mergeSort(merge(left), merge(right));
}
function mergeSort(left, right) {
var res = [];
while(left.length && right.length) {
if(left[0] < right[0]) {
res.push(left.shift());
} else {
res.push(right.shift());
}
}
while(left.length) {
res.push(left.shift());
}
while(right.length) {
res.push(right.shift());
}
return res;
}
各个排序算法复杂度及稳定性的比较
| 算法类型 | 平均时间复杂度 | 最坏时间复杂度 | 最佳时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n2) | O(n) | O(1) | 稳定 |
| 选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 |
| 插入排序 | O(n2) | O(n2) | O(n) | O(1) | 稳定 |
| 希尔排序 | O(nlogn) | O(nlog2n) | O(nlog2n) | O(1) | 不稳定 |
| 快速排序 | O(nlogn) | O(n2) | O(nlogn) | O(logn) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
（目前还不能理解堆排序，有时间看完二叉树再研究一下堆排序会更新堆排序的内容。）
各类排序算法演示
总结
前端要理解的算法虽然不多，但尽量多学习算法对一些代码优化有帮助，同时方便以后学习其他语言或者深入学习。
