java - 尝试理解桶排序代码

Question

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

  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. 这就是我所困惑的问题，您如何修改该方法以便可以传递一个包含另一个类的对象而不是整数的数组？

Answer 1

解决您的问题:

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

2. 桶排序背后的想法是使用基数排序的元素对输入进行初始传递，然后对小桶使用不同的排序(或迭代基数排序)，这些小桶可能很小并且更容易排序，或者所有存储桶的串联(例如回到数组中)可以以较低的复杂性进行排序。

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