c - C中的数组桶排序

Question

我正在尝试从 txt 文件中读取数字列表，然后使用桶排序对它们进行排序。所以这是我的代码:

void bucketSort(int array[],int *n)
{
    int i, j;  
    int count[*n]; 
    for (i = 0; i < *n; i++)
        count[i] = 0;

    for (i = 0; i < *n; i++)
        (count[array[i]])++;

    for (i = 0, j = 0; i < *n; i++)  
        for(; count[i] > 0; (count[i])--)
            array[j++] = i; 
}   

int main(int brArg,char *arg[])
{

    FILE *ulaz;
    ulaz = fopen(arg[1], "r");

    int array[100];
    int i=0,j,k,n;


      while(fscanf(ulaz, "%d", &array[i])!=EOF)i++;

    fclose(ulaz);    
    n=i;
    for (j = 0; j<i; j++)
    {
        printf("Broj: %d\n", array[j]);
    }

    BucketSort(array,&n); 
    for (k = 0; k<i; k++)
        printf("%d \n", array[i]);   


    return 0;
}

代码没有错误，但是当我调用我的函数而不是排序数组时，我得到数组长度随机数(例如:2 3 5 4，排序后我得到 124520 124520 124520 124520 或其他一些随机数)因为我我是初学者，有人可以帮助我处理我的代码以及我做错了什么吗？ (抱歉英语不好)

Answer 1

正如 Cool Guy 正确指出的，您在内存访问方面存在问题，但最重要的是代码不会对任何内容进行排序。首先你应该阅读如何Bucket Sort确实有效。

一般来说:

• 您根据一些保证桶不会弄乱输入顺序的标准在桶中划分输入数据
• 使用其他排序方法或递归地使用桶排序对每个桶进行排序
• 拼接排序后的数据(这就是为什么第一点有不打乱输入顺序的限制)

这是您原始代码的示例，我尝试尽可能少地调整它，以便您更容易理解。此代码将预定义的输入数组按范围划分为 3 个桶:

• [-infinity][-1] -> 第一个桶
• [0;10] -> 第二个桶
• [11;infinity] -> 第三个桶

然后对每个桶执行快速排序并连接结果。我希望这有助于理解该算法的工作原理。

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

struct bucket 
{
    int count;
    int* values;
};

int compareIntegers(const void* first, const void* second)
{
    int a = *((int*)first), b =  *((int*)second);
    if (a == b)
    {
        return 0;
    }
    else if (a < b)
    {
        return -1;
    }
    else
    {
        return 1;
    }
}

void bucketSort(int array[],int n)
{
    struct bucket buckets[3];
    int i, j, k;
    for (i = 0; i < 3; i++)
    {
        buckets[i].count = 0;
        buckets[i].values = (int*)malloc(sizeof(int) * n);
    }
    // Divide the unsorted elements among 3 buckets
    // < 0    : first
    // 0 - 10 : second
    // > 10   : third
    for (i = 0; i < n; i++)
    {
        if (array[i] < 0)
        {
            buckets[0].values[buckets[0].count++] = array[i];
        }
        else if (array[i] > 10)
        {
            buckets[2].values[buckets[2].count++] = array[i];
        }
        else
        {
            buckets[1].values[buckets[1].count++] = array[i];
        }
    }
    for (k = 0, i = 0; i < 3; i++)
    {
        // Use Quicksort to sort each bucket individually
        qsort(buckets[i].values, buckets[i].count, sizeof(int), &compareIntegers);
        for (j = 0; j < buckets[i].count; j++)
        {
            array[k + j] = buckets[i].values[j];
        }
        k += buckets[i].count;
        free(buckets[i].values);
    }
}

int main(int brArg,char *arg[]) {

    int array[100] = { -5, -9, 1000, 1, -10, 0, 2, 3, 5, 4, 1234, 7 };
    int i = 12,j,k,n;

    n=i;
    for (j = 0; j<i; j++)
    {
        printf("Broj: %d\n", array[j]);
    }

    bucketSort(array, n); 
    for (k = 0; k<i; k++)
        printf("%d \n", array[k]);   


    return 0;
}