常见的排序算法

[lhyt]

0.前言

相信大家面试的时候都要经历手写什么什么排序这种事情吧，要不就是大概说一下思路。不许用各种语言封装好的函数、api，仅仅用原生的方法把他写出来。虽然看起来没什么意思，但是这也是考察一个人的基础有没有扎实、编程思想好不好的一种方法。我们也可以发现一个规律，稳的算法一般是for循环，不稳的算法比较快，一般用while循环
重要的事情说三遍：
主要理解快速排序！！！
主要理解快速排序！！！
主要理解快速排序！！！
而且要滚瓜烂熟！
以下所有的排序都是升序

1.冒泡排序

先说最简单的吧，冒泡，就是指数值大的，就是一个大气泡，慢慢冒到后面（水面）去。对于要排序的数组，一个个去遍历，大的数往后移。往后移怎么做到呢，就是遍历的时候，两个数中（第j和j+1个）要是谁比较大，谁在后面（交换位置）。气泡都聚集在水面（大数都从后面聚集在一起，所以每次第二层遍历都会到len-1-j截止）
时间复杂度O(n^2)，如果是已经排好的情况是O（n）

function  bubble(arr){
	for(var i = 0,len = arr.length;i<len;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<len;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直接在原数组操作(不用slice的)

这种不会占用其他内存。基准值也是取第一个，quick传入3个参数：数组，子数组的起始位置、子数组的结束位置。第一次赋值肯定是quick（arr），l和r是undefined，l和r默认是第一个和最后一个数的索引。 pindex是基准值索引。
核心部分是中间判断l<r的操作
取第一个基准值，从第二个（current）开始遍历。current是目前最后一个小于基准值的索引（其实是留给基准值自己的一个空位）。如果遍历中第i个有小于基准值的，i与current互换，current再+1，这是什么效果呢，可以看一下：5,8,3,6,2,4的演示

初始：l = 0,pindex = 0,current = 0 + 1 = 1,i = 1,l、r分别指分组最左边和最右边索引
i=1, 5<8 跳过 5,8,3,6,2,4
i=2,5>3，arr[current]与arri交换位置 5,3,8,6,2,4, current + 1 = 2
i=3,5<6，跳过 5,3,8,6,2,4
i=4,5>2，arr[current]与arri交换位置，5,3,2,6,8,4 ,current + 1 = 3
i=5,5>4，arr[current]与arri交换位置，5,3,2,4,8,6 ,current + 1 = 4
最后基准值pindex塞在current前面，继续递归 3,2,4,5,8,6，已经完成了基准值左边都是小于他的、右边都是大于他的目的。接下来就是递归

	function  quick(arr,l,r) {
		var len = arr.length
		var l = typeof l === 'number' ? l:0;
		var r = typeof r === 'number' ? r:len - 1;
		if(l < r){
			var pindex = l;
			var current = pindex + 1;
			var i = current;
			while(i <= r){
				if(arr[i] < arr[pindex]){
					var temp = arr[i];
					arr[i] = arr[current];
					arr[current] = temp;	
					current++;				
				}
				i++
			}
			var tmp = arr[pindex];
			arr[pindex] = arr[current-1];
			arr[current -1] = tmp;
			var currentIndex = current -1;
			quick(arr,l,currentIndex - 1);
			quick(arr,currentIndex+1,r);
		}
		return arr
	}

2.3头尾指针（前面扯了个假快排）

先抛出我的话：看见快排有push、splice之类的，99%是假的，那个1%是闲得蛋疼的。估计是阮一峰很久之前的博客中毒太深（人非圣贤，孰能无过，而且这是他写的很远古的时代的文章了，网上的博客也是你抄我我抄你，c某dn积分，大家懂的）。其实，阮一峰 那种方法只是为了方便理解而已，浪费了空间，而且splice会使时间更长。我是付出了惨痛的教训才相信这个事实，因为写阮一峰的快排，面试挂过。

你问人家，人家说，快排就是取基准值，大的放右边小的放左边，然后递归，这就是错了，只是实现了视觉上的快排，而且浪费空间。所以说，我们不要被网上一些文章的假的快排欺骗了。他真正的方法是，从两边开始，比如数组6，3，8，7，4，2，9

• 取基准值6，指针i为1，j为6（最后一个）
• j--，直到遇到遇到比6小的2停下来
• i++，j停下来i开始动，直到遇到比6大的8
• 2和8交换，变成6，3，2，7，4，8，9
• 继续j--，遇到4，i遇到7，交换
• 变成了6，3，2，4，7，8，9
• j--，撞上了i，结束了循环，6和4交换
  最后是，4，3，2，6，7，8，9
  然后就拿着6左边的和6右边的重复递归
  需要注意的边界条件：

1. 如果已经排序好，就是一个顺序，比如6，7，8，9，j--直接撞上了i（此时i是1，所以平时判断碰撞的时候，需要加上，i>1，或者是！==1），所以我们可以直接返回这一段了。
2. 如果数组长度小于3，自己手动排好他吧

function quick(arr) {
	if(arr.length<3){//这里偷个懒
		return arr.sort((a,b)=>a-b);
	}
	var len = arr.length;
	var i =0;
	var j = len - 1;
	var p = arr[0];
	while(i<=j){
		while(arr[j]>=p&&i<j){//直到尾部遇到小于基准值，取值范围注意必须不能和下面有交集
			j--;
		}
		while(arr[i]<p&&i<j){//直到头部遇到大于等于基准值的，取值范围注意必须不能和上面有交集
			i++;
		}
		var temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
		if(i === j){
			break;
		}
	}
	return quick(arr.slice(1,i+1)).concat([p],quick(arr.slice(i+1)))
}

但是依赖slice!

2.4 改进版本

做算法，就不应该依赖api，结合第二三种快排的思想，我们再来个不用api的：

function quick(arr){
	!function sort(arr, l, r) {
		if (l >= r) {
	        return;
	    }
		if(r - l === 2){
			if(arr[l]>arr[r]){
	            var temp = arr[l];
	            arr[l] = arr[r];
	            arr[r] = temp;				
			}
			return
		}
	    var len = arr.length,l = typeof l === 'number' ? l:0,
	    r = typeof r === 'number' ? r:len - 1,
	    i = l,j = r,p = arr[l]; 
	    var m_from = l;
	    var m_to = r;
	    while (i < j) {
	        while (arr[j] >= p && i < j) {
	            j--;
	        }
	        while (arr[i] <= p && i < j) {	           
	        	i++;
	        }
	            var temp = arr[i];
	            arr[i] = arr[j];
	            arr[j] = temp;

	    }
	    arr[l] = arr[i];
	    arr[i] = p;
	    sort(arr, l, i - 1);
	    sort(arr, i + 1, r);
	}(arr);
    return arr
}

写个iife纯属强迫症，其实可以在里面那个函数直接返回arr，但是我觉得中间返回很多arr没用，就不让他返回

2.5 如果有很多重复

在上面的基础上，我们再改进一下

function quick(arr,l,r){
		if (l >= r) {
	        return;
	    }
		var len = arr.length,l = typeof l === 'number' ? l:0,
		    r = typeof r === 'number' ? r:len - 1,
		    i = l,j = r,p = arr[l]; 
		    var m_from = l;
		    var m_to = r;
		    while (i < j) {
		        while (arr[j] >= p && i < j) {
		        	if(arr[j] === p){ //新增部分
		        		swap(arr,j,m_to);
		        		m_to--;
		        	}
		            j--;
		        }
		        while (arr[i] <= p && i < j) {	 
		        	if(arr[i] === p){//新增部分
		        		swap(arr,i,m_from);
		        		m_from++;
		        	}	                  
		        	i++;
		        }
		        if(i==j){
		        	break;
		        }
		        //此时i和j是临界点，i的元素是小于p的
		        swap(arr, i, j);
		    }
		    while(m_from>l){ //新增部分
		    	swap(arr,m_from-1,i);
		    	i--;
		    	m_from--;
		    }
		    while(m_to<r){//新增部分
		    	swap(arr,m_to+1,j+1);
		    	j++;
		    	m_to++;
		    }
		    //ij是边界，i不包含基准值，j包含基准值
		    quick(arr,l,i);
		    quick(arr,j+1,r);
		    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 <len-1; i++) {
		min = i //先默认最小是自己
		for(var j = i+1;j<len;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;
}