尝试理解桶排序代码
我对下面的代码有三个问题：
static void funct(int[] list) {
final int N = 20;
java.util.ArrayList[] buckets = new java.util.ArrayList[N];
for(int i = 0; i< list.length; i++) {
int key = list[i];
if(buckets[key] = null)
buckets[key].add(list[i]);
}
int k = 0
for(int i = 0; i <buckets.length; i++) {
if(buckets[i] != null) {
for(int j = 0; j< buckets[i].size(); j++)
list[k++] = (Integer)buckets[i].get(j);
}
}
}
该算法有一个主要缺点，是它只能处理最多 20 个元素并且复杂度很低吗？
代码的要点是对元素列表进行排序 - 将它们放入数组中，然后放入桶中，然后再次将它们从桶中放入数组中？
这是我遇到的问题，你如何修改该方法，以便可以传递一个包含另一个类的对象而不是整数的数组？
这是我遇到的问题，如何传递一个包含另一个类的对象而不是整数的数组
I have three questions about the following code:
static void funct(int[] list) {
final int N = 20;
java.util.ArrayList[] buckets = new java.util.ArrayList[N];
for(int i = 0; i< list.length; i++) {
int key = list[i];
if(buckets[key] = null)
buckets[key].add(list[i]);
}
int k = 0
for(int i = 0; i <buckets.length; i++) {
if(buckets[i] != null) {
for(int j = 0; j< buckets[i].size(); j++)
list[k++] = (Integer)buckets[i].get(j);
}
}
}
The algorithm has a major shortcoming, is it that it will only work for up to 20 elements and that it has a poor complexity?
The point of the code is to sort a list of elements - they are put into an array, then put into buckets, then they are put from the buckets into the array again?
Heres the one I'm stumped on, how would you modify the method so that you could pass an array which contains objects of another class instead of integers?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
解决您的问题：
这是两个缺点。暂时不用考虑复杂性；考虑一下它如何适用于 20 多个元素。对于桶排序，其想法是根据元素在元素总范围中的位置来选择桶。在具有基于二进制的整数的计算机上执行此操作的最简单方法是选择数字中的前几位（最高有效位），并使用 2 的幂数的存储桶，例如 16 或 32。您可以使用与运算 (
&) 获取最高有效位（从而计算出存储桶）。然后您可以使用位直接选择存储桶。桶排序背后的想法是使用基数排序的元素对输入进行初始传递，然后对小桶使用不同的排序（或迭代基数排序），这些小桶可能很小并且更容易排序，或者所有存储桶的串联（例如回到数组中）可以以较低的复杂度进行排序。
桶排序基于了解输入的总范围，因此您可以将该范围划分为多个部分，然后单独对输入进行分类。最简单的方法是输入数字。如果输入中的排序只是相对的，并且没有已知的绝对值，也没有简单的方法来确定任何一个元素在总范围中的位置，那么桶排序就不适合。
桶排序
Addressing your questions:
That's two shortcomings. Never mind the complexity for a moment; consider how it is supposed to work for more than 20 elements. For a bucket sort, the idea is that you select a bucket based on the position of the element in the total range of elements. The easiest way to do that on a computer with binary-based integers is to select the first few bits (most significant bits) in the number, and use a power-of-two number of buckets, such as 16 or 32. You can get the most significant bits (and therefore figure out the bucket) with an and operation (
&). You can then use the bits to select the bucket directly.The idea behind bucket sort is to use an element of radix sort for an initial pass over the input, and then use a different sort (or an iterated radix sort) on the small buckets, which may be small and more easily sorted, or the concatenation of all the buckets (such as back into the array) may be sorted with lesser complexity.
Bucket sort is based on knowing the total range of input, so that you can divide up that range into segments and then categorize input individually. The easiest way to do that is if the input is numerical. If the ordering in the input is only relative, and there are no known absolutes and no easy way of figuring out where in the total range any one element is, then bucket sort isn't suitable.
这是一个很好的家庭作业问题。许多问题都是主观的，几乎肯定取决于你的课堂作业。
我建议你自己尝试一下，因为课堂课程比这里的任何答案都能更好地了解讲师正在寻找的内容。
此外，如果教室外的任何人看到这个，答案就是使用内置的数组排序并将这些垃圾扔掉！
This is a good homework question. Many of the questions are kind of subjective and almost certainly depend on your classwork.
I suggest you make a stab at it yourself because the class lessons will give a better idea of what the instructor is looking for than any answers here.
Besides, if anyone outside a classroom saw this, the answer would be to just use the built-in array sorting and throw this garbage away!