0

我对以下代码有三个问题：

  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);
      }
  }

}

  1. 该算法有一个很大的缺点，是它最多只能处理 20 个元素并且复杂度很差吗？

  2. 代码的重点是对元素列表进行排序-将它们放入数组中，然后放入桶中，然后将它们从桶中再次放入数组中？

  3. 这是我很难过的一个，你将如何修改该方法，以便你可以传递一个包含另一个类的对象而不是整数的数组？

4

2 回答 2

2

解决您的问题：

  1. 这是两个缺点。暂时不要考虑复杂性；考虑它应该如何为 20 多个元素工作。对于桶排序，想法是根据元素在整个元素范围内的位置来选择一个桶。在具有基于二进制整数的计算机上执行此操作的最简单方法是选择数字中的前几位（最高有效位），并使用 2 的幂的存储桶数，例如 16 或 32。您可以使用 and 操作 ( ) 获取最高有效位（并因此找出存储桶&）。然后，您可以使用这些位直接选择存储桶。

  2. 桶排序背后的想法是使用基数排序的元素对输入进行初始传递，然后在可能较小且更容易排序的小桶上使用不同的排序（或迭代基数排序），或者所有桶的连接（例如返回数组）可以以较低的复杂性进行排序。

  3. 桶排序基于知道输入的总范围，因此您可以将该范围划分为段，然后对输入进行单独分类。最简单的方法是输入是数字的。如果输入中的排序只是相对的，并且没有已知的绝对值，也没有简单的方法可以确定任何一个元素在总范围内的位置，那么桶排序就不合适。

于 2009-08-16T16:04:28.113 回答
0

这是一个很好的家庭作业问题。许多问题都是主观的，几乎可以肯定取决于你的课堂作业。

我建议您自己尝试一下，因为课堂课程将比这里的任何答案更好地了解教师正在寻找什么。

此外，如果教室外的任何人看到了，答案就是使用内置的数组排序并将这些垃圾扔掉！

于 2009-08-16T19:23:56.077 回答