计数排序（Counting Sort）的进阶应用：处理包含负数的整数数组 题目描述 给定一个包含负数和正数的整数数组，使用计数排序算法对数组进行升序排序。要求算法保持线性时间复杂度，且能正确处理负数。 解题过程 基础回顾 ： 标准计数排序适用于非负整数，通过统计每个元素的出现次数，然后按顺序重建数组。但若数组包含负数，直接应用会失败，因为负数无法作为数组索引。 关键思路 ： 将负数“平移”为非负数。通过找到数组中的最小值（设为 min ），将所有元素减去 min ，使得新数组的最小值为 0。排序后，再通过加回 min 还原原始值。 步骤详解 ： 步骤 1：确定范围 遍历数组，找到最小值 min 和最大值 max ，计算范围 range = max - min + 1 。 例如：数组 [-3, 2, 0, -1, 2] ， min = -3 ， max = 2 ， range = 2 - (-3) + 1 = 6 。 步骤 2：创建计数数组 初始化长度为 range 的计数数组 count ，所有元素设为 0。 步骤 3：统计频率 遍历原数组，对每个元素 x ，计算 index = x - min ，并增加 count[index] 。 示例： x = -3 → index = -3 - (-3) = 0 ， count[0] 加 1。 步骤 4：计算前缀和 对 count 数组计算前缀和，使 count[i] 表示小于等于 i + min 的元素个数。 例如： count = [1, 1, 1, 0, 2, 0] → 前缀和 [1, 2, 3, 3, 5, 5] 。 步骤 5：重建排序数组 从后向前遍历原数组（保证稳定性），对每个元素 x ： 计算 index = x - min 。 根据 count[index] 确定 x 在排序数组中的位置（位置为 count[index] - 1 ）。 将 x 放入结果数组，并减少 count[index] 。 最终得到排序后的数组，再统一加回 min （实际上已在索引转换中隐含还原）。 时间复杂度分析 ： 遍历数组求极值 O(n)，统计频率 O(n)，前缀和计算 O(range)，重建数组 O(n)。总复杂度 O(n + range)，当 range = O(n) 时，为线性排序。 边界处理 ： 若数组为空或范围极大（如 range >> n ），可结合桶排序优化。本方法适用于整数且范围可控的场景。