算法：鸽巢排序（桶排序）

鸽巢排序，名字很生动形象，其实就是把待排序的数组中相同的元素扔到同一个鸽巢。

例题

洛谷1177 排序

题目描述
将读入的 N 个数从小到大排序后输出。

输入格式
第 1 行为一个正整数 N。
第 2 行包含 N 个空格隔开的正整数 a[i]，为你需要进行排序的数，数据保证了a[i]不超过10^9。
​
输出格式
将给定的 N个数从小到大输出，数之间用空格隔开。

输入输出样例
输入

5
4 2 4 5 1

输出

1 2 4 4 5

说明提示
对于20% 的数据，有 N <= 10^3。
对于100% 的数据，有 N <=10^5 。

备注
本来洛谷1177是需要用快速排序来求解的，但实在找不到用鸽巢排序就能过的裸题，因此只好以这道题为例子了。这道题用鸽巢排序实际上只能拿60分，因为鸽巢排序对空间的需求量较大。

鸽巢排序（桶排序）

鸽巢排序，顾名思义就是把每一个数当做一个鸽巢，而一个鸽巢记录的就是a数组中每个数出现的次数，这里就用nest来记录了，nest[i]表示i这个数在a数组中出现的次数，而根据a数组计算得出这个nest数组是极为简单的。但考虑到负数情况，我们选择对数组进行平移，这里我们取a数组的最小值对应到0，既nest[i]表示(i + a_min)这个数在a数组中出现的次数。

最后再从a_min到a_max遍历一遍，如果nest[i - a_min]大于0，就让数组a中从（当前有序数列的末位 + 1）到（当前有序数列的末位 + nest[i - a_min] + 1）的所有值等于i就好了，这样就顺利地将数组a排好序了。

最后，算一下时间复杂度：这里我们设m为最大值与最小值之差，那么时间复杂度就是O(n + m)。这种排序算法适合应用在n特别大，但m较小的情况。如果m太大，空间、时间都得炸。例如此题的前两个测试点，就因为m太大，所以就RE了。

代码

# include <cstdio>
# include <cmath>
# include <cstring>
# include <algorithm>
# include <climits>

using namespace std;

const int N_MAX = 100000, M_MAX = 100000000;

int n;
int a[N_MAX + 10];
int nest[M_MAX + 10];

void pigeonSort()
{
	int a_max = INT_MIN, a_min = INT_MAX;
	for (int i = 1; i <= n; i++) {
		a_max = max(a[i], a_max);
		a_min = min(a[i], a_min);
	}
	for (int i = 1; i <= n; i++)
		nest[a[i] - a_min]++;
	int now = 0;
	for (int i = a_min; i <= a_max; i++)
		while (nest[i - a_min]--) a[++now] = i;
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	pigeonSort();
	for (int i = 1; i <= n; i++)
		printf("%d ", a[i]);
	printf("
");
	return 0;
}