计数排序

非常简单就能实现的排序，其原理为开一个 $a[1\dots n]$ 的数组（$n$ 为数据最大值），读入数据 $i$ 就存到对应位置 $a[i]$（即 $a[i]$ 加 $1$），之后按顺序输出 $a[i]$ 个数字 $i$ 即完成排序。

代码实现及复杂度统计

int a[N] = {0}, n, m, tmp; // n 为数据最大值，m 为数据个数，tmp 用于临时存储数据
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		cin >> tmp;
		a[tmp]++; // 对应个数加一
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < a[i]; ++j) cout << i << ' '; // 输出对应个数的数字
	}
}

时间复杂度：读入 $O(m)$，输出 $O(m+n)$

空间复杂度：$O(n)$

拓展

桶排序

选择排序

从第一个元素开始，向后走寻找比它更小的值，然后将这个值与第一个元素交换，继续往下。重复此过程，即剩余数列的更小值与第二个元素交换，……这样就能得到排好序的数列。

代码实现及复杂度统计

for (int i = 0; i < n - 1; ++i) {
	for (int j = i + 1; j < n; ++j) {
		if (a[j] < a[i]) swap(a[j], a[i]);
	}
}

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

空间复杂度：$O(n)$