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

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

1. #define _CRT_SECURE_NO_WARNINGS 1
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. 
   
5. int* add_item(int* array, int count, int item);
   
6. void bucket_sort(int array[], int length);
   
7. 
   
8. struct Bucket
   
9. {
   
10.     int* data;
    
11.     int count;
    
12. };
    
13. 
    
14. int* add_item(int* array, int count, int item)
    
15. {
    
16.     int* newArray = (int*)malloc(sizeof(int) * (count + 1));
    
17.     int i;
    
18. 
    
19.     for (i = 0; i < count; i++)
    
20.     {
    
21.         newArray[i] = array[i];
    
22.     }
    
23. 
    
24.     newArray[count] = item;
    
25. 
    
26.     return newArray;
    
27. }
    
28. 
    
29. void bucket_sort(int array[], int length)
    
30. {
    
31.     int min = array[0];
    
32.     int max = array[0];
    
33.     int i, j, k, cap, size;
    
34.     struct Bucket* bucket = NULL;
    
35.     struct Bucket b;
    
36. 
    
37.     for (i = 1; i < length; i++)
    
38.     {
    
39.         if (array[i] > max)
    
40.         {
    
41.             max = array[i];
    
42.         }
    
43. 
    
44.         if (array[i] < min)
    
45.         {
    
46.             min = array[i];
    
47.         }
    
48.     }
    
49. 
    
50.     cap = max - min + 1;
    
51.     bucket = (struct Bucket*)malloc(sizeof(struct Bucket) * cap);
    
52. 
    
53.     for (i = 0; i < cap; i++)
    
54.     {
    
55.         bucket[i] = *(struct Bucket*)malloc(sizeof(struct Bucket));
    
56.     }
    
57. 
    
58.     for (i = 0; i < length; i++)
    
59.     {
    
60.         b = bucket[array[i] - min];
    
61.         if (b.count < 0)
    
62.         {
    
63.             b.count = 0;
    
64.         }
    
65. 
    
66.         bucket[array[i] - min].data = add_item(b.data, b.count++, array[i]);
    
67.         bucket[array[i] - min].count = b.count;
    
68.     }
    
69. 
    
70.     for (i = 0, k = 0; i < cap; i++)
    
71.     {
    
72.         size = bucket[i].count;
    
73. 
    
74.         if (size > 0)
    
75.         {
    
76.             for (j = 0; j < size; j++)
    
77.             {
    
78.                 array[k] = bucket[i].data[j];
    
79.                 k++;
    
80.             }
    
81.         }
    
82.     }
    
83. }
    
84. 
    
85. int main(void)
    
86. {
    
87.     int array[] = { 73, 108, 111, 118, 101, 70, 105, 115, 104, 67, 46, 99, 111, 109 };
    
88.     int i, length;
    
89. 
    
90.     length = sizeof(array) / sizeof(array[0]);
    
91.     bucket_sort(array, length);
    
92. 
    
93.     printf("排序后的结果是：");
    
94.     for (i = 0; i < length; i++)
    
95.     {
    
96.         printf("%d ", array[i]);
    
97.     }
    
98.     putchar('\n');
    
99. 
    
100.     return 0;
     
101. }

复制代码

代码详情索引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行是这样

1. if (b.count < 0)
   
2. {
   
3. b.count = 0;
   
4. }

复制代码

把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 ，这在正常的情况下应该已经是满足的。

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

1.         b = bucket[array[i] - min];
   
2.         if (b.count == 0)
   
3.         {
   
4.             bucket[array[i] - min].data = add_item(b.data, b.count, array[i]);
   
5.             bucket[array[i] - min].count = ++b.count;
   
6.         }
   

复制代码

请注意，我将  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