c拓展阅读桶排序
本帖最后由 houqing1999 于 2023-6-24 20:43 编辑能否解释一下此处结构体的作用，以及两个函数的作用，代码具体是怎么实现的，里面for循环的作用
#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 = array;
}
newArray = item;
return newArray;
}
void bucket_sort(int array[], int length)
{
int min = array;
int max = array;
int i, j, k, cap, size;
struct Bucket* bucket = NULL;
struct Bucket b;
for (i = 1; i < length; i++)
{
if (array > max)
{
max = array;
}
if (array < min)
{
min = array;
}
}
cap = max - min + 1;
bucket = (struct Bucket*)malloc(sizeof(struct Bucket) * cap);
for (i = 0; i < cap; i++)
{
bucket = *(struct Bucket*)malloc(sizeof(struct Bucket));
}
for (i = 0; i < length; i++)
{
b = bucket - min];
if (b.count < 0)
{
b.count = 0;
}
bucket - min].data = add_item(b.data, b.count++, array);
bucket - min].count = b.count;
}
for (i = 0, k = 0; i < cap; i++)
{
size = bucket.count;
if (size > 0)
{
for (j = 0; j < size; j++)
{
array = bucket.data;
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);
bucket_sort(array, length);
printf("排序后的结果是：");
for (i = 0; i < length; i++)
{
printf("%d ", array);
}
putchar('\n');
return 0;
} 本帖最后由 isdkz 于 2023-6-24 19:09 编辑
首先，我们来看一下这个代码中使用的一些主要元素：
1. 结构体Bucket ：这个结构体由两个字段组成，一个是int* data ，这是一个指向整数的指针，用于存储指向桶中的元素的指针，另一个是int count ，这是一个整数，用于记录桶中的元素数量。
2.add_item函数：此函数接受一个整数数组、数组的长度和一个整数，然后返回一个新的数组，新的数组包含原数组中的所有元素，再加上新添加的元素。这个函数通过使用malloc函数动态分配一个新的内存空间，并使用循环将原数组的元素复制到新数组中，然后在新数组的末尾添加新元素。
3.bucket_sort函数：此函数实现了桶排序算法。它首先找出待排序数组中的最小和最大元素，然后创建一个桶数组，每个桶是一个Bucket结构体。桶的数量等于最大元素和最小元素的差加一，这样可以确保每个可能的元素值都有一个对应的桶。然后，该函数将每个元素放入对应的桶中。最后，它将所有非空桶中的元素复制回原数组，从而实现排序。
代码的具体实现过程：
1.bucket_sort函数开始时，首先找出数组中的最大值和最小值。
2. 根据最大值和最小值的差值计算出需要的桶的数量（ cap ），并为桶分配内存空间。
3. 通过遍历数组，将每个元素放入对应的桶中。对于每个元素，先找到其对应的桶（ bucketi] - min] ），然后调用add_item函数将元素添加到桶的数据中。
4. 当所有的元素都放入桶中后，遍历每个桶，将桶中的元素复制回原数组。
至于for循环的作用，主要有以下几点：
· 在add_item函数中， for循环用于复制原数组的所有元素到新数组中。
· 在bucket_sort函数中，第一个for循环用于找出数组中的最大值和最小值。第二个for循环用于初始化桶数组。第三个for循环用于遍历原数组，将每个元素添加到对应的桶中。最后一个for循环用于遍历桶数组，将桶中的元素复制回原数组。
以上就是这个代码的整体实现和各个元素的作用。 本帖最后由 houqing1999 于 2023-6-24 20:33 编辑
isdkz 发表于 2023-6-24 19:07
首先，我们来看一下这个代码中使用的一些主要元素：
1. 结构体Bucket ：这个结构体由两个字段组成，一 ...
还有几个点，1为什么add_item 要最后新添加一个元素newArray = item;
2第二个函数里找最大值最小值的for循环初始为啥i=1，这样少比较一个元素吧，
3void bucket_sort(int array[], int length)里面的for (i = 0; i < length; i++)
{
b = bucket - min];
if (b.count < 0)
{
b.count = 0;
}
bucket - min].data = add_item(b.data, b.count++, array);
bucket - min].count = b.count;
}为啥里面的if语句条件是b.count<0，还是没懂。
同样的for (i = 0, k = 0; i < cap; i++)
{
size = bucket.count;
if (size > 0)
{
for (j = 0; j < size; j++)
{
array = bucket.data;
k++;
}
}
这个里面的if语句条件为啥是size>0, 本帖最后由 houqing1999 于 2023-6-27 22:08 编辑
houqing1999 发表于 2023-6-24 20:31
还有几个点，1为什么add_item 要最后新添加一个元素newArray = item;
2第二个函数里找最大值最 ...
问题的解决请见这个，给新鱼油索引一下https://fishc.com.cn/thread-230064-1-1.html
但感觉问题还是没有解释清楚，所以暂时还没有最佳答案 币哦
页:
[1]