计数排序（Counting Sort）处理含负数数组时触发段错误问题排查

问题描述 #

在对比排序算法运行速度的测试中，当输入数组包含负值时，计数排序函数触发段错误（segmentation fault），原问题代码如下：

void countSort(int arr[], int n)
{
    struct timeval ta, te;
    gettimeofday(&ta, NULL);
    int M = 0;
    for (int i = 0; i < n; i++)
        if (arr[i] > M)
            M = arr[i];
    int *countArray = (int *)calloc(M + 1, sizeof(int));
    for (int i = 0; i < n; i++)
        countArray[arr[i]]++;
    for (int i = 1; i <= M; i++)
        countArray[i] += countArray[i - 1];
    int *outputArray = (int *)malloc(n * sizeof(int));
    for (int i = n - 1; i >= 0; i--)
    {
        outputArray[countArray[arr[i]] - 1] = arr[i];   //segmentation fault
        countArray[arr[i]]--;
    }
    for (int i = 0; i < n; i++)
        arr[i] = outputArray[i];

    free(countArray);
    free(outputArray);
    gettimeofday(&te, NULL);
    printf("time: %lf sec\n", te.tv_sec - ta.tv_sec + (te.tv_usec - ta.tv_usec) / 1000000.0);
}

核心原因分析 #

原代码只计算了数组的最大值M，并创建了大小为M+1的计数数组，仅覆盖了0到M的非负区间。当数组中存在负值时，countArray[arr[i]]会尝试访问负下标，直接触发内存越界，导致段错误。

排查步骤 #

1. 定位越界场景：在段错误触发的代码行前添加打印语句，输出当前arr[i]的值，确认是否为负数——这是最快确认问题的方式。
2. 验证计数数组范围：检查计数数组的创建逻辑，确认其是否覆盖了数组中所有元素的取值区间（包括负值）。
3. 内存分配检查：添加calloc/malloc的返回值检查，避免空指针访问引发的额外错误。

修复方案 #

需要同时计算数组的最大值和最小值，通过偏移量将所有元素映射到非负区间，确保计数数组的下标合法：

修复后的代码 #

void countSort(int arr[], int n)
{
    struct timeval ta, te;
    gettimeofday(&ta, NULL);
    
    // 遍历数组，同时获取最大值和最小值
    int max_val = arr[0], min_val = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max_val) max_val = arr[i];
        if (arr[i] < min_val) min_val = arr[i];
    }
    
    // 计算计数数组的大小：覆盖从min_val到max_val的所有整数
    int count_size = max_val - min_val + 1;
    int *countArray = (int *)calloc(count_size, sizeof(int));
    if (!countArray) {
        perror("calloc failed");
        return;
    }
    
    // 统计元素出现次数，用arr[i]-min_val将负值映射为非负下标
    for (int i = 0; i < n; i++) {
        countArray[arr[i] - min_val]++;
    }
    
    // 累加计数，确定每个元素在输出数组中的位置
    for (int i = 1; i < count_size; i++) {
        countArray[i] += countArray[i - 1];
    }
    
    int *outputArray = (int *)malloc(n * sizeof(int));
    if (!outputArray) {
        perror("malloc failed");
        free(countArray);
        return;
    }
    
    // 从后向前填充输出数组，保证排序稳定性
    for (int i = n - 1; i >= 0; i--) {
        int idx = arr[i] - min_val;
        outputArray[countArray[idx] - 1] = arr[i];
        countArray[idx]--;
    }
    
    // 将排序结果复制回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = outputArray[i];
    }
    
    free(countArray);
    free(outputArray);
    
    gettimeofday(&te, NULL);
    printf("time: %lf sec\n", te.tv_sec - ta.tv_sec + (te.tv_usec - ta.tv_usec) / 1000000.0);
}

关键修复点 #

• 新增最小值计算，确保覆盖所有元素的取值范围
• 用arr[i] - min_val作为计数数组的下标，将负值映射为合法的非负索引
• 增加内存分配失败的检查逻辑，提升代码健壮性

内容的提问来源于stack exchange，提问作者Oltich