前言
先吐槽。 金三银四，最近来我司计划招聘两名前端工程师，一名初级，一名中级，结果前来面试的人络绎不绝，让我也当面试官，结果呢。前来的有一两年工作经验的初级工程师，都是渣渣，不是基础差，就是广度不够，连笔试题目都做不出来，尤其是算法题目，简单的排序都做不出来。给我的感觉，连刚参加工作的我都不如。而后面试的两个中级工程师，面试后感觉也就比我差点，工作经验比我长点，可是这个期望薪水，是不是有点高呀。只是排序算法题大多用的是冒泡法，作为工程师不应该开口闭口都是快排吗。嗯，只是忽然想想自己也只是知道快排的思想，具体怎么实现，就懵逼了，于是才有了这篇博客。
常见的冒泡法
冒泡法的概念，很是基础，基本上C语言入门书籍，都会介绍一遍。算法实现和其名字一样冒泡，(从小到大排)高个子从数组的低序号冒泡到高序号，并结束本轮循环。下轮循环的时候，剔除掉已经排好序的高个子，开始排下个高个子，这样需要写到两个循环。具体实现如下：
const bubbleSort = (arr) => {
const arrLength = arr.length;
let temp;
for(let i = 1; i < arrLength; i++ ) {
for(let j = 0; j < arrLength - i; j++) {
if(arr[j] > arr[j + 1]) {
temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
如此计算，自然可以简单的想到啦，当然还有另外一种更傻的方法，就是每次都出一个数字正确排序，再求出下个数的正确排序，如此下来，也是能实现，只是算发并不不好看，先看看具体实现：
const rubbishSort = (arr) => {
const arrLength = arr.length;
let sameControl = {};
let result = [];
for(let i = 0; i < arrLength; i++) {
let target = arr[i],
left = 0,
same = 0;
for(let j = 0; j < arrLength; j++) {
if(arr[j] < target) {
left++;
}
if(arr[j] === target) {
same++;
}
}
if(result[left] === undefined) {
for(let resultIndex = left; resultIndex < left + same; resultIndex++) {
result[resultIndex] = target;
}
}
}
return result;
}
上面算法一看还是很麻烦的，为了相同的元素还特地设置了 same 变量，虽然最后也是能实现排序的，只是其计算的步骤却是要比冒泡法高很多的，不仅仅有两个长度为 arrLength 的 for 循环，在最后一个循环里面还要做两次判断。而冒泡法，第二个 for 循环 就要精简很多了。
大O表示法
要如何判断哪种算法更好呢？常用的比较方法是运行时间，通过运行时间来比较，运行时间越少的，自然越优，毕竟计算机是按照一条条指令并行处理的。大O表示法是种特殊的表示法，指出运行速度的快慢。
对于长度为 n 的数组，若用冒泡法需要循环 n 次，每次循环长度从 n 一直下降到 0，可以求得其运行时间为 n²/2，用大O表示法就是 O(n²)，大O法是自然省略前面的常数的。若用第二种算法，逻辑基本差不多，但是其运行时间为 n²，用大O表示法就是 O(n²)。可以看出来后一种的运行时间足足是前者的两倍之长。
虽然如此，但是 O(n²) 这样的时间，你可以忍？如果有1000个数字，那岂不要花 1,000,000 次计算。想想要是计算机这么搞，岂不是累死了。
快速排序算法
面对传统的这些方法，比如上面，每次排好一个位置都需要循环一遍，效率低下，实在麻烦，有没有更好的办法？分而治之就提供了一个很好的思路，就是要将问题从大化小，一个个简单击破，最后合并在一起就好了。在排序的体现上就是将待排序的数组不断的拆分成小数组，最后划分到根本不用排序的数组，再排序合并。
具体怎么做呢？先看看快速排序（Quicksort）的Javascript实现 这里阮老师给出的思想是：
在数据集之中，选择一个元素作为"基准"（pivot）
**通过基准值pivot来实现分而治之的思想，**拆分出小的单元，再仿佛拆分。具体如下：
var quickSort = function(arr) {
if (arr.length <= 1) { return arr; }
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++){
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
};
这么一看很有分而治之的味道，每次将数组分为两半，分别排序，从而降低迭代次数，实现了优化。在最优的时候，每次都可以将数组分成两半，**于是调用栈为 O(logN)，底数为2，每次调用排序数量为 n，所以时间复杂度为 O(NlogN)，**相比于冒泡的 O(n²)，快了特别多，如当 n = 10000 的时候，相差1000倍。这个过程其实和二分法有点类似了。
上面算法看着好简单，难道传说中的快速排序就是这样的？在上面的例子中可以发现，主要通过 left 和 right 来进行数据存储，也就是说其每次迭代的空间复杂度为 O(n)，而迭代次数为 O(logN)，所以总的空间复杂度为 O(NlogN)。此时，意味着随着待排序对象的加长，其所占用的空间会不断叠加，与之对比冒泡排序的空间复杂度。。。嗯，不就是 O(1)嘛，
空间复杂度的提高也会影响性能。那有没有运行时间又少，空间复杂度又低的呢？下面给出我自己下的方法：
const quickSort = (arr, left, right) => {
if (arr.length <= 1) {
return arr;
}
left = left || 0;
right = right || arr.length - 1;
const target = arr[left];
const leftInit = left;
const rightInit = right;
let leftEnd;
let rightStart;
let temp;
left++;
if(left === right) {
if(target > arr[right]) {
temp = arr[left - 1];
arr[left - 1] = arr[right];
arr[right] = temp;
}
return false;
}
while(left < right) {
while(arr[left] <= target && left < right) {
left++;
}
while(arr[right] > target && left < right) {
right--;
}
if(left < right ) {
temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
if(left === right) {
if(target > arr[left]) {
arr[leftInit] = arr[left];
arr[left] = target;
leftEnd = left - 1;
} else if(leftInit !== left -1) {
arr[leftInit] = arr[left - 1];
arr[left - 1] = target;
leftEnd = left - 2;
rightStart = left;
} else {
rightStart = left + 1;
}
}
}
if(leftEnd !== undefined) {
qs(arr, leftInit, leftEnd);
}
if(rightStart !== undefined) {
qs(arr, rightStart || right, rightInit)
}
}
（吐个槽，quickSort 方法，写了一个小时半才写好，一开始以为很简单，结果跑一下，才发现各种bug，实在惭愧，现在有点体谅那些写不出快速排序的面试者了）
具体的思想可以参考这篇 博客。上面的 quickSort 的思想还是很简单的，通过两边不断的推移，将小于 target 的数放在左边，大于 target 的数放在右边。只是可能出现左边的数都小于 target，又或者是左边的数都大于 target，所以需要特别处理，导致复杂度提高了。
这时候看到了 聊聊前端排序的那些事 上面介绍到排序 sort 在 Chrome 中的实现，核心部分还是快速排序，原来 Chrome 里面也是用 JavaScript 来实现 sort 方法的！具体源码，只是没有想到 Chrome 里面居然用了 partition 来跳转 js 代码，太可怕了。
chrome 里面先是对输入数组范围小于10的，采用插入排序，包括迭代过程中也是，否则采用快排。快排中采用三点取值，分别是首尾数值，和中间数值。中间数值的下标会根据数组是否大于 1000 来分情况生成，具体情况请看源码。随后对这三个数值排序，取中间值作为基准。采用的快速方法和上文中的第二种思路相似的，只是用了 for 循环和一个 do while 循环，实现起来也是麻烦不少，但是估计速度会更快，更优秀吧。
快排复杂度
前面有提到快速排序算法的运算时间为 O(NlogN)，这是根据调用栈和每次调用量，来计算的，但是其调用栈却不总是 O(logN)，O(logN) 是建立在每次循环取基准值刚好是该数组的中间值，如果不是中位数值呢？如对数组[1, 2, 3, 4, 5]，这种混乱度低的数组，如果还是用从 0 下标开始的快速排序算法，那其计算下来和普通的冒泡法的运行时间是相似的。
由于这种原因，Chrome 里面的快排用三值分而治之，保证随机性，提高快排的运算效能。快排的最糟糕运行时间为 O(n²)，最佳为 O(NlogN)，当然平均时间为 O(NlogN)，基准值取值随机的情况下， O(n²) 是低概率事件。
归并排序
在 聊聊前端排序的那些事 中看到Firefox采用归并排序，具体缘由文中后面后面也是介绍了一下历史，但是归并排序是什么呢？思路如下图所示
算法也挺简单的，如下：
const mergeSort = (arr) => {
const len = arr.length;
if(len < 2) {
return arr;
}
const middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
const merge = (left, right) => {
let result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length) {
result.push(left.shift());
}
while (right.length) {
result.push(right.shift());
}
return result;
}
上面代码计算参考 这篇博客。
归并也是采用分而治之的思路，和二分法的思路有些接近，就像上图一样，把数组整体分割成最小单元，两个元素或则一个元素。先从小数组中排序，再和相邻的数组间排序，一级一级往上走。可以知道这种方式下，调用栈肯定是 O(logN)，而每次调用运算为 N，所以其运算时间为 O(NlogN)。其运行时间比快排还要稳定，是稳定排序，只是问题在于 result 数组，归并运算的问题在于其空间复杂度为 O(NlogN)，和阮老师里面提到的快速算法空间复杂度是一致的，其实由于反复递归，每次递归的代码执行栈是很高的，相对于上文自己写的快速排序还是有很大差别的。
其他排序
其他排序还有一些很经典的：
- 插入排序。插排序如同打扑克牌，插入牌一样。从第二个元素开始，每个数都回溯其应该排序位置，和冒泡法的套路有点像。
- 选择排序；
- 堆排序； 当然还有很多，只是怕全都看完容易忘记，还是记住三个常见有用的算法吧。
关于排序，还有个有趣的地方，数组的完全随机排列，洗牌算法和排序算法之间的矛盾问题，算是一个扩展吧。
ps: 为何网上查找的快速排序算法大多不是快速排序，或者是错误的，这如何是好。。。。。。 另外块排是不稳定排序，这也是个隐患。以后可以出个面试题，哈哈哈哈