如何实现bucket排序

Question

我是编程新手，需要在c中实现bucket排序。我的困惑是如何创建一个链表数组，以及如何根据值将值插入链表。我在网上找到的其他程序太复杂了。我无法理解它们。所以有人能帮我

Answer 1

首先创建一个链表，其中包含添加、删除、交换等所需的所有函数，然后将所有未排序的数据添加到其中，然后将列表传递给实际排序列表的函数。并使用swap等函数来交换对象（int、chars或字符串，无论您在排序什么）。

如果你是c的新手，这可能会有点令人困惑。但先开始，然后你可以粘贴一些代码供我们查看和帮助，但不要指望有人会给你完整的解决方案。

这也是bucket排序的一个很好的解释，这可能有助于您理解需要实现什么。

http://www.youtube.com/watch?annotation_id=annotation_508951&feature=iv&src_ vid＝Iiukrns0Gwk&v=ovAfqUafjAA

这可以帮助您理解链表在c中的实现http://spicemind.com/notes/c/c-linked-list-implementation/

=================================================

是的，你可以创建一个链表数组假设您实现了一个链表：

struct linkedlist
{
  //implementation of linked list.
};

然后在main中，您可以声明一个链表：

struct linkedlist mylist1;

并在main中创建一个链表数组：

struct linkedlist[10] mylist2;

要访问此链表数组的不同部分：mylist2[0].data=x//假设您在存储数据的链表中有一个名为data的int类型。依此类推

Answer 2

bucket排序最常见的变体对0到某个最大值M之间的n个数字输入的列表进行操作，并将值范围划分为n个bucket，每个bucket的大小为M/n。如果使用插入排序对每个bucket进行排序，则可以显示排序在预期的线性时间内运行（其中取所有可能输入的平均值）。然而，这种类型的性能会随着集群而降低；如果许多值出现在一起，它们将全部落入一个存储桶中，并且排序缓慢。

Bucket Sort 的说明视频