计数排序（Counting Sort）的进阶应用：处理负数和小数的优化与稳定性证明

题目描述：给定一个包含负数和/或小数的数组，如何使用计数排序对其进行排序？请详细讲解处理负数和小数的优化方法，并证明优化后算法仍然是稳定的排序算法。

解题过程循序渐进讲解：

第一步：回顾基础计数排序的限制

基础计数排序通常要求：

1. 输入元素是非负整数
2. 元素范围已知且范围不大（通常最大值与最小值的差值不宜过大）

其核心步骤：

1. 找出最大值max，创建长度为max+1的计数数组count，统计每个元素出现的次数
2. 对count数组求前缀和，得到每个元素排序后的最后一个位置
3. 从后往前遍历原数组，根据count数组确定元素位置，放入结果数组

为什么基础版本不能处理负数和小数？

• 负数会导致计数数组的索引为负（数组索引不能为负）
• 小数无法直接作为数组索引

第二步：处理负数的优化方案

目标：允许数组元素为任意整数（正、负、零）。

核心思想：将数值范围平移到非负区间。

具体步骤：

1. 遍历数组，同时找到min和max
2. 计算偏移量offset = -min（使最小值平移到0）
3. 创建计数数组count，长度为max - min + 1
4. 统计时，将元素num映射到索引num + offset
5. 排序时，从计数数组索引i映射回原始值i - offset

示例：数组[-3, 2, -1, 0, 2, -3]

• min = -3, max = 2, offset = 3
• 计数数组长度 = 2 - (-3) + 1 = 6
• -3映射到索引-3+3=0，2映射到2+3=5，以此类推
• 排序后反向映射即可

第三步：处理小数的优化方案

目标：允许数组元素为有限精度的浮点数。

核心思想：将小数转换为整数处理。

情况A：已知小数位数（如货币金额，固定2位小数）

• 将所有数乘以10^d（d为小数位数），转换为整数
• 用处理负数的方法排序这些整数
• 排序后再除以10^d还原为小数

示例：[3.14, 1.23, 5.67]，小数位数d=2

• 乘以100：[314, 123, 567]
• 排序整数：[123, 314, 567]
• 除以100：[1.23, 3.14, 5.67]

情况B：未知小数位数，但精度有限

• 确定最小精度（如0.001）
• 将所有数乘以1/精度，转换为整数
• 同上述步骤处理

第四步：同时处理负数和小数

结合第二、三步的思想：

1. 确定精度和范围：

   • 找到最小值min、最大值max
   • 确定精度p（如0.01、0.001等）

2. 转换为整数：

   • 计算缩放因子scale = 1/p
   • 对每个元素x，计算int_x = round((x - min) * scale)
   • 实际上更优做法：int_x = round(x * scale)，然后找整数的最小值

3. 优化公式：

   • 设scaled_min = round(min * scale), scaled_max = round(max * scale)
   • 偏移量offset = -scaled_min
   • 转换：index = round(x * scale) + offset
   • 这样保证所有index在[0, scaled_max - scaled_min]范围内

4. 计数排序：

   • 创建计数数组，长度为scaled_max - scaled_min + 1
   • 统计每个index出现次数
   • 求前缀和得到位置信息

5. 稳定性保持：

   • 从后往前遍历原数组
   • 对每个元素x，计算其index
   • 根据计数数组得到应放入结果数组的位置pos = count[index] - 1
   • 放入结果数组，同时count[index]--
   • 这一步保证了相同元素的相对顺序不变（稳定性）

6. 还原数据（如果需要）：

   • 如果原数据是小数，结果数组需要除以scale还原
   • 注意浮点数精度误差

第五步：稳定性证明

计数排序稳定性的关键在于从后往前遍历和前缀和表示最后一个位置。

稳定性定义：排序后，值相等的元素保持原来的相对顺序。

证明：

1. 计数数组经过前缀和后，count[k]表示值≤k的元素在排序后的最后一个位置（从1开始计数）
2. 从后往前遍历原数组时：
   • 当遇到元素a[i]，其值对应的索引为idx
   • 它在结果数组中的位置是count[idx] - 1（因为count[idx]是最后一个位置索引+1）
   • 放入后count[idx]--
3. 对于值相同的元素：
   • 它们对应的idx相同
   • 原数组中靠后的元素先被处理，放在count[idx]指示的位置
   • 然后count[idx]减小，原数组中靠前的元素放在更小的位置
   • 因此相同值的元素在结果数组中仍然是"后面的在后，前面的在前"
   • 即保持了原有的相对顺序

处理负数和小数后：

• 我们只是对元素做了线性变换：index = round(x * scale) + offset
• 这个变换是一一对应的，且保持大小关系：
  • 如果x1 < x2，则index1 < index2
  • 如果x1 = x2，则index1 = index2
• 因此对index排序等价于对原数排序
• 稳定性证明同上，因为算法操作完全相同

第六步：时间复杂度与空间复杂度分析

1. 时间复杂度：O(n + k)

   • n：数组长度
   • k：计数数组长度 = (scaled_max - scaled_min + 1)
   • 当k与n同一数量级时，为O(n)

2. 空间复杂度：O(n + k)

   • 结果数组：O(n)
   • 计数数组：O(k)

3. 适用场景：

   • 数据范围不大（k不太大）
   • 需要稳定排序
   • 元素可线性映射到整数

第七步：代码实现要点（伪代码）

function countingSortAdvanced(arr, precision=0.001):
    if arr为空: return arr
    
    # 1. 确定范围和缩放
    scale = 1 / precision
    scaled_arr = [round(x * scale) for x in arr]
    min_scaled = min(scaled_arr)
    max_scaled = max(scaled_arr)
    offset = -min_scaled
    k = max_scaled - min_scaled + 1
    
    # 2. 计数
    count = [0] * k
    for val in scaled_arr:
        index = val + offset
        count[index] += 1
    
    # 3. 前缀和
    for i in range(1, k):
        count[i] += count[i-1]
    
    # 4. 从后往前排序（保持稳定）
    n = len(arr)
    result = [0] * n
    for i in range(n-1, -1, -1):
        val = scaled_arr[i]
        index = val + offset
        pos = count[index] - 1
        result[pos] = arr[i]  # 存储原始值
        count[index] -= 1
    
    return result

第八步：注意事项

1. 精度问题：浮点数转换为整数时可能有舍入误差
2. 范围问题：如果max-min很大，计数数组会很大，内存消耗大
3. 负数偏移：偏移量计算要准确，确保所有索引非负
4. 稳定性验证：可通过测试用例验证相等元素的相对顺序

这个优化后的计数排序能够处理包含负数和有限精度小数的数组，同时保持了稳定排序的特性，适用于需要稳定排序且数据范围有限的场景。