java - 使用链表进行桶排序

Question

我正在尝试在 Java 中实现桶排序，以便对整数数组进行排序。我正在尝试使用链接列表作为我的存储桶，但在理解如何这样做时遇到了一些麻烦。谁能提供一个实现？

有人向我提供了这个算法，但它对我来说意义不大:

Answer 1

既然你没有代码可以分析，那我就给个写出来的答案。创建一个 Bucket 类，它将包含两个数字(0-9、10-19 等)之间的范围、一个插入方法(按顺序插入)，并包含一个空数组。然后创建一个桶列表:

遍历输入列表并将每个数字插入桶列表内的适当桶中。当您插入值时，它会为您排序。最后，获取所有 Bucket 的数组，然后将它们放在一起作为输出列表。

这是 Wikipedia 的分步过程:

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

这是为您提供的算法:

这个简单的翻译为:

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

注意:根据您的实现情况，第 4 步实际上可能会在您执行第 3 步时发生。

此算法不会深入到您必须编写代码的复杂细节中。这只是帮助您入门的简单指南。