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

题目描述：给定一个包含负数和小数的浮点数数组，设计一个排序算法将其按升序排列。要求算法的时间复杂度为O(n)，但可以使用额外空间。

解题过程：

1. 问题分析

• 标准计数排序通常用于非负整数
• 现在需要处理包含负数和小数的浮点数
• 关键挑战：如何将浮点数映射到计数数组的索引

2. 核心思路

• 将浮点数转换为可计数的整数
• 通过缩放和偏移解决负数和小数问题
• 使用桶的思想进行分组计数

3. 具体步骤

步骤1：确定数值范围

def find_range(arr):
    min_val = min(arr)
    max_val = max(arr)
    return min_val, max_val

步骤2：设计映射函数

def float_to_index(value, min_val, scaling_factor):
    # 将浮点数映射到整数索引
    # scaling_factor 决定精度，如1000表示保留3位小数
    return int((value - min_val) * scaling_factor)

步骤3：实现排序算法

def counting_sort_float(arr, decimal_places=3):
    if not arr:
        return []
    
    min_val, max_val = find_range(arr)
    scaling_factor = 10 ** decimal_places  # 精度控制
    
    # 计算范围大小
    range_size = int((max_val - min_val) * scaling_factor) + 1
    
    # 创建计数数组
    count = [0] * range_size
    
    # 统计每个值出现的次数
    for num in arr:
        index = float_to_index(num, min_val, scaling_factor)
        count[index] += 1
    
    # 计算前缀和（累积分布）
    for i in range(1, range_size):
        count[i] += count[i-1]
    
    # 构建结果数组
    result = [0] * len(arr)
    for num in reversed(arr):  # 反向遍历保证稳定性
        index = float_to_index(num, min_val, scaling_factor)
        result[count[index] - 1] = num
        count[index] -= 1
    
    return result

4. 处理负数的优化方案

def counting_sort_float_negative(arr, decimal_places=3):
    min_val, max_val = find_range(arr)
    scaling_factor = 10 ** decimal_places
    
    # 使用偏移量处理负数
    offset = -min_val if min_val < 0 else 0
    range_size = int((max_val + offset - min_val) * scaling_factor) + 1
    
    count = [0] * range_size
    
    # 统计频率（考虑偏移）
    for num in arr:
        adjusted_num = num + offset
        index = int(adjusted_num * scaling_factor)
        count[index] += 1
    
    # 累积分布
    for i in range(1, range_size):
        count[i] += count[i-1]
    
    # 输出结果（去除偏移）
    result = [0] * len(arr)
    for num in reversed(arr):
        adjusted_num = num + offset
        index = int(adjusted_num * scaling_factor)
        result[count[index] - 1] = num
        count[index] -= 1
    
    return result

5. 算法分析

• 时间复杂度：O(n + k)，其中k是值域范围
• 空间复杂度：O(n + k)
• 稳定性：是稳定排序
• 适用场景：数值范围不大且精度要求确定的浮点数排序

6. 实际应用示例

# 测试包含负数和小数的数组
test_arr = [3.14, -2.5, 1.0, 0.0, -1.2, 3.14, 2.7]
sorted_arr = counting_sort_float_negative(test_arr, 2)
print(sorted_arr)  # 输出：[-2.5, -1.2, 0.0, 1.0, 2.7, 3.14, 3.14]

这个算法通过巧妙的映射机制，将计数排序的应用范围扩展到了包含负数和小数的浮点数排序，在特定场景下能提供线性的时间复杂度。