计数排序（Counting Sort）的进阶应用：对包含负数和浮点数的数组进行排序

字数 2532 2025-12-05 19:51:26

计数排序（Counting Sort）的进阶应用：对包含负数和浮点数的数组进行排序

题目描述

给定一个包含任意实数的数组 arr（可能包含负数、浮点数），请设计一个基于计数排序（Counting Sort）思想的高效排序算法，将数组按非递减顺序排序。要求充分利用计数排序线性时间复杂度的特性，并合理处理负数和浮点数带来的额外挑战。

循序渐进解题过程

步骤1：回顾标准计数排序的限制

标准计数排序（Counting Sort）通常用于非负整数的排序，其基本步骤是：

找出数组中的最大值 max，创建一个长度为 max + 1 的计数数组 count。
遍历原数组，统计每个元素出现的次数，存入 count。
根据 count 数组，将元素按顺序放回原数组。

限制：

只能处理整数（索引必须是整数）。
不能直接处理负数（计数数组索引不能为负）。
不能直接处理浮点数（索引不能是小数）。
当数据范围（max - min）很大时，空间消耗可能过大。

步骤2：扩展思路——支持负数

要支持负数，核心思路是将数值映射到计数数组的合法索引（从0开始）。
做法：

遍历数组，找到最小值 min 和最大值 max。
创建计数数组 count，长度为 max - min + 1。
对于原数组中的每个元素 x，将其映射到索引 x - min（确保非负），然后进行计数。

例如：数组 [-3, 2, -1, 2]

min = -3, max = 2
计数数组长度 = 2 - (-3) + 1 = 6
元素 -3 映射到索引 -3 - (-3) = 0，2 映射到索引 2 - (-3) = 5。

映射公式：
index = x - min（结果一定是非负整数）

步骤3：扩展思路——支持浮点数

计数排序要求索引是整数，所以浮点数不能直接作为索引。
解决办法：将浮点数转换为整数，同时保持大小顺序不变。

常用技巧：

确定浮点数的最小值 min 和最大值 max。
设定一个缩放因子（scale factor），例如将浮点数乘以一个倍数（如 10^k，k 是小数位数），转换成整数，再进行计数排序。
排序后，再将整数转换回原始浮点数值。

注意：

缩放因子需要根据浮点数的精度需求选择，过大可能导致整数范围太大，浪费空间；过小可能丢失精度。
如果浮点数范围很大或精度要求高，计数排序可能不适用（空间爆炸），此时应考虑其他排序（如快速排序、归并排序）。

步骤4：设计通用排序流程

假设我们处理的是可能包含负数和浮点数的数组，并希望用计数排序思想实现。
步骤分解：

数据预处理：
- 遍历数组，找到最小值 min_val 和最大值 max_val。
- 确定精度：如果全是整数，缩放因子 scale = 1；如果有浮点数，根据题目要求或数据特征确定小数点后保留位数 d，取 scale = 10^d。
转换为整数数组：
- 创建临时数组 mapped，对于每个元素 x，计算：
  mapped_value = round((x - min_val) * scale)
  这样确保所有映射值都是非负整数，且范围是 [0, (max_val - min_val) * scale]。
计数排序：
- 创建计数数组 count，长度为 (max_val - min_val) * scale + 1。
- 遍历 mapped 数组，统计每个整数的出现次数。
- 对 count 数组求前缀和，得到每个整数在排序后数组中的最后一个位置索引。
- 从后往前遍历原数组（为了保持稳定性），根据 mapped 值找到在输出数组中的位置，放入对应元素。
转换回原值：
- 输出数组中存储的是映射后的整数值，需要还原为原始值：
  original_value = (mapped_value / scale) + min_val

步骤5：示例演示

假设数组：[-1.2, 3.5, -1.2, 0, 2.3]，我们保留1位小数（d=1, scale=10）。

找到 min_val = -1.2，max_val = 3.5。
映射计算：
- -1.2 → round((-1.2 - (-1.2)) * 10) = 0
- 3.5 → round((3.5 - (-1.2)) * 10) = 47
- 0 → round((0 - (-1.2)) * 10) = 12
- 2.3 → round((2.3 - (-1.2)) * 10) = 35
  得到映射数组：[0, 47, 0, 12, 35]。
计数排序这些整数（范围0~47），得到排序后的映射数组：[0, 0, 12, 35, 47]。
还原：
- 0 → 0/10 + (-1.2) = -1.2
- 12 → 12/10 + (-1.2) = 0
- 35 → 35/10 + (-1.2) = 2.3
- 47 → 47/10 + (-1.2) = 3.5
  最终排序结果：[-1.2, -1.2, 0, 2.3, 3.5]。

步骤6：时间与空间复杂度分析

时间复杂度：O(n + k)，其中 n 是数组长度，k 是映射后的整数范围 (max_val - min_val) * scale + 1。当 k 很大时，效率降低。
空间复杂度：O(n + k)，需要额外的计数数组和输出数组。

适用场景：

数组元素范围相对集中（k 不太大）。
对稳定性有要求（计数排序是稳定的）。
需要线性时间复杂度且数据分布均匀。

不适用场景：

数据范围极大（如浮点数精度高，scale 很大导致 k 巨大）。
此时应改用比较排序（如快速排序、归并排序）或基数排序。

总结

