C语言计数排序代码失效原因咨询及代码解析请求

你的代码存在的关键问题 #

这段代码离正确的计数排序还有不少偏差，核心问题如下：

• 未初始化内存：malloc 分配的 res 数组没有初始化，内存里是随机垃圾值，直接执行 res[s]++ 会导致计数完全错误。必须先把数组元素初始化为0。
• 返回值类型错误：函数声明返回 int*，但你写的是 return *res;，这返回的是数组第一个元素的值（int 类型），和返回值类型不匹配。就算改成返回 res，这也只是个计数数组，不是排序后的结果数组，调用方拿到也无法直接得到有序序列。
• 忽略 result_count 参数：这个参数是用来传递排序后结果数组的长度的，你的代码完全没用到它，调用方无法知道返回数组的有效长度。
• 硬编码数组长度：直接 malloc(100 * sizeof(int)) 假设所有元素都小于100，但实际场景中数组元素的范围可能更大，这种写法通用性极差，容易越界。

计数排序的核心逻辑与正确实现 #

计数排序是一种非比较型排序算法，专门针对整数数组（或可映射为整数的元素），核心是通过统计每个元素的出现次数，再根据计数生成有序数组。

正确实现步骤 #

1. 确定元素范围：遍历原数组，找到最大值和最小值，以此确定计数数组的长度（max - min + 1），避免硬编码。
2. 初始化计数数组：分配对应长度的内存，并将所有元素初始化为0。
3. 统计元素出现次数：遍历原数组，每个元素对应计数数组的位置为 元素值 - 最小值，该位置的计数加1。
4. 生成排序结果：遍历计数数组，根据每个位置的计数值，将对应元素（最小值 + 索引）重复对应次数放入结果数组，同时更新 result_count 为原数组的长度（因为排序不改变元素数量）。
5. 返回结果数组：返回指向结果数组的指针。

正确代码示例 #

#include <stdlib.h>
#include <string.h>

int *countingSort(int arr_count, int *arr, int *result_count) {
    if (arr_count == 0) {
        *result_count = 0;
        return NULL;
    }

    // 找到数组的最大值和最小值
    int min = arr[0], max = arr[0];
    for (int i = 1; i < arr_count; i++) {
        if (arr[i] < min) min = arr[i];
        if (arr[i] > max) max = arr[i];
    }

    // 创建并初始化计数数组（calloc自动初始化为0）
    int count_len = max - min + 1;
    int *count = (int *)calloc(count_len, sizeof(int));
    if (count == NULL) {
        *result_count = 0;
        return NULL;
    }

    // 统计每个元素的出现次数
    for (int i = 0; i < arr_count; i++) {
        count[arr[i] - min]++;
    }

    // 生成排序后的结果数组
    *result_count = arr_count;
    int *res = (int *)malloc(arr_count * sizeof(int));
    if (res == NULL) {
        free(count);
        *result_count = 0;
        return NULL;
    }

    int idx = 0;
    for (int i = 0; i < count_len; i++) {
        while (count[i] > 0) {
            res[idx++] = min + i;
            count[i]--;
        }
    }

    free(count); // 释放计数数组的内存，避免泄漏
    return res;
}

代码说明 #

• 用 calloc 分配计数数组，自动初始化为0，省去手动初始化的步骤。
• 先判断数组为空的情况，避免空指针错误。
• 动态计算计数数组的长度，适配不同元素范围的输入。
• 生成结果数组后释放计数数组，避免内存泄漏。
• 正确更新 result_count 参数，让调用方知道返回数组的长度。

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