使用Count Sort在C语言中打印排序数组时代码出错求助

你的代码核心问题出在计数数组的初始化循环条件上：

// Initialize the count array elements to zero
for(i=0; i < size+1; i++){
    count[i] = 0;
}

你用原数组的size+1作为循环终止条件，但计数数组的实际长度是max+1（由malloc((max+1)*sizeof(int))分配）。原数组size为6，而数组最大值是64，这意味着你只初始化了计数数组的前7个元素（索引0-6），剩下的索引7-64的元素都是未初始化的垃圾值。后续执行count[A[i]]++时，访问这些未初始化的内存会导致不可预测的行为，直接导致排序失效。

修复步骤 #

1. 修正计数数组初始化条件：将循环条件改为i <= max（或i < max+1），确保计数数组的所有元素都被初始化为0：

// Initialize the count array elements to zero
for(i=0; i <= max; i++){
    count[i] = 0;
}

2. 添加内存分配检查：使用malloc后最好检查是否分配成功，避免内存不足导致的崩溃：

int* count = (int*) malloc((max+1)*sizeof(int));
if(count == NULL){
    printf("内存分配失败\n");
    return;
}

3. 释放动态内存：排序完成后释放count数组，避免内存泄漏：

free(count);

修复后的完整代码 #

#include<stdio.h>
#include<limits.h>
#include<stdlib.h>

void displayArray(int *arr,int size){
    printf("[ ");
    for(int i=0; i<size; i++){
        printf("%d ",arr[i]);
    }
    printf("]\n");
}

int maximum(int A[], int size){
    int max = INT_MIN;
    for(int i=0; i<size; i++){
        if(max < A[i]){
            max = A[i];
        }
    }
    return max;
}

void countSort(int* A, int size){
    int i,j;

    // Find the maximum element in Array
    int max = maximum(A,size);

    // Create the count array
    int* count = (int*) malloc((max+1)*sizeof(int));
    if(count == NULL){
        printf("内存分配失败\n");
        return;
    }

    // Initialize the count array elements to zero
    for(i=0; i <= max; i++){
        count[i] = 0;
    }

    // Increment the corresponding index in the count array
    for(i=0; i<size; i++){
        count[A[i]] = count[A[i]] + 1;
    }

    i = 0;  // Counter for count array
    j = 0;  // Counter for given array

    while(i <= max){
        if(count[i] > 0){
            A[j] = i;
            count[i] = count[i] - 1;
            j++;
        }
        else{
            i++;
        }
    }
    free(count);
}

int main(){
    int A[] = {56,23,53,13,64,34};
    int n = 6;
    displayArray(A,n);
    countSort(A,n);
    displayArray(A,n);
    return 0;   
}

运行结果 #

修复后执行代码，会输出预期的排序结果：

[ 56 23 53 13 64 34 ]
[ 13 23 34 53 56 64 ]

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