本文是lhyt本人原创，希望用通俗易懂的方法来理解一些细节和难点。转载时请注明出处。文章最早出现于本人github
0.前言
相信大家面试的时候都要经历手写什么什么排序这种事情吧，要不就是大概说一下思路。不许用各种语言封装好的函数、api，仅仅用原生的方法把他写出来。虽然看起来没什么意思，但是这也是考察一个人的基础有没有扎实、编程思想好不好的一种方法。
重要的事情说三遍：
主要理解快速排序！！！
主要理解快速排序！！！
主要理解快速排序！！！
而且要滚瓜烂熟！
以下所有的排序都是升序
1.冒泡排序
先说最简单的吧，冒泡，就是指数值大的，就是一个大气泡，慢慢冒到后面（水面）去。对于要排序的数组，一个个去遍历，大的数往后移。往后移怎么做到呢，就是遍历的时候，两个数中（第j和j+1个）要是谁比较大，谁在后面（交换位置）。气泡都聚集在水面（大数都从后面聚集在一起，所以每次第二层遍历都会到len-1-j截止）
时间复杂度O(n^2)，如果是已经排好的情况是O（n）
function bubble(arr){
for(var i = 0,len = arr.length;i
for (var j = 0; i < len-1-j; j++) {
if(arr[j]>arr[j+1]){
var temp = arr[j+1]
arr[j] = arr[j+1]
arr[j] = temp
}
}
}
return arr
}
2.快速排序（重点）
快排是面试问得最多的了，也是目前用得最多，效率最稳的方法。快速排序的最慢情况是O(n²)，升序的时候。但它的数学期望是O(n log n) ，且O(n log n)记号中隐含的常数因子很小，比复杂度稳定等于O(n log n)的归并排序要小很多。对绝大多数顺序性较弱的随机数列而言，快速排序总是占优。
首先，取一个基准值（我们取第一个，也可以取中间、取最后都行），接着让小于基准值的在左边，大于的在右边，分成左右两堆。然后分别对左边和右边那堆采取同样的操作，取基准值，让基准值左边都是小于他的，右边都是大于他的。一直重复操作，直到全部升序。
2.1另外开辟两个空数组
这种方法容易理解，但是依赖另外开辟出来的数组。我们取第一个作为基准，从第二（特别注意，第二个开始！不然栈溢出）个开始遍历，小于基准的数放在左数组（left），大于基准的放在右数组，接着对左数组和右边数组重复操作，再对左边数组的左边和右边进行操作......直到数组长度为1
function quick(arr){
if(arr.length <= 1){
return arr
}
var pivot = arr[0]
var left = []
var right = []
var len = arr.length
for(var i = 1;i
if(arr[i]>pivot){
right.push(arr[i])
}else{
left.push(arr[i])
}
}
return quick(left).concat([pivot],quick(right))
}
当然网上也有人家从中间开始的，中间开始的话，就用splice去除这个值，再给pivot赋值
2.2直接在原数组操作
这种比较难理解，但是不会占用其他内存。基准值也是取第一个，quick传入3个参数：数组，子数组的起始位置、子数组的结束位置。第一次赋值肯定是quick（arr），left和right是undefined，left和right默认是第一个和最后一个数的索引。 partitionIndex是基准值索引。
核心部分是中间判断left
取第一个基准值，从第二个（index）开始遍历。index是目前最后一个小于基准值的索引（其实是留给基准值自己的一个空位）。如果遍历中第i个有小于基准值的，i与index互换，index再+1，这是什么效果呢，可以看一下：8，5，10，7，6的演示
基准值是8，从5开始遍历（var i = index; i <= right; i++）。
i=1发现5<8，arr【1】与arr【1】交换位置，index+1，此时数组不变8，5，10，7，6，但是index已经是2
i=2发现10>8，跳过，index=2
i=3发现7<8，arr【3】与arr【2】交换，8，5，7，10，6，index=3
i=4发现6<8，arr【4】与arr【3】交换，8，5，7，6，10，index=4
遍历已经完成，把基准值和最后一个小于他的arr【index-1】互换6，5，7，8，10，已经完成了基准值左边都是小于他的、右边都是大于他的目的。
一个模块的操作完成，基准值索引partitionIndex变成index-1
接下来就是对分出来的左数组和右数组重复的递归操作
function quick(arr, left, right) {
var len = arr.length,
partitionIndex,
left = typeof left == 'number' ? left : 0,
right = typeof right == 'number' ? right : len-1;
if (left < right) {//保证小于基准值的在左边，大的在右边
var pivot = left, //基准值是数组的第一个
index = pivot + 1; //从数组的第二个开始
for (var i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
var temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
index++;
}
}
var temp = arr[pivot];
arr[pivot] = arr[index - 1];
arr[index - 1] = temp;
partitionIndex = index-1;
quick(arr, left, partitionIndex-1);
quick(arr, partitionIndex+1, right);
}
return arr;
}
3.选择排序
表现最稳定的排序之一，无论什么数据进去都是O(n²)复杂度，但是依赖额外内存保存最小值
数组长度为len的数组中进行选择排序时：
取后len个的最小值放数组第一个位置
取后len-1个的最小值放数组第二个位置
取后len-2个的最小值放数组第三个位置
.......
显然，最后一个就是最大的，前面的已经完成了排序
function select(arr){
var min //保存运算过程中最小值索引
var temp
for (var i = 0,len = arr.length; i
min = i //先默认最小是自己
for(var j = i+1;j
if(arr[min]>arr[j]){
min = j //记录更小的值的索引
}
}
temp = arr[i]
arr[i] = arr[min]
arr[min] = temp
}
return arr
}
4.插入排序
就像打牌一样，自己是怎么整理的呢。拿着一张牌，一个个往下去对比，发现下一个大于（或等于）自己，上一个小于（或等于）自己，那就把他放在中间。复杂度稳定O（n^2）,最好的情况是已经排序完成时O（n），依赖额外内存，保存当前遍历的数
function insert(arr) {
var len = arr.length;
var preIndex, current;
for (var i = 1; i < len; i++) {
preIndex = i - 1;//小于自己的数的索引
current = arr[i];
while(preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex+1] = arr[preIndex];//如果满足条件，把当前的数插入中间
preIndex--;
}
arr[preIndex+1] = current;
}
return arr;
}
5.计数排序
将数组区间取出来（【min，max】），然后对数组进行遍历，计算每一个数组元素在区间【min，max】中出现次数，最后从头到尾把数组写出来。复杂度是O（n），比较稳定，但是依赖额外内存空间
计数排序需要全部都是整数！
这里，我们取正整数来试验，所以只要取得最大值就行。arr的值表示bucket的位置，如果bucket的某个位置是undefined，说明arr里面没有这个位置的索引值
function count(arr) {
var max = Math.max(...arr)//需要知道最大值的，这里只能作弊了
var bucket = new Array(max+1),//一个被max+1个undefined填充的数组
sortedIndex = 0;//重写arr的索引
for (var i = 0; i < arr.length; i++) {
if (!bucket[arr[i]]) {//第一次遇到bucket的某个索引值为arr值，将undefined变成0
bucket[arr[i]] = 0;
}
bucket[arr[i]]++;//开始统计
}
for (var j = 0; j < max + 1; j++) {
while(bucket[j] > 0) {
arr[sortedIndex++] = j;//重写arr
bucket[j]--;//再一次进入同样的循环，直到没有重复值（0的时候）
}
}
return arr;
}
6.基数排序
先比较个位数的大小，按顺序分类，从头到尾重新取出数字。再进行第二次比较，比较十位数的大小，按顺序分类，再从头到尾取出........直到最高位。要求全是整数。
我们这里比较两位数以内的
var counter = [];
function radixSort(arr, maxDigit) {
var mod = 10;
var dev = 1;
for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
for(var j = 0; j < arr.length; j++) {
var bucket = parseInt((arr[j] % mod) / dev);
if(counter[bucket]==null) {
counter[bucket] = [];
}
counter[bucket].push(arr[j]);//和计数排序一样，这里只需要0-9的数组存放
}
var pos = 0;
for(var j = 0; j < counter.length; j++) {
var value = null;
if(counter[j]!=null) {
while ((value = counter[j].shift()) != null) {
arr[pos++] = value;
}
}
}
}
return arr;
}
7.归并排序
由名字可以知道，这其实就是一种递归。顺序是比较前面两个=>比较前面两个的后面两个=>比较前面四个=>比较前面四个的后面两个=>比较前面6个的后面两个=>比较前面8个........
始终都是O（nlogn）的复杂度，不受输入数据影响，但是依赖额外内存
每一次2个数的小组比较，两个小组的数量一致而且排序方式也是升序，对比起来就是一一对比。大的组比较也是一样。数量不同只有数组长度非2的n次方的尾部的比较。
function mergeSort(arr) { //采用自上而下的递归方法
var len = arr.length;
if(len < 2) {
return arr;//递归到子数组长度为1为止
}
var middle = Math.floor(len / 2),//数组被分成左右两个子数组
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right)
{
var 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;
}
原文来源于：lhyt的github
