Appearance
简介
排序数组
选择排序
在第
时间复杂度:
cpp
for (int i = 1; i <= n; i ++) {
int tmp = i; // tmp: 第 i 小的数
for (int j = i + 1; j <= n; j ++)
if (a[j] < a[tmp]) tmp = j;
swap(a[i], a[tmp]);
}
冒泡排序
重复扫描数组
时间复杂度:
cpp
while (true) {
bool swapped = false;
for (int i = 1; i <= n; i ++) {
if (a[i] > a[i + 1]) {
swap(a[i], a[i + 1]);
swapped = true;
}
}
if (!swapped)
break;
}
插入排序
将数组
时间复杂度:
cpp
for (int i = 2; i <= n; i ++) {
int tmp = a[i], j = i - 1;
while (j >= 1 && a[j] > tmp)
a[j + 1] = a[j --];
a[j + 1] = tmp;
}
计数排序
记录每个元素出现的次数,然后依次输出。
时间复杂度:
cpp
int maxn = - 1e9;
for (int i = 1; i <= n; i ++) {
f[a[i]] ++;
maxn = max(maxn, a[i]);
}
int p = 0;
for (int i = 1; i <= maxn; i ++)
for (int i = 1; i <= f[i]; i ++)
a[++ p] = i;
快速排序
对
- 设定基准数为
; - 扫描该区间,将所有比基准数小的元素移至其左,大于基准数的元素移至其右;
- 递归地对基准数的左侧子区间和右侧子区间进行排序。
初始调用时,传入
平均时间复杂度:
最坏时间复杂度:
cpp
int partition(int low, int high) {
int pivot = a[low];
while (low < high) {
while (low < high && pivot <= a[high])
-- high;
a[low] = a[high];
while (low < high && pivot >= a[low])
++ low;
a[high] = a[low];
}
a[low] = pivot;
return low;
}
// 对 a[low] ... a[high] 排序
void qsort(int low, int high) {
if (low < high) {
int pivot = Partition(A, low, high);
qsort(A, low, pivot - 1);
qsort(A, pivot + 1, high);
}
}
归并排序
对
- 将数组分为
和 两个子数组; - 递归排序两个子数组;
- 合并两个已排序的子数组。
- 设定变量
和 ,分别等于两个子数组的起始下标; - 比较
和 ,选择更小的,加入数组 的末尾,并自增 (或 ); - 重复上一步直到某指针超出数组末尾;
- 将子数组剩下的所有元素加入数组
的末尾,再将数组 拷贝到数组 。
- 设定变量
时间复杂度:
cpp
// 对 a[l] ... a[r] 排序
void msort(int l, int r) {
if (l == r) return;
int m = (l + r) / 2;
msort(l, m);
msort(m + 1, r);
int i = l, j = m + 1, k = l;
while (i <= m && j <= r) {
if (a[i] <= a[j])
b[k ++] = a[i ++];
else
b[k ++] = a[j ++];
}
while (i <= m) b[k ++] = a[i ++];
while (j <= n) b[k ++] = a[j ++];
for (i = l; i <= r; i ++)
a[i] = b[i];
}
猴子排序
随机交换两个元素,直到排完序。
平均时间复杂度:
最好时间复杂度:
最坏时间复杂度:
cpp
srand(unsigned(time(0)));
while (true) {
swap(a[rand() % n + 1], a[rand() % n + 1]);
bool solve = true;
for (int i = 2; i <= n; i ++)
if (a[i] < a[i - 1])
solve = false;
if (solve) break;
}
逆序对数
若
在 归并排序 的第 3 步:合并两个有序数组时,若出现
逆序对的数量可能会超过 int
的范围,需要开 long long
。
cpp
void msort(int l,int r){
if(l == r) return;
int m = (l + r) / 2;
msort(l, m);
msort(m + 1, r);
int i = l, j = m + 1, k = l;
while (i <= m && j <= r) {
if(a[i] <= a[j])
b[k ++] = a[i ++];
else {
b[k ++] = a[j ++];
ans += m - i + 1; // 统计逆序对
}
}
while (i <= m) b[k ++] = a[i ++];
while (j <= r) b[k ++] = a[j ++];
for (i = l; i <= r; i ++)
a[i] = b[i];
}
稳定性
稳定排序不会破坏键值相同元素的原顺序。
例如,对于结构体 Student
:
cpp
struct Student {
int score;
int id;
}
给定一个 Student
数组,先以 id
为键值进行排序,再以 score
为键值进行排序。稳定排序能保证所有 score
相同的 Student
仍按照 id
升序。
算法 | 是否稳定 | 算法 | 是否稳定 |
---|---|---|---|
选择排序 | 快速排序 | ||
冒泡排序 | 归并排序 | ||
插入排序 | 猴子排序 | ||
记数排序 |