桶排序的进阶应用：对包含负数的整数数组进行排序

题目描述：
给定一个包含负数、零、正数的整数数组，请使用桶排序（Bucket Sort）的思想将其升序排列。要求利用桶排序的分桶与收集过程，正确处理负数，并分析其时间复杂度和空间复杂度。

解题过程

桶排序的基本思想是将数据分到有限数量的桶里，每个桶再单独排序（通常使用其他排序算法或递归使用桶排序），最后按顺序将各个桶的元素合并。
传统桶排序假设输入数据均匀分布在某个范围（如 [0,1)），但本题中数据包含负数，因此需要调整分桶策略以兼容负数。

步骤 1：理解传统桶排序的局限性

传统的桶排序通常用于均匀分布在某个非负区间的数据（例如 [0, max]）。
如果直接用于负数，会出现两个问题：

1. 负数无法映射到正数索引的桶中。
2. 负数和正数混合时，简单的映射会破坏大小顺序。

步骤 2：设计兼容负数的分桶策略

我们可以将整个数据范围划分为若干连续的区间，每个区间对应一个桶。
关键点：

• 找出数组中的最小值 min_val 和最大值 max_val。
• 设定桶的个数 bucket_num（通常为数组长度或根据数据分布调整）。
• 每个桶负责的区间长度为：
  bucket_range = (max_val - min_val + 1) / bucket_num（向上取整，确保覆盖整个范围）。

映射公式：
对于任意元素 num，其对应的桶索引为：

bucket_index = floor((num - min_val) / bucket_range)

这样，负数也能被正确映射到从 0 开始的桶索引，且桶之间保持数值上的有序性。

步骤 3：算法步骤详解

假设数组为 arr，长度为 n。

1. 找出最值：
   遍历一次数组，得到 min_val 和 max_val。

2. 确定桶的数量和区间：
   设桶数量 bucket_num = n（最细粒度）。
   计算区间长度：
   bucket_range = (max_val - min_val) / bucket_num（浮点数除法）。
   注意：为了处理边界，实际计算索引时用：
   index = floor((num - min_val) / bucket_range)，
   但需防止 num == max_val 时索引超出范围，因此对最大值特殊处理，将其放入最后一个桶。

3. 创建空桶：
   用一个列表（或数组）的列表表示桶：buckets = [[] for _ in range(bucket_num)]。

4. 分配元素到桶中：
   遍历 arr 的每个元素 num：

   • 计算索引：

     idx = int((num - min_val) / bucket_range)
     

   • 如果 num == max_val，则将 idx 置为 bucket_num - 1（防止越界）。
   • 将 num 加入 buckets[idx]。

5. 对每个非空桶内部排序：
   可以选用任意排序算法，例如插入排序（因为每个桶内数据量较小，插入排序高效且稳定）。

6. 按顺序合并桶：
   从 buckets[0] 到 buckets[bucket_num-1]，依次将每个桶内已排序的元素放回原数组。

步骤 4：举例说明

数组：arr = [4, -3, 0, -1, 2, 5, -2, 3]

• n = 8，min_val = -3，max_val = 5
• 桶数量 bucket_num = 8
• 区间长度 bucket_range = (5 - (-3)) / 8 = 1.0

分配过程（idx = int((num - (-3)) / 1.0)）：

• num = 4 → idx = 7（注意：max_val=5 时才放最后一个桶，这里 4 不是最大值）
  更精确地计算：(4 - (-3)) / 1.0 = 7.0 → idx=7
• num = -3 → 0
• num = 0 → 3
• num = -1 → 2
• num = 2 → 5
• num = 5 → 最大值，直接放入最后一个桶 idx=7（但计算得 8，需限制为 7）
• num = -2 → 1
• num = 3 → 6

桶内容：

桶0: [-3]
桶1: [-2]
桶2: [-1]
桶3: [0]
桶4: []
桶5: [2]
桶6: [3]
桶7: [4, 5]

每个桶内已有序（这里恰好有序），合并后结果：
[-3, -2, -1, 0, 2, 3, 4, 5]

步骤 5：复杂度分析

• 时间复杂度：

  • 找最值：O(n)
  • 分桶：O(n)
  • 桶内排序：假设有 k 个桶，第 i 个桶有 n_i 个元素，用插入排序为 O(n_i²)，平均情况下数据分布均匀，n_i ≈ n/k，总时间 ≈ k * O((n/k)²) = O(n²/k)。
    当 k ≈ n 时，接近 O(n)。
    最坏情况（所有元素集中在一个桶）退化为 O(n²)，取决于内部排序算法。
  • 合并：O(n)
  • 平均复杂度：O(n + n²/k + k)。当 k ≈ n 时，接近 O(n)。

• 空间复杂度：

  • 桶的存储：O(n + k)，k 为桶数量。

步骤 6：边界条件与注意事项

1. 处理最大值：确保最大值被分配到最后一个桶，避免索引越界。
2. 空桶：合并时跳过空桶。
3. 桶数量选择：通常选 bucket_num = n，但若数据范围极大而 n 较小，可减少桶数以节省空间，但可能增加桶内排序时间。
4. 稳定性：若桶内排序使用稳定排序（如插入排序），则整体排序稳定。

步骤 7：代码框架（Python）

def bucket_sort_with_negative(arr):
    if not arr:
        return arr
    n = len(arr)
    min_val, max_val = min(arr), max(arr)
    
    bucket_num = n
    bucket_range = (max_val - min_val) / bucket_num
    
    buckets = [[] for _ in range(bucket_num)]
    
    for num in arr:
        if num == max_val:
            idx = bucket_num - 1
        else:
            idx = int((num - min_val) / bucket_range)
        buckets[idx].append(num)
    
    # 每个桶内排序（这里用内置的 Timsort，稳定且高效）
    for bucket in buckets:
        bucket.sort()
    
    # 合并
    k = 0
    for bucket in buckets:
        for num in bucket:
            arr[k] = num
            k += 1
    return arr

总结

这个题目展示了如何扩展桶排序以处理任意整数（包括负数），核心在于通过最小值偏移将整个数值范围平移到非负区间，再进行分桶。
该方法保持了桶排序平均情况线性时间复杂度的优点，同时通过简单的索引映射解决了负数问题。在实际应用中，桶排序适合数据分布均匀的场景，否则可能退化为平方复杂度。