使用链接列表进行桶排序

Question

我试图在Java中实现桶排序，以便对整数数组进行排序。我正在尝试使用链接列表作为我的桶，但有一些困难，了解如何这样做。有人能提供一个实现吗？

我已经得到了这个算法，但这对我来说没有什么意义：

​

Answer 1

既然你没有代码要分析，我会给出一个书面的答案。创建一个Bucket类，它将包含两个数字(0-9、10-19等)之间的范围，一个insert方法(按顺序插入)，并包含一个空数组。然后创建如下桶的列表：

​

​

循环输入列表，并将每个数字插入到桶列表中的适当桶中。当您插入值时，它将为您排序。最后，获取所有Bucket的数组和块，然后为输出列表聚在一起。

下面是一个逐步脱离维基百科的过程

1. 设置一个初始空的“桶”数组。
2. 分散:遍历原始数组，将每个对象放入桶中。
3. 对每个非空桶进行排序。
4. 集合:按顺序访问桶，并将所有元素放回原始数组中。

这是提供给您的算法：

​

​

这个简单的翻译是：

1. A是必须排序的输入数组。
2. n是输入数组A的长度。
3. 必须将输入数组A的所有元素插入到桶B列表中。
4. 现在，在桶的列表B中订购每个桶。
5. 创建一个新的列表/数组返回，这将是所有排序桶的列表。

注意到：步骤4实际上可以按照您的实现来执行步骤3。

这个算法不会深入到你将要编码的复杂细节中。这只是一个简单的指南，以帮助你开始。

Answer 2

您可以开始分析以下内容：桶例

Answer 3

嗯，我不懂java，但我仍然可以给你算法。

最简单的方法是使桶以数组的形式出现，其中每个数组索引指向一个空的链接列表。

for each integer :  
   integer goes to bucket i  // bucket number depends on your implementation 
   pointer = bucket[i]   

   while pointer is not NULL  
      pointer = pointer->next  

   allocate new node
   pointer points to this node
   pointer.data = integer  
   pointer.next = NULL