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

我们先看题目描述：
给你一个包含负整数和小数的数组，请设计一个稳定的计数排序变体，使其能够正确排序这类数据，并证明其稳定性。

解题过程如下：

1. 理解核心挑战
   标准计数排序只能处理非负整数，因为依赖数组索引（索引从0开始）。要处理负数和小数有两个问题：

   • 负数不能直接作为索引
   • 小数无法直接映射到整数索引

2. 处理负数的策略
   步骤1：平移映射
   找到数组中的最小值min（可能是负数），在统计频次时，将每个元素值减去min，使得所有值变为非负：

   offset_value = value - min
   

   这样，值min映射到0，max映射到max-min。

   步骤2：统计频次
   创建计数数组count，大小为max-min+1，统计每个偏移后值的出现次数。

   步骤3：计算前缀和
   对count数组计算前缀和，此时count[i]表示小于等于i+min的元素个数（注意是原始值）。

   步骤4：逆向填充结果
   从原数组末尾开始向前遍历，根据当前值的偏移位置在count数组中找到其应放位置，然后count[offset]--。逆向遍历保证了稳定性。

3. 处理小数的扩展
   方法1：定点化转换（适用于已知精度的小数）

   • 确定小数位数d（如0.01则d=2）
   • 将所有数乘以10^d转为整数
   • 用上述处理负数的方法排序这些整数
   • 排序后再除以10^d恢复为小数

   方法2：桶排序结合（适用于范围广的小数）

   • 将小数范围划分为多个桶
   • 在每个桶内用比较排序（如插入排序）
   • 这实际是桶排序思想，严格说已不是纯计数排序

4. 稳定性证明
   证明的关键在于填充阶段的顺序：

   • 逆向遍历原数组时，对于相同值的元素，后面出现的会先被放置
   • 但由于count[offset]表示当前元素应放位置（从后往前计算），且每次放置后count[offset]--
   • 这样，对于值相同的两个元素，在原数组中靠后的会放在结果数组中更靠后的位置
   • 因此原数组中的相对顺序得以保持，排序是稳定的

5. 完整算法示例（处理负整数）
   输入：[-3, 2, 0, -1, 2, -3]

   1. min = -3, max = 2
   2. 计数数组大小：2-(-3)+1=6
   3. 偏移统计：[-3→0, 2→5, 0→3, -1→2, 2→5, -3→0]
   4. count = [2,0,1,1,0,2]  # 值(-3,-2,-1,0,1,2)的频次
   5. 前缀和：  [2,2,3,4,4,6]
   6. 逆向填充：
      最后元素-3: offset=0, count[0]=2 → 放位置1(2-1)，count[0]=1
      倒数第二2: offset=5, count[5]=6 → 放位置5(6-1)，count[5]=5
      ...继续直到第一个元素
   7. 结果：[-3,-3,-1,0,2,2]（稳定）
   

6. 复杂度分析

   • 时间复杂度：O(n + k)，其中k = max-min+1
   • 空间复杂度：O(n + k)（结果数组+计数数组）
   • 当k远小于n时效率很高，但当小数精度高时k可能很大

这个变体扩展了计数排序的适用范围，同时保持了稳定性和线性时间复杂度，是计数排序在实践中的重要优化方向。