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

当您尝试写入不属于您的程序的内存位置时，您的代码表现出未定义的行为。

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

上述循环导致了问题。你说 i 是 4 这意味着 *n 也是 4 而 array 包含 2 3 5 4。在上面的代码中，count 是一个包含 *n 个元素的数组（在本例中为 4 个元素），数组的有效索引是 count[0]、count[1]、count[2] 和 count[3]。正在做

count[array[i]]

当 i 为零时可以，因为它与 count[2] 相同。当 i 为 1 时与 count[3] 相同。之后，当 i 为 4 和 5 时，count[4] 和 count[5] 是错误的，因为您试图写入无效的内存位置。

此外，您的代码没有对值进行排序。

Answer 2

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

总的来说：

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

这里是你的原始代码的例子，我试着尽可能少地调整它，这样你更容易理解。此代码将预定义的输入数组按范围划分为 3 个存储桶：

[-无穷大][-1] -> 第一个桶
[0;10] -> 第二个桶
[11;无限] -> 第三个桶

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

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

C中的数组桶排序

array bucket sort in C

c

arrays

sorting