通过数值映射和缩放取整，计数排序可以扩展支持负数和浮点数排序。关键在于将原始值线性映射到非负整数索引，排序后再还原。虽然扩展了应用范围，但要注意空间开销和精度选择，避免因缩放导致范围过大而效率降低。

计数排序（Counting Sort）的进阶应用：对包含负数和浮点数的数组进行排序题目描述给定一个包含任意实数的数组 arr （可能包含负数、浮点数），请设计一个基于计数排序（Counting Sort）思想的高效排序算法，将数组按非递减顺序排序。要求充分利用计数排序线性时间复杂度的特性，并合理处理负数和浮点数带来的额外挑战。循序渐进解题过程步骤1：回顾标准计数排序的限制标准计数排序（Counting Sort）通常用于非负整数的排序，其基本步骤是：找出数组中的最大值 max ，创建一个长度为 max + 1 的计数数组 count 。遍历原数组，统计每个元素出现的次数，存入 count 。根据 count 数组，将元素按顺序放回原数组。限制：只能处理整数（索引必须是整数）。不能直接处理负数（计数数组索引不能为负）。不能直接处理浮点数（索引不能是小数）。当数据范围（ max - min ）很大时，空间消耗可能过大。步骤2：扩展思路——支持负数要支持负数，核心思路是将数值映射到计数数组的合法索引（从0开始）。做法：遍历数组，找到最小值 min 和最大值 max 。创建计数数组 count ，长度为 max - min + 1 。对于原数组中的每个元素 x ，将其映射到索引 x - min （确保非负），然后进行计数。例如：数组 [-3, 2, -1, 2] min = -3 , max = 2 计数数组长度 = 2 - (-3) + 1 = 6 元素 -3 映射到索引 -3 - (-3) = 0 ， 2 映射到索引 2 - (-3) = 5 。映射公式： index = x - min （结果一定是非负整数）步骤3：扩展思路——支持浮点数计数排序要求索引是整数，所以浮点数不能直接作为索引。解决办法：将浮点数转换为整数，同时保持大小顺序不变。常用技巧：确定浮点数的最小值 min 和最大值 max 。设定一个缩放因子（scale factor），例如将浮点数乘以一个倍数（如 10^k，k 是小数位数），转换成整数，再进行计数排序。排序后，再将整数转换回原始浮点数值。注意：缩放因子需要根据浮点数的精度需求选择，过大可能导致整数范围太大，浪费空间；过小可能丢失精度。如果浮点数范围很大或精度要求高，计数排序可能不适用（空间爆炸），此时应考虑其他排序（如快速排序、归并排序）。步骤4：设计通用排序流程假设我们处理的是可能包含负数和浮点数的数组，并希望用计数排序思想实现。步骤分解：数据预处理：遍历数组，找到最小值 min_val 和最大值 max_val 。确定精度：如果全是整数，缩放因子 scale = 1 ；如果有浮点数，根据题目要求或数据特征确定小数点后保留位数 d ，取 scale = 10^d 。转换为整数数组：创建临时数组 mapped ，对于每个元素 x ，计算： mapped_value = round((x - min_val) * scale) 这样确保所有映射值都是非负整数，且范围是 [0, (max_val - min_val) * scale] 。计数排序：创建计数数组 count ，长度为 (max_val - min_val) * scale + 1 。遍历 mapped 数组，统计每个整数的出现次数。对 count 数组求前缀和，得到每个整数在排序后数组中的最后一个位置索引。从后往前遍历原数组（为了保持稳定性），根据 mapped 值找到在输出数组中的位置，放入对应元素。转换回原值：输出数组中存储的是映射后的整数值，需要还原为原始值： original_value = (mapped_value / scale) + min_val 步骤5：示例演示假设数组： [-1.2, 3.5, -1.2, 0, 2.3] ，我们保留1位小数（ d=1, scale=10 ）。找到 min_val = -1.2 ， max_val = 3.5 。映射计算： -1.2 → round((-1.2 - (-1.2)) * 10) = 0 3.5 → round((3.5 - (-1.2)) * 10) = 47 0 → round((0 - (-1.2)) * 10) = 12 2.3 → round((2.3 - (-1.2)) * 10) = 35 得到映射数组： [0, 47, 0, 12, 35] 。计数排序这些整数（范围0~47），得到排序后的映射数组： [0, 0, 12, 35, 47] 。还原： 0 → 0/10 + (-1.2) = -1.2 12 → 12/10 + (-1.2) = 0 35 → 35/10 + (-1.2) = 2.3 47 → 47/10 + (-1.2) = 3.5 最终排序结果： [-1.2, -1.2, 0, 2.3, 3.5] 。步骤6：时间与空间复杂度分析时间复杂度：O(n + k)，其中 n 是数组长度，k 是映射后的整数范围 (max_val - min_val) * scale + 1 。当 k 很大时，效率降低。空间复杂度：O(n + k)，需要额外的计数数组和输出数组。适用场景：数组元素范围相对集中（k 不太大）。对稳定性有要求（计数排序是稳定的）。需要线性时间复杂度且数据分布均匀。不适用场景：数据范围极大（如浮点数精度高，scale 很大导致 k 巨大）。此时应改用比较排序（如快速排序、归并排序）或基数排序。总结通过数值映射和缩放取整，计数排序可以扩展支持负数和浮点数排序。关键在于将原始值线性映射到非负整数索引，排序后再还原。虽然扩展了应用范围，但要注意空间开销和精度选择，避免因缩放导致范围过大而效率降低。