一. 冒泡排序

总体思想就是：

第一轮：数组里的第二项到最后一项，都和第一项进行比较，如果比第一项小，两者就交换；最后比较完，第一项就是最小的;
第二轮：数组里的第三项到最后一项，，都和第二项进行比较，如果比第一项小，两者就交换；最后比较完，第二项就是最小的;
以此类推……..

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Array.prototype.bubbleSort = function(){
	var length = this.length;
	for(var i=0;i<this.length;i++)
	{
		for(var j=i+1;j<this.length;j++)
		{
			if(this[j]<this[i])
			{
				var mid = this[i];
				this[i] = this[j];
				this[j] = mid;
			} 
		}
	}
	return this;
}

var arr = [1,5,3,7,9,4,23,100,79,0];
console.log(arr.bubbleSort());

二. 选择排序

和冒泡算法相比，它的好处是是不用每比较一次就换一次位置。比如在冒泡算法中，如果arr[3]<arr[0],这时候会换一次；但同时如果arr[5]比他俩都小，那还会再交换一次;这样下来每进行一次外部循环会进行很多步的交换操作。选择排序避免了这个问题,每一次外部的循环只需要交换一次。

选择排序

思想：每一次外部循环找出当前范围内最小值的index，然后进行交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Array.prototype.selectSort = function(){
	for(var i=0;i<this.length;i++){
		var index=i;

		for(var j=i+1;j<this.length;j++){
			if(this[j]<this[index])		//这儿必须是this[index]
			{
				index = j;
			}
		}

		var mid = this[index];
		this[index] = this[i];
		this[i] = mid;
	}

	return this;

}

var arr = [1,5,3,7,9,4,23,100,79,0];
console.log(arr.selectSort());

三. 插入排序

思想：只进行一次遍历；遍历到第i个元素的时候，确保这个元素之前的所有元素是排好序的；即对于第i个元素。在前i-1个元素中找好位置，然后插入到正确的位置。

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Array.prototype.insertionSort = function(){

	for(var i =1;i<this.length;i++){
		var temp = this[i];
		j = i;
		while(j>0&&temp<this[j-1]){		//  [3,5,2]
			//j是一直都在变的	比如[3,5,2]在i=2的时候
			//第一次进while j=2 2<5 所以第一次while运算完[3,5,5],j=1;
			//第二次进while的时候还是用2和3进行比较因为temp是不变的 运算完是[3,3,5]
			//跳出while循环以后，再把temp插入到j所标示出的位置
			this[j] = this[j-1];			//在this[j]>this[j-1]时跳出循环,这样就找到了arr[i]应该插入的位置
			j--;
		}
		this[j]=temp;

	}

	return this;
	
}

var arr = [5,1,23,3,7,9,4,100,79,0];
console.log(arr.insertionSort());

四. 归并排序(快速排序)

归并算法分两种，一种使用中间项的值来分割，一种使用中间项的index来分割；其实思路是一样的,都是使用递归;我比较喜欢第一种，思路简单,直接按大小分的组；

递归就是一个，从最初开始一直一直调用自己，但是一直没有运算；一直到分到不能再继续调用自己了，这时开始运算，并一步一步往回算；

  1. 使用中间项的值 :

找出中间项的值，把比他小的放到左边的数组里，比他大的放到右边的数组里，之后合并；然后对左边和右边的数组递归调用此方法；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Array.prototype.mergeSort = function(){
	
		if(this.length<=1){
			return this;
		}
		var midIndex = Math.floor(this.length/2);

		var left = [];
		var right = [];
		var mid = [];

		for(var i=0;i<this.length;i++){
			if(this[i]<this[midIndex]){
				left.push(this[i]);
			}else if(this[i]>this[midIndex]){
				right.push(this[i])
			}else if(this[i] == this[midIndex]){
				mid.push(this[i])
			}
		}

		return Array.prototype.mergeSort.call(left).concat(mid,Array.prototype.mergeSort.call(right))

}

var arr = [5,1,3,23,2];
console.log(arr.mergeSort());
  1. 使用中间项的index

思路如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
var mergeSortRec = function(array){
	var length = array.length;
	if(length == 1){
		return array;
	}

	var mid = Math.floor(length/2);
	var left = array.slice(0,mid);
	var right = array.slice(mid,length);

	var merge = function(left,right){		//把左右两项合并：规则左右两数组一项一项对比 晓得push进去
		var result = [];
		il = 0;
		ir = 0;

		while(il<left.length&&ir<right.length){
			if(left[il]<right[ir]){
				result.push(left[il++]);
			}else{
				result.push(right[ir++]);
			}
		}

		while(il<left.length){
			result.push(left[il++])
		}
		while(ir<left.length){
			result.push(right[ir++])
		}
		console.log(result);

		return result;
	}

	return merge(mergeSortRec(left),mergeSortRec(right));

}
console.log(mergeSortRec([2,5,1,8,3]));