计数排序（Counting Sort）的进阶应用：处理包含负数的整数数组

我将为您详细讲解如何扩展基础计数排序算法，使其能够处理包含负数的整数数组。

题目描述

标准的计数排序算法假设输入数组只包含非负整数。但在实际应用中，我们经常需要处理同时包含正数和负数的整数数组。本题目要求：

1. 设计一个能够处理包含负数整数数组的计数排序算法
2. 保持计数排序的线性时间复杂度特性
3. 确保排序的稳定性

解题过程

步骤1：理解标准计数排序的局限性

标准计数排序的工作流程：

1. 找出数组中的最大值
2. 创建计数数组，大小为最大值+1
3. 统计每个元素出现的次数
4. 根据计数数组重构排序后的数组

问题：当数组包含负数时，负数无法直接作为计数数组的索引。

步骤2：关键思路 - 数值偏移

为了处理负数，我们需要引入偏移量（offset）的概念：

• 找到数组中的最小值（可能是负数）
• 计算偏移量 = -min_value
• 将每个元素加上偏移量，使其变为非负数
• 进行标准计数排序
• 最后减去偏移量，恢复原始值

步骤3：详细算法步骤

步骤3.1：寻找最小值和最大值

def find_min_max(arr):
    min_val = arr[0]
    max_val = arr[0]
    for num in arr:
        if num < min_val:
            min_val = num
        if num > max_val:
            max_val = num
    return min_val, max_val

步骤3.2：计算偏移量和计数数组大小

min_val, max_val = find_min_max(arr)
offset = -min_val  # 将最小值映射到0
range_size = max_val - min_val + 1  # 计数数组的大小

步骤3.3：创建并填充计数数组

count = [0] * range_size

# 统计每个元素（考虑偏移）出现的次数
for num in arr:
    count[num + offset] += 1

步骤3.4：计算累积计数（保证稳定性）

# 计算累积计数，count[i]表示小于等于(i-offset)的元素个数
for i in range(1, len(count)):
    count[i] += count[i-1]

步骤3.5：构建排序结果（从后往前遍历保证稳定性）

result = [0] * len(arr)

# 从后往前遍历原数组，保证稳定性
for i in range(len(arr)-1, -1, -1):
    num = arr[i]
    # 计算在计数数组中的位置
    pos = num + offset
    # 计算在结果数组中的位置（需要减1，因为计数从1开始）
    result_index = count[pos] - 1
    result[result_index] = num
    count[pos] -= 1

步骤4：完整算法实现

def counting_sort_with_negatives(arr):
    if not arr:
        return arr
    
    # 步骤1：找到最小值和最大值
    min_val = min(arr)
    max_val = max(arr)
    
    # 步骤2：计算偏移量和范围
    offset = -min_val
    range_size = max_val - min_val + 1
    
    # 步骤3：创建并初始化计数数组
    count = [0] * range_size
    
    # 步骤4：统计每个元素出现的次数
    for num in arr:
        count[num + offset] += 1
    
    # 步骤5：计算累积计数
    for i in range(1, range_size):
        count[i] += count[i-1]
    
    # 步骤6：构建排序结果（保持稳定性）
    result = [0] * len(arr)
    for i in range(len(arr)-1, -1, -1):
        num = arr[i]
        pos = num + offset
        result_index = count[pos] - 1
        result[result_index] = num
        count[pos] -= 1
    
    return result

步骤5：示例演示

让我们通过一个具体例子来理解整个过程：

输入数组：[4, -2, 1, -5, 0, 3, -2, 4]

步骤5.1：找到极值

• 最小值：-5
• 最大值：4

步骤5.2：计算偏移量

• 偏移量 = -(-5) = 5
• 范围大小 = 4 - (-5) + 1 = 10

步骤5.3：统计频率
原始值：[-5, -2, 1, 0, 3, -2, 4]
偏移后：[0, 3, 6, 5, 8, 3, 9]
计数数组：[1, 0, 0, 2, 0, 1, 1, 0, 1, 1]

步骤5.4：累积计数
累积计数：[1, 1, 1, 3, 3, 4, 5, 5, 6, 7]

步骤5.5：构建结果
从后往前处理：

• 元素4 → 位置6 → result[6] = 4
• 元素-2 → 位置2 → result[2] = -2
• 元素3 → 位置5 → result[5] = 3
• 元素0 → 位置3 → result[3] = 0
• 元素1 → 位置4 → result[4] = 1
• 元素-5 → 位置0 → result[0] = -5
• 元素-2 → 位置1 → result[1] = -2
• 元素4 → 位置7 → result[7] = 4

最终结果：[-5, -2, -2, 0, 1, 3, 4, 4]

步骤6：复杂度分析

• 时间复杂度：O(n + k)，其中n是数组长度，k是数值范围(max-min+1)
• 空间复杂度：O(n + k)，用于计数数组和结果数组
• 稳定性：通过从后往前遍历原数组来保证

步骤7：适用场景和限制

适用场景：

• 整数排序
• 数值范围不大时（k ≈ O(n)）
• 需要稳定排序时

限制：

• 只适用于整数
• 当数值范围很大时(k >> n)，空间效率低
• 不适合浮点数（需要特殊处理）

这种扩展后的计数排序在保持线性时间复杂度的同时，成功解决了处理负数的问题，是基础计数排序的重要改进。