OI中的花样排序方法

OI中的花样排序方法

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

选择排序

时间复杂度:$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(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(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)$,其中$w$表示待排序数值的值域,稳定排序

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]; //按排名将原数组的书输出到另一个数组中存储
}
感谢支持,您的支持将是我原创的动力!