c - 使用C实现基数排序

Question

我被以下问题困扰了几天。我用C实现基数排序，除了一行代码之外一切都很好。你能帮我解决这个问题吗？

我的问题出在 radix_sort 函数的第一行。当我使用int semi_sort[12]时，我可以正确运行程序。但是，我想使用传递给函数的大小变量，但是当我使用 int semi_sort[size] 而不是 int semi_sort[12] 时，我的程序会崩溃。谁能告诉我这是为什么吗？顺便说一下，我提到了this link ，在作者的代码中，他做了int semiSorted[size]。为什么这行代码这次能起作用？

提前谢谢您!!

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

#define bucket_size 10

int find_the_largest(int arr[],int size);
void display(int arr[],int size);
void radix_sort(int arr[],int size);

int main()
{
    printf("------------------------------------------------------\n");
    printf("        Hey! This is a radix sort algorithm!\n");
    printf("------------------------------------------------------\n\n");
    int array[] = {10, 2, 303, 4021, 293, 1, 0, 429, 480, 92, 2999, 14};
    int size = sizeof(array)/sizeof(int);
    int largest_num = find_the_largest(array,size);
    printf("The unsorted array:");
    display(array,size);
    printf("The radix sort algorithm:\n\n");
    radix_sort(array,size);
    display(array,size);
    return 0;
}

int find_the_largest(int arr[],int size){
    int i,max_num=0;
    for(i=0;i<size;i++){
        if(arr[i]>max_num)
            max_num = arr[i];
    }
    return max_num;
}

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

void radix_sort(int arr[],int size){

    int semi_sort[12];
    int max_num = find_the_largest(arr,size);
    int i,significant_num = 1;

    while(max_num/significant_num>0){
        int bucket[bucket_size] = {0};

        for(i=0;i<size;i++){
            bucket[(arr[i]/significant_num)%10]++;
        }

        for(i=1;i<size;i++){
            bucket[i] += bucket[i-1];
        }

        for(i=size-1;i>=0;i--){

            semi_sort[--bucket[(arr[i]/significant_num)%10]] = arr[i];
        }


        for(i=0;i<size;i++)
            arr[i] = semi_sort[i];

        significant_num *= 10;
    }
}

Answer 1

您的代码有问题:

for(i=1;i<size;i++){
    bucket[i] += bucket[i-1];
}

因为size可以大于bucket_size。

您可能遇到以下问题:

for(i=size-1;i>=0;i--){
    semi_sort[--bucket[(arr[i]/significant_num)%10]] = arr[i];
}

因为 --bucket[(arr[i]/significant_num)%10] 可以大于 11 或小于 0。

并且 find_the_largest 在负数上无法正常工作。

您可以为缓冲区动态分配内存，如下所示:

semi_sort = malloc(size * (sizeof *semi_sort));

并且不要忘记最后释放内存(free(semi_sort))。