【排序算法(一)】各种排序算法的主要方式和复杂度分析

1，排序：按关键字有序的序列
2，稳定性：假设ki=kj(1<=i,j<=n,i≠j)，且在排序前ri领先于rj（即i 3，内排序：排序过程中，将待排的所有记录全部放在内存中。
性能指标：
①时间性能：关键字比较次数和记录移动次数（都尽可能少）
②辅助空间
③算法的复杂度：算法本身的复杂度（？）
4，外排序：由于记录的个数太多，不能同时放置在内存中，整个排序需要在内外存之间多次进行数据交换才能实现。
5，分类
从难易程度：冒泡排序，简单选择排序，直接插入排序比较简单，希尔排序，堆排序，归并排序，快速排序属于改进算法。
6，排序中常用到交换的操作，写代码时拎出来写。以下都是按照升序排列。

基本思想：
比较两两相邻的关键字，如果反序则交换，直到没有反序的记录为止。
代码示例：

void BubbleSort0(SqList *L) {
	int i,j;
	for(i=1;ilength;i++){
		for(j=i+1;jlength;j++){
			if(L->[i]>L->[j]){
				//交换值
				swap(L,i,j);
			}
		}
	}
}

正宗冒泡排序：

void BubbleSort(SqList *L) {
	int i,j;
	for(i=1;ilength;i++){
		for(j=L->length-1;j>i;j--){
			if(L->[j] > L->[j+1]){
				swap(L,j,j+1);
			}
		}
	}
}

复杂度：O(n^2)

通过n-i次比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录交换之。(通过记录下标避免了多次交换)
代码示例：

void SelectSort(){
	int i,j,min;
	for(i=0;ilength;i++){
		int min = i;
		for(j=i+1;jlength;j++){
			if(L->[min] > L->[j]){
				min = j;
			}
		}
		if(i != min){
			swap(L,i,min);
		}
		
	}
}

复杂度：O(n^2)

将一个记录插入到已经排好序的有序表中，从而得到一个有序的新增记录为1的有序表。
代码示例：

void InsertSort(SqList *L){
	int i,j;
	for(i=2;ilength;i++ ){
		if(L->[i][i-1]){
			L->[0] = L->[i];
			for(j=i-1;L->[j]>L->[0];j--){
				L->[j+1] = L->[j];
			}
			L->[j+1] = L->[0];
		}
	}
}

复杂度：O(n^2)

虽然复杂度一样，但是性能具体来说，直接插入>简单选择>冒泡