OI中的花样排序方法

排序算法多种多样 ，性质也大多不同。

选择排序

时间复杂度：O(n2)O(n^2) ，不稳定排序

1
2
3
4
5
6
7
8
9
10
11
12
13
void selectionSort(int* a,int n){  //选择排序
	for(int i = 1;i < n;i++){ //最后一位不用判断
		int ith = i; //ith记录当前位置后最小数的位置
		for(int j = i + 1;j <= n;j++){
			if(a[j] < a[ith])
			ith = j; //循环寻找当前位置后最小的数
		}
		int t = a[i];
		a[i] = a[ith];
		a[ith] = t;  //将第i个小的数与位置为i的数互换
	}

}

冒泡排序

时间复杂度：O(n2)O(n^2) ，稳定排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void bubbleSort(int* a,int n){ //冒泡排序
	bool flag = true;
	while(flag){
		flag = false;
		for(int i = 1;i < n;i++){
			if(a[i] > a[i + 1]){
				flag = true; //如果当前有一个是乱序的，则需要下次再从头检查
				int t = a[i];
				a[i] = a[i + 1];
				a[i + 1] = t;  //交换当前元素与下一个元素
			}
		}
	}
}

插入排序

时间复杂度：O(n2)O(n^2) ， 稳定排序

1
2
3
4
5
6
7
8
9
10
11
void insertionSort(int* a,int n){ //插入排序
	for(int i = 2;i <= n;i++){
		int key = a[i];  //记录当前位置数值，方便后续调换顺序
		int j = i - 1;   //从i - 1向前调换
		while(j > 0 && a[j] > key){ //将key从后往前调整到正确的位置
			a[j + 1] = a[j]; //将正确位置以后的数值逐一向前移动
			--j; //j向前移动
		}
		a[j + 1] = key; //在正确位置放入key
	}
}

计数排序

时间复杂度：O(n+w)O(n+w)，其中ww表示待排序数值的值域，稳定排序

1
2
3
4
5
6
7
8
9
10
11
const int MAXN = 10010; //需要排序的元素的总个数
const int MAXM = 10086; //需要排序的元素的数据范围

int n, w, a[MAXN], b[MAXN], cnt[MAXM]; //n为元素个数，w为元素最大值

void countingSort() {
	memset(cnt,0,sizeof(cnt));
	for(int i = 1;i <= n;i++) ++cnt[a[i]]; //统计每个元素出现的次数
	for(int i = 1;i <= w;i++) cnt[i] += cnt[i - 1]; //用前缀和计算排名
	for(int i = n;i >= 1;i--) b[cnt[a[i]]--] = a[i]; //按排名将原数组的书输出到另一个数组中存储
}