Skip to content

排序

2021-01-10

你听说过猴子排序吗?

简介

排序数组 a 中的元素 a[1],a[2],,a[n]本章只研究升序排序。

选择排序

在第 i 次遍历中,交换 a[i] 和第 i 小的数。

时间复杂度:O(n2)

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]);
}

冒泡排序

重复扫描数组 a,若 a[i]>a[i+1] 就交换它们。当没有可交换元素时结束排序。

时间复杂度:O(n2)

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;
}

插入排序

将数组 a 分为「已排序」和「未排序」区。每次将「未排序」区的一个元素插入「已排序区」的正确位置。

时间复杂度:O(n2)

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;
}

计数排序

记录每个元素出现的次数,然后依次输出。

f[x]:数字 x 出现了几次。

时间复杂度:O(n)不适用于大范围元素。

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;

快速排序

a[low]a[high] 区间进行排序:

  1. 设定基准数为 a[low]
  2. 扫描该区间,将所有比基准数小的元素移至其左,大于基准数的元素移至其右;
  3. 递归地对基准数的左侧子区间和右侧子区间进行排序。

初始调用时,传入 low=1,high=n

平均时间复杂度:O(nlogn)

最坏时间复杂度:O(n2)

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);
	}
}

归并排序

a[l]a[r] 区间进行排序:

  1. 将数组分为 a[lm]a[m+1r] 两个子数组;
  2. 递归排序两个子数组;
  3. 合并两个已排序的子数组。
    • 设定变量 ij,分别等于两个子数组的起始下标;
    • 比较 a[i]a[j],选择更小的,加入数组 b 的末尾,并自增 i(或 j);
    • 重复上一步直到某指针超出数组末尾;
    • 将子数组剩下的所有元素加入数组 b 的末尾,再将数组 b 拷贝到数组 a

时间复杂度:O(nlogn)

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];
}

猴子排序

随机交换两个元素,直到排完序。

平均时间复杂度:O(nn!)

最好时间复杂度:O(n)

最坏时间复杂度:O()

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;
}

逆序对数

i<ja[i]>a[j],则 (a[i],a[j]) 是一组逆序对。

归并排序 的第 3 步:合并两个有序数组时,若出现 a[i]>a[j] 的情况,由 i<j 可知 a[im]a[j] 构成了 mi+1 个逆序对,便可以统计到答案中。

WARNING

逆序对的数量可能会超过 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 升序。

算法是否稳定算法是否稳定
选择排序×快速排序×
冒泡排序归并排序
插入排序猴子排序×
记数排序