C中的计数排序分段错误

Question

下面是我对计数排序的尝试。我已经用图表表达了我的逻辑，运行口头表达了它，并对我的代码进行了彻底的注释。但是，我的代码导致了分段错误。我知道分段错误表示对内存的非法访问，所以这一定意味着我的索引值之一正在尝试访问数组范围之外的索引。但是，我不明白为什么会这样。

幸运的是，我的调试器突出显示了下面这行，我在评论中也注意到了，这是发生分段错误的地方。尽管如此，我完全被难住了。如果您能帮助理解此分段错误的性质，我们将不胜感激。谢谢。

void sort(int values[], int n)
{

    //create array of finite size (65536)
    int countArray[INT_MAX];

    //create array to eventually store sorted values
    int sortedValues[n];

    //loop through unsorted values to increment countArray index for each occurrence
    for(int i = 0; i < n; i++) {
        countArray[ values[i] ] += 1;
    }


    //starting index for sortedValues[]
    int sortedIndex = 0;

    //loop until we've reached the end of sortedValues[]
    while(sortedIndex < n) {

        //loop through each index value of countArray
        //j represents the value
        for(int j = 0; j < INT_MAX; j++) {

            //how many times does the index of countArray occur in values[]?
            int c = countArray[j];

            //only add index j as a value to sortedValues[] if it appears in values[]
            while(c > 0) {

                //append j to sortedValues[]
                //--SEGMENTATION FAULT OCCURS ON THE LINE BELOW--
                sortedValues[sortedIndex] = j;

                //decrease the count of countArray[j] once value appended to sortedValues[]
                c -= 1;

                //move to next index of sortedValues[]
                sortedIndex += 1;
            }
        } 
    }
    return;
}

Answer 1

您需要将 countArray 个元素初始化为零以修复崩溃：

int countArray[INT_MAX] = {0};

但是，您的函数仍然无用，因为它将排序后的数字放入一个本地数组中，该数组永远不会脱离函数。为了解决这个问题，删除 sortedValues 数组，并使用原始的 values 数组代替输出：

values[sortedIndex] = j;

现在调用者将看到他传递给您的函数的数组返回排序。

注：外层循环while(sortedIndex < n)无害但无用，因为for循环保证sortedIndex正好是n.您应该从代码中删除 while 循环。

Answer 2

正如我之前评论过的，您不需要 sortedIndex.

的单独循环

正如@dasblinkenlight 所建议的，您不需要创建本地数组 sortedValue 来存储排序后的值，而是可以对数组 values 进行适当的排序。

此外，您需要用全零初始化 countArray 以避免索引垃圾值。

代码如下：

void sort(int values[], int n)
{
    //create array of finite size (65536)
    int countArray[INT_MAX] = {0};

    //loop through unsorted values to increment countArray index for each occurrence
    for(int i = 0; i < n; i++) {
        countArray[ values[i] ] += 1;
    }

    //starting index for sortedValues[]
    int sortedIndex = 0;

   //loop through each index value of countArray
   //j represents the value
   for(int j = 0; j < INT_MAX; j++) {

    //how many times does the index of countArray occur in values[]?
    int c = countArray[j];

    //only add index j as a value to sortedValues[] if it appears in values[]
    while(c > 0) {
     //append j to sortedValues[]
     values[sortedIndex] = j;

     //decrease the count of countArray[j] once value appended to sortedValues[]
     c -= 1;

     //move to next index of sortedValues[]
     sortedIndex += 1;
    }
   }
}

C中的计数排序分段错误

Counting sort segmentation fault in C

c

segmentation-fault

cs50

counting-sort