1. 概述
在本教程中，我们将学习 Pigeonhole Sort（鸽巢排序） 这种排序算法。它适用于特定场景下的排序任务，尤其在数据量与值域接近的情况下表现优异。
2. 什么是 Pigeonhole 排序？
Pigeonhole 排序适用于以下场景：
当数组中元素个数 n 与数组中可能取值的范围 N 接近时。
比如我们有一个数组：{3, 8, 2, 1, 9, 5, 7, 7, 8}，其中：
- 元素个数 n = 9
- 最小值为 1，最大值为 9，所以值域 N = 9
此时 n ≈ N，因此非常适合使用 Pigeonhole 排序。
✅ **时间复杂度为 O(n + N)**，在数据密集且值域有限时非常高效。
❌ 不适合用于值域极大或数据稀疏的场景，否则空间浪费严重。
3. 算法原理
Pigeonhole 排序分为三个步骤：
3.1. 确定值域范围
首先找出数组中最小值 min 和最大值 max，从而确定值域范围 N：
int min = arr[0];
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] < min) {
min = arr[i];
}
if (arr[i] > max) {
max = arr[i];
}
}
int N = max - min + 1;
3.2. 创建并填充“鸽巢”
创建一个大小为 N 的数组，每个元素是一个列表（vector），表示一个“鸽巢”。然后将原始数组中的元素按值插入到对应的鸽巢中：
List<Integer>[] pigeonholes = new ArrayList[N];
for (int i = 0; i < N; i++) {
pigeonholes[i] = new ArrayList<>();
}
for (int i = 0; i < arr.length; i++) {
pigeonholes[arr[i] - min].add(arr[i]);
}
⚠️ 每个鸽巢保存的是相同值的元素。
3.3. 将鸽巢内容写回原数组
最后，依次将鸽巢中的元素按顺序写回原数组即可完成排序：
int index = 0;
for (int i = 0; i < N; i++) {
for (int num : pigeonholes[i]) {
arr[index++] = num;
}
}
整个过程非常直观，而且没有比较操作，因此效率高。
4. 示例演示
我们以数组 {3, 8, 2, 1, 9, 5, 7, 7, 8} 为例说明整个流程：
第一步：计算 min, max, N
- min = 1
- max = 9
- N = 9
第二步：构建鸽巢并填充
每个鸽巢对应一个值，比如索引 0 对应值 1，索引 1 对应值 2，依此类推。
第三步：写回原数组
最终排序结果为：
{1, 2, 3, 5, 7, 7, 8, 8, 9}
✅ 排序完成，无需比较，效率很高。
5. 小结
Pigeonhole 排序是一种基于计数的非比较排序算法，适用于：
- 元素数量 n 与值域 N 接近的情况
- 数据密集，值域较小
⚠️ 踩坑提示：
- 如果值域远大于元素数量，会浪费大量空间
- 不适合处理负数，除非做偏移处理
- 不具备通用性，使用场景有限
✅ 优点：
- 时间复杂度低，O(n + N)
- 实现简单，逻辑清晰
📌 总结：Pigeonhole 排序虽然不是万能排序算法，但在某些特定场景下非常高效，是值得掌握的排序技巧之一。