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

Question

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

当我插入这个
int array[] = {121, 432, 564, 23, 1, 45, 788};
输出为“1 23 45 121 432 564 788”output
但是当我插入这个
int array[] = {3,4,1,5,2};
输出为“1 2 3 4 2496” output

我实现了教程中的代码。谁能指出问题

#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;

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

Radix Sort showing wrong values in the output

c

sorting

radix-sort