排序算法之：鸽巢排序（Pigeonhole Sort）

题目描述
给定一个包含 n 个元素的整数数组 nums，数组中的元素范围已知（例如，最小值 min 和最大值 max 确定）。要求使用 鸽巢排序 对数组进行升序排序，并分析其时间复杂度和适用场景。

解题过程

1. 理解鸽巢排序的核心思想
鸽巢排序是一种非比较型排序算法，适用于待排序元素的范围已知且范围不大的情况。其核心思想是：

• 假设待排序数组的值域为 [min, max]，则值域大小为 range = max - min + 1。
• 创建 range 个“鸽巢”（即桶），每个鸽巢对应值域中的一个可能值。
• 遍历数组，将每个元素放入对应值的鸽巢中（例如，元素 x 放入第 x - min 个鸽巢）。
• 最后按顺序遍历鸽巢，将非空鸽巢中的元素依次放回原数组，即完成排序。

2. 步骤详解
步骤 1：确定值域范围
遍历数组，找到最小值 min 和最大值 max：

min_val = min(nums)  
max_val = max(nums)  
range_size = max_val - min_val + 1  

步骤 2：创建鸽巢并分配元素

• 初始化 range_size 个空列表（鸽巢）：

  pigeonholes = [[] for _ in range(range_size)]  
  

• 遍历数组，将元素 x 放入索引为 x - min_val 的鸽巢中：

  for x in nums:  
      index = x - min_val  
      pigeonholes[index].append(x)  
  

步骤 3：合并鸽巢
按鸽巢顺序（从索引 0 到 range_size-1）遍历，将每个鸽巢中的元素依次放回原数组：

k = 0  
for i in range(range_size):  
    for x in pigeonholes[i]:  
        nums[k] = x  
        k += 1  

3. 示例演示
假设 nums = [4, 2, 4, 0, 2, 1]：

• min_val = 0, max_val = 4, range_size = 5。
• 创建鸽巢：

  索引 0（值 0）: [0]  
  索引 1（值 1）: [1]  
  索引 2（值 2）: [2, 2]  
  索引 3（值 3）: []  
  索引 4（值 4）: [4, 4]  
  

• 合并后得到排序结果：[0, 1, 2, 2, 4, 4]。

4. 复杂度分析

• 时间复杂度：
  • 遍历数组求 min/max：O(n)。
  • 分配元素到鸽巢：O(n)。
  • 合并鸽巢：O(n + range)（每个元素被访问一次）。
  • 总时间复杂度为 O(n + range)。
• 空间复杂度：需要 O(n + range) 的额外空间存储鸽巢和元素。

5. 适用场景与局限性

• 适用场景：元素范围（range）较小且已知，例如对年龄、分数等离散值排序。
• 局限性：若范围远大于元素数量（例如 range >> n），空间效率极低。

通过以上步骤，鸽巢排序以线性时间复杂度完成排序，但需注意其空间开销与值域范围紧密相关。