java - 使用链表进行桶排序

Question

我正在尝试在 Java 中实现桶排序，以便对整数数组进行排序。我正在尝试使用链接列表作为我的存储桶，但在理解如何执行此操作时遇到一些困难。有人能提供一个实现吗？

我已经获得了这个算法，但它对我来说没有多大意义:

Answer 1

由于您没有代码可供分析，我将给出书面答案。创建一个 Bucket 类，其中包含两个数字之间的范围(0-9、10-19 等)、一个插入方法(按顺序插入)，并包含一个空数组。然后创建一个存储桶列表，如下所示:

循环输入列表并将每个数字插入存储桶列表中相应的存储桶中。当您插入值时，它会为您排序。最后，获取 Bucket 的所有数组，然后汇总在一起作为输出列表。

这是 Wikipedia 的逐步过程。 :

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

这是为您提供的算法:

这个简单的转化为:

1. A 是您必须排序的输入数组
2. n 是输入数组A的长度
3. 您必须将输入数组 A 的所有元素插入存储桶列表 B
4. 现在对 Bucket 列表中的每个 Bucket B 进行排序。
5. 创建一个要返回的新列表/数组，它将是所有有序 Bucket 的列表。

注意:根据您的实现，步骤 4 实际上可以在执行步骤 3 时发生。

该算法不会深入研究您必须编写代码的复杂细节。这只是一个帮助您入门的简单指南。