计数排序（Counting Sort）的进阶应用：处理负数和小数 题目描述 已知计数排序适用于非负整数排序，但如何扩展该算法，使其能够处理包含负整数的数组？进一步地，能否通过改进计数排序，使其支持浮点数排序？ 解题过程 1. 计数排序的核心思想回顾 计数排序是一种非比较排序算法，适用于整数范围已知且范围不大的情况。基本步骤： 统计频率 ：遍历数组，统计每个整数出现的次数。 计算前缀和 ：将频率数组转换为前缀和数组，确定每个元素在排序后的位置。 反向填充 ：从原数组末尾开始，根据前缀和数组将元素放入结果数组的对应位置，保证稳定性。 2. 扩展至包含负数的数组 问题 ：传统计数排序要求键值 k ≥ 0 ，因为数组索引不能为负。 解决方案 ：通过偏移量（Offset）将整个数值范围平移到非负区间。 步骤 ： 遍历数组，找到最小值 min 和最大值 max 。 创建计数数组 count ，长度为 max - min + 1 。 统计元素出现次数时，将元素 x 映射到索引 x - min （确保索引 ≥ 0）。 生成前缀和数组时，需注意索引偏移。 反向填充时，将计数数组的索引 i 转换回实际值 i + min 。 示例 ： 数组 [-2, 5, -3, 0, 2] min = -3 , max = 5 ，计数数组长度 5 - (-3) + 1 = 9 。 元素 -2 映射到索引 -2 - (-3) = 1 。 排序后数组为 [-3, -2, 0, 2, 5] 。 3. 扩展至浮点数排序 问题 ：浮点数范围连续且无限，无法直接使用整数索引。 解决方案 ：将浮点数转换为整数后再排序，需保证精度且不破坏稳定性。 步骤 （以保留小数点后两位的浮点数为例）： 将每个浮点数乘以 100 ，转换为整数（例如 3.14 → 314 ）。 找到整数范围的最小值 min 和最大值 max 。 使用扩展后的计数排序处理整数数组。 将排序后的整数除以 100 ，还原为浮点数。 注意事项 ： 若浮点数范围过大或精度要求高，计数数组可能超内存限制，此时需改用其他排序（如桶排序）。 若浮点数有正有负，需结合负数处理方法的偏移量技巧。 示例 ： 数组 [1.23, -0.45, 3.14, -0.45] 乘以 100 ： [123, -45, 314, -45] min = -45 , max = 314 ，计数数组长度 314 - (-45) + 1 = 360 。 排序后整数数组为 [-45, -45, 123, 314] 。 除以 100 还原： [-0.45, -0.45, 1.23, 3.14] 。 关键总结 负数处理 ：通过偏移量将数值范围平移至非负区间。 浮点数处理 ：缩放为整数后排序，再还原。需注意精度和范围限制。 适用场景 ：计数排序的扩展形式适用于数值范围可控的情况，若范围过大应选择桶排序或基数排序。