算法阅读笔记--排序

发表于 | 分类于

选择排序

对一个序列A中的元素A[1]到A[n]，令i从1到n枚举，进行n趟操作，每趟从待排序部分[i,n]中选择最小的元素，令其与待排序部分的第一个元素A[i]进行交换，这样元素A[i]就会与当前有序区间[1,i-1]形成新的有序区间[1,i]。
总时间复杂度为O(n^2)。

1
2
3
4
5
6
7
8
9
10
11
12
13
void selectSort(){
	for(int i=1; i<=n; i++){
		int k=i;
		for(j=i; j<=n; j++){
			if(A[j]<A[k]){
				k = j;
			}
		}
		int temp = A[i];
		A[i] = A[k];
		A[k] = temp;
	}
}

插入排序

1
2
3
4
5
6
7
8
9
10
11
int A[maxn], n; //n为元素个数，数组下标为1到n
void insertSort(){
	for(int i=2; i<=n; i++){
		int temp = A[i], j=i;
		while(j>1 && temp<A[j-1]){
			A[j] = A[j-1];
			j--;
		}
		A[j] = temp;
	}
}