冒泡排序vs归并排序vs选择排序vs插入排序

发表于 | 分类于 |

今天写了几个小排序，记录下来，都是比较简单的。

归并排序

归并排序的思想是分治，我们先来看下分治的思想。

分治：分而治之。就是把一个复杂的问题分成两个或者更多的相同的货相似的子问题，再把子问题分成更小的子问题。一直到最后子问题可以简单的直接求解。原问题的解即为子问题的合并。

比如快速排序，归并排序，傅里叶变换都是利用的分而治之的思想。

分治的策略是：
对于一个规模为n的问题，若该问题可以容易的解决，则直接解决。
若不能直接解决，将其分解为K个规模比较小的子问题。

这些子问题互相独立与原问题形式相同，递归的解这些子问题，然后将各子问题的解合并得到原问题的解。

归并排序：
将待排序元素分成大小大致相同的2个子集合(递归直到最小的排序单元），分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。

归并排序算法的时间复杂度是O（nlogn）,对于冒泡排序的O(n*n),效率还有有比较好的提高。js代码如下：

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
function merge(left,right){
	var resultArr = [];
	while(left.length>0 && right.length>0){
		if(left[0]<right[0]){
			resultArr.push(left.shift());
		}else{
			resultArr.push(right.shift());
		}
	}
	return resultArr.concat(left).concat(right);
}

function mergeSort(arr){
	if(arr.length<=1){
		return arr;
	}
	var mid = parseInt(arr.length/2);

	var left = arr.slice(0,mid);
	var right = arr.slice(mid);

	return merge(mergeSort(left),mergeSort(right));
}

var arr = [2,4,1,7,8,4];
console.log(mergeSort(arr));

插入排序

将数据分为两部分，有序部分与无序部分，一开始有序部分包含第1个元素，依次将无序的元素插入到有序部分，直到所有元素有序。插入排序又分为直接插入排序、二分插入排序、链表插入等，这里只讨论直接插入排序。它是稳定的排序算法，时间复杂度为O(n^2)。

注意与选择排序的区别，插入排序是把后面的每一个数插入到前面已经排好序的队列中。而选择排序是每次在后面选择最小的或者最大的，插入到已经有序的队列后面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function insertSort(arr){
	for(var i=1;i<arr.length;i++){
		var j=i-1;
		var value = arr[i];
		while(j>-1 && value<arr[j]){
			arr[j+1] = arr[j]; 
			j--;
		}
		arr[j+1] = value;
	}
	return arr;
}
var arr = [2,4,1,7,8,4];
console.log(insertSort(arr));

前面已经排好序了，要把后面最小的数插入到前面，所以是要从j=i-1开始找。然后如果该数一直比前面的有序的小，就把比他大的数往后移动，最后找到该点后，再把元素插入到该地方。

冒泡排序

冒泡排序可谓是最经典的,最简单的排序算法了，它是基于比较的排序算法，时间复杂度为O(n^2)，其优点是实现简单，n较小时性能较好。

相邻的数据进行两两比较，小数放在前面，大数放在后面，这样一趟下来，最小的数就被排在了第一位，第二趟也是如此，如此类推，直到所有的数据排序完成。下面是js完成冒泡排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function bubbleSort(arr){
	var len = arr.length;
	for(var i=0;i<len;i++){
		for(var j=len-1;j>i;j--){
			if(arr[j]<arr[j-1]){
				var temp = arr[j];
				arr[j] = arr[j-1];
				arr[j-1] = temp;
			}
		}
	}
	return arr;
}

var arr = [2,4,1,7,8,4];
console.log(bubbleSort(arr));

选择排序

有两个序列，一个是已经排序的序列，一个是暂未排序的序列。每次都从后面选出一个最大的或者最小的插入到前面已经排序好的末尾。依次类推，知道所有的元素排列完毕。

先把第一个定位基准，往后面未排序的找到最小的并且记录下index。如果index是不等于原来的i，说明这一趟已经找到了比他小的数，就可以讲这两个数交换了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function selectSort (arr){
	var len = arr.length;
	for(var i=0;i<len;i++){
		var index = i;
		for(var j=i+1;j<len;j++){
			if(arr[index]>arr[j]){
				index = j;
			}
		}
		if(index!=i){
			var temp = arr[index];
			arr[index] = arr[i];
			arr[i] = temp;
		}
	}
	return arr;
}
var arr = [2,4,1,7,8,4];
console.log(selectSort(arr));

事件复杂度

排序