拓展阅读，桶排序的疑问还

houqing1999

完整代码如下，想问一下
1为什么add_item 要最后新添加一个元素newArray[count] = item;
2第二个函数里找最大值最小值的for循环初始为啥i=1，这样少比较一个元素吧，
3void bucket_sort(int array[], int length)里面的61行为啥是if (b.count < 0)74行的条件判断为啥是size > 0

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>

int* add_item(int* array, int count, int item);
void bucket_sort(int array[], int length);

struct Bucket
{
    int* data;
    int count;
};

int* add_item(int* array, int count, int item)
{
    int* newArray = (int*)malloc(sizeof(int) * (count + 1));
    int i;

    for (i = 0; i < count; i++)
    {
        newArray[i] = array[i];
    }

    newArray[count] = item;

    return newArray;
}

void bucket_sort(int array[], int length)
{
    int min = array[0];
    int max = array[0];
    int i, j, k, cap, size;
    struct Bucket* bucket = NULL;
    struct Bucket b;

    for (i = 1; i < length; i++)
    {
        if (array[i] > max)
        {
            max = array[i];
        }

        if (array[i] < min)
        {
            min = array[i];
        }
    }

    cap = max - min + 1;
    bucket = (struct Bucket*)malloc(sizeof(struct Bucket) * cap);

    for (i = 0; i < cap; i++)
    {
        bucket[i] = *(struct Bucket*)malloc(sizeof(struct Bucket));
    }

    for (i = 0; i < length; i++)
    {
        b = bucket[array[i] - min];
        if (b.count < 0)
        {
            b.count = 0;
        }

        bucket[array[i] - min].data = add_item(b.data, b.count++, array[i]);
        bucket[array[i] - min].count = b.count;
    }

    for (i = 0, k = 0; i < cap; i++)
    {
        size = bucket[i].count;

        if (size > 0)
        {
            for (j = 0; j < size; j++)
            {
                array[k] = bucket[i].data[j];
                k++;
            }
        }
    }
}

int main(void)
{
    int array[] = { 73, 108, 111, 118, 101, 70, 105, 115, 104, 67, 46, 99, 111, 109 };
    int i, length;

    length = sizeof(array) / sizeof(array[0]);
    bucket_sort(array, length);

    printf("排序后的结果是：");
    for (i = 0; i < length; i++)
    {
        printf("%d ", array[i]);
    }
    putchar('\n');

    return 0;
}

代码详情索引https://fishc.com.cn/forum.php?m ... 040&pid=6266730

isdkz

1.  add_item  函数是一个动态数组的实现，当要向数组中添加元素时，由于静态数组长度不可变，因此需要动态分配新的内存空间以存放更多元素。 newArray[count] = item;  这行代码的作用是将新的元素添加到新的数组的末尾。

2. 在找最大值和最小值的循环中，循环索引  i  的初始值为  1  ，而不是  0 ，是因为在进入循环之前， min  和  max  已经被初始化为了  array[0] ，即第一个元素，所以从第二个元素开始比较即可，没有忽略任何元素。

3.  bucket_sort  函数中的判断条件  b.count < 0  和  size > 0  ：
   
   ·  b.count < 0  应该是一个编程错误，正常情况下，任何桶的元素个数不应该为负数。在这个代码中，这个判断可能没有起到预期的作用。通常，我们会初始化  count  为  0 ，不会让它小于  0 。

   ·  size > 0  是检查桶是否有元素。只有桶中有元素（即  size  大于  0 ）才需要对桶内的元素进行操作。如果  size  等于  0 ，即桶中没有元素，那么对桶的操作就没有意义。

sfqxx

占楼

sfqxx

1. 为什么add_item要在最后新添加一个元素newArray[count] = item;
   在add_item函数中，数组newArray是用来存储原数组array和新元素item的。首先，通过动态内存分配，将newArray的大小设置为count+1，确保能够容纳下原数组和新元素。然后，通过for循环将原数组中的元素复制到newArray中。最后，将新元素item放置到newArray的最后一位，完成对newArray的构建。这样做是为了实现向数组尾部添加新元素的功能。

