简介

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

选择排序

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

时间复杂度：$O(n^2)$。

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(n^2)$。

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(n^2)$。

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)$。不适用于大范围元素。

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[\mathrm{low}]$ 到 $a[\mathrm{high}]$ 区间进行排序：

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

初始调用时，传入 $\mathrm{low}=1,\mathrm{high}=n$。

平均时间复杂度：$O(n\log n)$。

最坏时间复杂度：$O(n^2)$。

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[l\cdots m]$ 和 $a[m+1\cdots r]$ 两个子数组；
2. 递归排序两个子数组；
3. 合并两个已排序的子数组。
   • 设定变量 $i$ 和 $j$，分别等于两个子数组的起始下标；
   • 比较 $a[i]$ 和 $a[j]$，选择更小的，加入数组 $b$ 的末尾，并自增 $i$（或 $j$）；
   • 重复上一步直到某指针超出数组末尾；
   • 将子数组剩下的所有元素加入数组 $b$ 的末尾，再将数组 $b$ 拷贝到数组 $a$。

时间复杂度：$O(n\log n)$。

// 对 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(n\cdot n!)$。

最好时间复杂度：$O(n)$。

最坏时间复杂度：$O(\mathrm{\infty })$。

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<j$ 且 $a[i]>a[j]$，则 $(a[i],a[j])$ 是一组逆序对。

在 归并排序 的第 3 步：合并两个有序数组时，若出现 $a[i]>a[j]$ 的情况，由 $i<j$ 可知 $a[i\cdots m]$ 和 $a[j]$ 构成了 $m-i+1$ 个逆序对，便可以统计到答案中。

WARNING

逆序对的数量可能会超过 int 的范围，需要开 long long。

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：

struct Student {
	int score;
	int id;
}

给定一个 Student 数组，先以 id 为键值进行排序，再以 score 为键值进行排序。稳定排序能保证所有 score 相同的 Student 仍按照 id 升序。

算法	是否稳定	算法	是否稳定
选择排序	$\times$	快速排序	$\times$
冒泡排序	$\sqrt{}$	归并排序	$\sqrt{}$
插入排序	$\sqrt{}$	猴子排序	$\times$
记数排序	$\sqrt{}$