在输出中显示错误值的基数排序

Question

我正在学习dsa，我尝试在c中实现基排序。我使用这个课程教程。实现了它，但是它们使用的数字数组得到了正确的排序，但是当我使用不同的数组时，它显示了一些垃圾值。

当我插入这个

int array[] = {121,432,564，23，1，45,788}；

输出为"1 23 45 121 432 564 788“输出

但当我插入这个

int array[] = {3,4,1,5,2}；

输出为"1 2 3 4 2 496“输出

我实现了本教程中的代码。有人能指出这个问题吗？

#include <stdio.h>

void radix_sort(int array[], int size);
void counting_sort(int array[], int size, int place);

int main(void)
{
    int array[] = {3,4,1,5,2};
    int size = sizeof(array) / sizeof(int);

    radix_sort(array, size);

    for (int i = 0; i < size; i++)
        printf("%i ", array[i]);
    printf("\n");
}

void radix_sort(int array[], int size)
{
     int max = array[0];
     for (int i = 1; i < size; i++)
     {
         if (array[i] > max)
         max = array[i];
     }

for (int place = 1; max / place > 0; place *= 10)
    counting_sort(array, size, place);
}

void counting_sort(int array[], int size, int place)
{
    int output[size + 1];
    int max = (array[0] / place) % 10;

    for (int i = 1; i < size; i++)
    {
         if (((array[i] / place) % 10) > max)
             max = array[i];
    }
    int count[max+1];

    for (int i = 0; i < max; ++i)
        count[i] = 0;

    for (int i = 0; i < size; i++)
        count[(array[i] / place) % 10]++;

    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    for (int i = size-1; i >= 0; i--)
    {   
       output[count[(array[i] / place) % 10] - 1] = array[i];
       count[(array[i] / place) % 10]--;
    }

    for (int i = 0; i < size; i++)
       array[i] = output[i];
 }

Answer 1

for (int i = 1; i < 10; i++) {将访问自count[max+1] => count[5+1]以来超出界限的数组，因此您的程序具有未定义的行为。它可能会崩溃、输出垃圾或做任何事情。

您应该在该循环中使用i <= max：

for (int i = 1; i <= max; i++)  // use `i <= max` here
    count[i] += count[i - 1];

您还需要将可变长度数组count的内存调零，因为它在创建后将包含不确定值。您试着用for (int i = 0; i < max; ++i) count[i] = 0;来完成这个操作，但是这忽略了数组中的最后一个元素。您还需要i <= max：

int count[max + 1];
for (int i = 0; i <= max; ++i) count[i] = 0;