常用排序算法的js实现（冒泡、选择、插入、归并、希尔、快排）

//冒泡排序
function sort(arr){
	for (var i=0; i<arr.length; i++){
		for(var j=0; j<arr.length-1-i; j++){
			if(arr[j]>arr[j+1]){
				var k = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = k;
			}
		}
	}
	return arr;
}
console.log(sort([1,4,2,6,3,7]));


//选择排序
function sort(arr){
	for(var i=0; i<arr.length-1; i++){
		var k = i;
		for(var j=i+1; j<arr.length; j++){
			if(arr[j]<arr[k])
				k = j;
		}
		if(k!=i){
			var t = arr[k];
			arr[k] = arr[i];
			arr[i] = t;
		}
	}
	return arr;
}
console.log(sort([1,4,2,6,3,7]));


//插入排序
function sort(arr){
	for(var i=1; i<arr.length; i++){
		for(var j=0; j<i; j++){
			if(arr[j]>arr[i]){
				var k = arr[i];
				arr.splice(i,1);
				arr.splice(j,0,k);
				break;
			}
		}
	}
	return arr;
}
console.log(sort([1,4,2,6,3,7]));


//归并排序
function guibing(arr1,arr2){
	var i=j=0;
	var arr = [];
	while(i<arr1.length && j<arr2.length){
		if(arr1[i]<=arr2[j]){
			arr.push(arr1[i++]);
		}else{
			arr.push(arr2[j++]);
		}
	}
	while(i<arr1.length){
		arr.push(arr1[i++]);
	}
	while(j<arr2.length){
		arr.push(arr2[j++]);
	}
	return arr;
}
function sort(arr){
	if(arr.length == 1)
		return arr;
	var mid = Math.floor(arr.length/2);
	var left = arr.slice(0,mid);
	var right = arr.slice(mid);
	return guibing(sort(left),sort(right));
}
console.log(sort([1,4,2,6,3,7,5,12,8,2,4]));


//快速排序
function sort(arr,l,r){
	if(l<r){
		var key = arr[l];
		var i=l,j=r;
		while(i<j){
			while(i<j && arr[j]>=key)
				j--;
			if(i<j)
				arr[i++]=arr[j];
			while(i<j && arr[i]<=key)
				i++;
			if(i<j)   
				arr[j--] = arr[i]
		}
		arr[i] = key;
		sort(arr,l,i-1);
		sort(arr,i+1,r);
	}
}
var arr = [1,4,2,6,3,7,5,12,8,2,4];
sort(arr,0,arr.length-1);
console.log(arr);


//希尔排序
function sort(arr){
	var i,j,gap;
	for (gap = parseInt(arr.length/2); gap > 0; gap = parseInt(gap / 2)){
		for (i = gap; i < arr.length; i++){
			for (j = i - gap; j > 0 && arr[j] > arr[j + gap]; j-=gap){
				var t = arr[j];
				arr[j] = arr[j + gap];
				arr[j + gap] = t;
			}
		}
	}
}
var arr = [1,4,2,6,3,7,5,12,8,2,4];
sort(arr);
console.log(arr);