排序算法总结<一>

　　最近在准备各个实习面试，也是逐渐接触了各种面试和笔试题，多次碰到算法里的排序算法。各种算法以前也曾学习研究过，但是，总是在脑子里像浆糊般搅在一起，所以，决定写个笔记总结一下自己和各种资料里学习到的，以留后用。

平方阶排序

（1）冒泡排序
　　算法思想：每一趟排序都使得有序区多一个数据（气泡），所以n个数只需要（n-1）趟就可以使整个数据有序。具体的方法是，每次从一端开始，顺序向另一端两两比较，每次将大（小）的移动到后端，每完成一次，后端有序区就会多一个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
template <class T>
void BubbleSort(T *list, int n){
	T temp;
	for(int i = 1; i < n; i++){
		for(int j = 0; j < n-i; j++){
			if(list[j] > list[j+1]){
				temp = list[j];
				list[j] = list[j+1];
				list[j+1] = temp;
			}
		}
	}
}

　　上面的代码是模板函数，适用于各种定义了大于运算符的数据类型。并且，上述代码是每次将较大的数向后移动，也就是说，排完顺序后是从小到大的，需要从大到小的代码类似。
　　我们从上面的代码很快就可以看出，如果一开始传入的数据就是有序的，照理走完一边就可以发现了，但是它还是会循环完全过程，所以我们应该加入一个bool变量来优化该程序，在发现已经有序了就立即跳出程序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <class T>
void BubbleSort(T *list, int n){
	T temp;
	bool exchange;
	for(int i = 1; i < n; i++){
		exchange = 0;
		for(int j = 0; j < n-i; j++){
			if(list[j] > list[j+1]){
				temp = list[j];
				list[j] = list[j+1];
				list[j+1] = temp;
				exchange = 1
			}
		}
		if(!exchange) return;
	}
}

　　通过观察我们作出了优化的程序，我们可以轻松的发现，冒泡排序的最优复杂度就是O(n)，即一开始就是有序的；最坏的复杂度当然是与想要的顺序反序的输入，此时将完成所有的循环，复杂度为O(n^2)，而平均的复杂度也应该是O(n^2)。

（2）插入排序
　　算法思想：不断将后续的元素按照一定的大小顺序不断插入到前面有序的序列中。具体可将要插入数据取出，然后逐次向前不断与有序部分比较，如果要从小到大排列，那么只要被比较数较大，就后移一位，直到找到比插入数小的，将插入数插入到该位的后一位，继续该过程，直到所有的数都完成插入。因为第一个数已经有序，所以n个数也只需要（n-1）趟就可以使整个数据有序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <class T>
void InsertSort(T *list, int n){
	T current;
	for(int i = 1; i < n; i++){
		current = list[i];
		for(int j = i-1; j >=0; j--){
			if (list[j] > current){
				list[j+1] = list[j];
			}
			else{
				list[j+1] = current;
				break;
			}
		}
	}
}

　　我们从上面的代码就可以看到，如果传入序列已经排好序，那么内层循环就会直接退出，所以最优复杂度就是O(n)，最坏的复杂度也是与想要的顺序反序的输入，此时将完成所有的循环，复杂度为O(n^2)，而平均的复杂度也应该是O(n^2)。

（3）选择排序
　　算法思想：每次遍历无序区域，找出最大值或者最小值，然后，将其交换到有序区域的边缘，使其成为有序区的一部分。很显然，该算法针对n个数也只需要（n-1）趟就可以使整个数据成为有序的序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <class T>
void SelectSort(T *list, int n){
	T temp;
	int min;
	for(int i = 0; i < n; i++){
		min = i;
		for(int j = i+1; j < n; j++){
			if(list[j] < list[min]) min = j;
		}
		if(min ! = i){
			temp = list[i];
			list[i] = list[min];
			list[min] = temp;
		}
	}
}

　　通过上面的程序我们可以看到，选择排序每次都必须完成选择最小（最大）值，然后交换的过程，所以对于选择排序来说，它的最优复杂度和最差复杂度还有平均复杂度都为O(n^2)。