本文是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