引入

在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。(Cf. Leetcode,2020)。

有一种做法是这样的:

1
2
3
4
5
6
7
8
int* Count = new int[n]();
for (int i = 0; i < n; i++) {
Count[nums[i]]++;
}
for (int i = -; i < n; i++) {
if (Count[i] >= 2)
return i;
}

这样的做法,我们同样可以用在排序中。对于上下界确定的欲排序数组,我们建立一个计数数组,遍历整个数组,进行计数,就可以直接输出对应的有序数组。我们称这种排序方法为鸽巢排序。这种排序方法在特殊的情况下可以实现时间复杂度 $O(n)$ 。

有些时候计数数组显得过于庞大,而且,例如对于一个双精度数组,就无法建立这样的对应数组。这个时候我们设立一系列“容量”相等的集合,将数组进行有序分割,再对被分割的子数组实施排序。这样的集合称为,这样的排序方法称为桶排序

桶排序继承了鸽巢排序的优点,但是鸽巢排序占用空间大的问题仍然解决得不好。而且桶排序仍然有先决条件,可以说是一种特殊情况下的排序。

桶排序是一种分配排序。分配排序不需要进行关键码的比较,但需要知道待排序列的一些具体情况。(Cf.Jin-nuo,2016)