排序算法

[Lmagic16]

微信图文解释

讲一讲排序算法吧~

先是各个排序算法的性能和适用场景，具体例子，注意的情况，改进的办法

• Chrome 采用的V8引擎的sort在数组长度小于10时采用插入排序（稳定），在数组长度大于10时采用快速排序（不稳定），firefox采用归并排序实现sort；

冒泡排序

//基础版冒泡排序，每轮从序列头开始，两两比较，将较大的值放到最后。
function bubbleSort(arr){
	var len = arr.length;
	for(var i=0;i<len;i++){
		for(var j=0;j<len-1-i;j++){ 
			if(arr[j] > arr[j+1]){ // 两两比较，将最大的冒泡到最后去
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}
		}
	}
	return arr;
}
//改进版冒泡排序
function bubbleSort1(arr){
	var len = arr.length;
	var pos = len;  //设置pos标志量记录每轮最后交换的位置
	for(var i=0;i<len;i++){
		var tempos;
		for(var j=0;j<pos;j++){ // 每轮只需比较到pos位置即可
			if(arr[j] > arr[j+1]){
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
				tempos = j; 
			}
		}
		pos = tempos;
	}
	return arr;
}

选择排序

//选择排序，每轮选择序列中最小的值将其和序列头的值交换。
function selectionSort(arr){
	var len = arr.length;
	for(var i=0;i<len;i++){
		var min = arr[i];
		var pos = i;
		for(var j=i;j<len;j++){ 
			if(arr[j] < min){ // 找出当前序列最小值所在位置
				min = arr[j];
				pos = j;
			}
		}
		var temp = arr[i];//将本轮最小值序列起始值交换
		arr[i] = arr[pos];
		arr[pos] = temp;
	}
	return arr;
}

插入排序

插入排序算法中 处理 数组倒序时最麻烦

//插入排序，从最开始逐步构建有序序列，将下一个值插入到当前有序序列中。
function insertSort(arr){
	var res = [arr[0]];
	for(var i=1;i<arr.length;i++){
		var temp = arr[i];   // 取出当前要插入的值
		for(var j=0;j<res.length;j++){
			if(temp<res[j]){  //若该值小于这个序列，则将该值插入
				res.splice(j,0,temp);
				break;   //这里必须跳出
			}else if(j === res.length-1){ //若该值走到了序列末尾，则直接插入
				res.push(temp);
				break;
			}else if((temp>=res[j]) && (temp<=res[j+1]) ){
				res.splice(j+1,0,temp);
				break;
			}
		}
	}
	return res;
}
//改进版本插入排序,不采用额外数组空间
function insertSortImprove(arr){
	var len = arr.length;
	for(var i=1;i<len;i++){
		j = i;
		temp = arr[i];
		while((j>0) && (arr[j-1] > temp)){
			arr[j] = arr[j-1];
			j--;
		}
		arr[j] = temp;
	}
	return arr;
}

归并排序

时间复杂度始终是始终都是O(n log n），但需要额外的内存空间。

//归并排序，firefox使用归并排序作为Array.prototype.sort的实现;
function mergeSort(arr){
	var len = arr.length;
	if(len <= 1){
		return arr;
	}
	var half = Math.floor(len/2);
	var arrLeft = arr.slice(0,half);
	var arrRight = arr.slice(half);
	res = merge(mergeSort(arrLeft),mergeSort(arrRight));
	return res;
}

function merge(arrLeft,arrRight){
	var res = [],
		iL = 0,
		iR = 0;
	while((iL<arrLeft.length) && (iR<arrRight.length)){ 
		if(arrLeft[iL] < arrRight[iR]){
			res.push(arrLeft[iL]);
			iL++;
		}else{
			res.push(arrRight[iR]);
			iR++;
		}
	}
	while(iL<arrLeft.length){
		res.push(arrLeft[iL]);
		iL++;
	}
	while(iR<arrRight.length){
		res.push(arrRight[iR]);
		iR++;
	}
	return res;
}

快速排序

//快速排序，每轮以序列起始值key为参考值，将序列分为左右两边，左边都比key小，右边都比key大，然后递归进行排序
//chrome的Array.prototype.sort采用快速排序实现
function quickSort(arr){
	function sort(start,end){
		if(start >= end ) return; 
		var key = arr[start];
		var i = start+1;
		var j = end;
		while(true){
			while(arr[i] <=key){
				i++;
				if(i>=end)break;
			}
			while(arr[j] >= key){
				j--;
				if(j<=start)break;
			}
			if(i<j){
				var temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}else{
				break;
			}
		}
		if(j > start){
			var t = arr[start];
			arr[start] = arr[j];
			arr[j] = t;
			sort(start,j-1);
			sort(j+1,end);
		}
	}
	sort(0,arr.length-1);
	return arr;
}

1. 100个数中选出前10个，选快排
2. 100万个数中选前10个，选堆排