2. 第二个函数里找最大值最小值的for循环初始为啥i=1，这样少比较一个元素吧？
   在bucket_sort函数中，循环变量i的初始值为1是因为在确定最大值和最小值时，将数组中的第一个元素array[0]作为初始的最大值和最小值。然后使用循环从第二个元素开始比较，以更新最大值和最小值。所以不会少比较一个元素。

3. void bucket_sort(int array[], int length)里面的61行为啥是if (b.count < 0)，74行的条件判断为啥是size > 0？
   在bucket_sort函数中，结构体Bucket的数据成员count表示每个桶中已存储的元素个数。第61行的判断条件if (b.count < 0)是在判断当前桶b中是否已存储过元素。若count<0，说明当前桶为空，需要将count置为0。
   第74行的条件判断if (size > 0)是判断当前桶中是否有数据需要进行排序。只有当桶中的元素个数大于0时，才会执行内部的循环，将桶中的元素按顺序存放到原数组array中。这样可以避免对空桶进行处理，提高排序效率。

求最佳答案

houqing1999

sfqxx 发表于 2023-6-25 21:07
1. 为什么add_item要在最后新添加一个元素newArray[count] = item;
   在add_item函数中，数组newArray ...

第一个问题那个新元素的作用是啥？

还有为什么
若count<0，说明当前桶为空？

houqing1999

isdkz 发表于 2023-6-25 20:37
1.  add_item  函数是一个动态数组的实现，当要向数组中添加元素时，由于静态数组长度不可变，因此需要动态 ...

可是b.count<0不报错是怎么回事，所以应该改成b.count=0?但是原代码里61行是这样

if (b.count < 0)
{
b.count = 0;
}

把if语句条件搞成b.count==0里面语句怎么改

isdkz

houqing1999 发表于 2023-6-25 21:31
可是b.count

[b]对于  b.count < 0  你的观察是对的，正常情况下，一个桶中元素的数量  b.count  应该是非负的，因此  b.count < 0  应该永远不会为真。因此，这个条件的存在可能是编程错误，或者可能是作者的原始意图被错误地转化为了代码。

至于你的问题，关于将  b.count < 0  更改为  b.count == 0 ，我认为这个更改是没有必要的。因为在执行  bucket[array[i] - min].data = add_item(b.data, b.count++, array[i]);  之前，我们需要保证  b.count  已经是  0 ，这在正常的情况下应该已经是满足的。

但如果你坚持要进行更改，那么应该如下：

        b = bucket[array[i] - min];
        if (b.count == 0)
        {
            bucket[array[i] - min].data = add_item(b.data, b.count, array[i]);
            bucket[array[i] - min].count = ++b.count;
        }

请注意，我将  b.count++  改为了  ++b.count 。因为我们现在是在  b.count == 0  的情况下添加元素，然后更新  count ，所以  ++b.count （先增加，后使用）与原来的  b.count++ （先使用，后增加）的效果是一样的。[/b]

houqing1999

isdkz 发表于 2023-6-25 21:35
对于  b.count < 0  你的观察是对的，正常情况下，一个桶中元素的数量  b.count  应该是非负的，因此   ...

不是我坚持要改，而是您说这个count<0的条件是错的那应该怎么改才对？

langyawang

这个是C++吗？

langyawang

还是C？

sfqxx

houqing1999 发表于 2023-6-25 21:28
第一个问题那个新元素的作用是啥？

还有为什么

1. 在函数`add_item`中，`newArray[count] = item;`的作用是将新元素`item`添加到数组`newArray`的最后一个位置(`count`索引处)。通过动态分配内存以增加数组大小，并将原始数据复制到新数组中，最后将新元素添加到末尾。

2. 在`bucket_sort`函数中，循环的初始值设为`i = 1`是因为在找最大值和最小值时，已经默认将第一个元素赋给了`min`和`max`，所以从第二个元素开始比较即可。这样做不会少比较一个元素。

3. 在`bucket_sort`函数中的61行，`b.count < 0`的判断条件是为了判断当前的桶是否为空。如果`b.count < 0`，表示当前桶还没有添加任何元素，需要对`count`进行初始化为0才能正确添加元素。

希望以上解答能够帮到你！

houqing1999

langyawang 发表于 2023-6-26 13:06
还是C？

是C