具有最大值和最小值的桶排序

Question

对于一个赋值，我必须创建一个方法来对大小为 25 的数组实现桶排序，该数组填充了 0 到 25（含）之间的随机整数，并且我必须使用最大值作为方法的参数。 Max 是数组中最大的元素（在我的代码中是 25）。然后我必须创建另一个方法，在同一个数组上实现桶排序，但现在它填充了 -25 到 25（含）之间的随机整数，但在这个方法中我必须使用一个最大值和一个最小值，它们都传入. 最大值相同，但 min 是数组中的最小值（在我的代码中为 -25）。我完成了第一部分，但我无法弄清楚如何更改我的第一种方法来完成第二部分。这是我的第一个方法：

public static void sort( int[] arr, int max )
{
  int min = 0;
  int [] bucket=new int[max+1];
  for (int i=0; i< max; i++) {
    bucket[arr[i]]++;;
  }
  for (int i=0; i<bucket.length; i++) {
    for (int j=0; j<bucket[i]; j++) {
       arr[min++]=i;
    }
  }
}

Answer 1

您只需创建存储桶来保存从最小值到最大值的值。例如，如果最小值为 -25，最大值为 25，则您必须创建 51 个存储桶。如果最小值为 -4，最大值为 25，那么您必须创建 30 个桶。因此，我会更改您的代码以生成存储桶以及一些用于填充存储桶的内部逻辑。以下是您的操作方法：

public static void sort( int[] arr, int min, int max )
{
  int nBuckets = max - min + 1;
  int [] bucket=new int[nBuckets];
  for (int i=0; i< arr.length; i++) {
       bucket[arr[i] - min]++;

  }
  int index = 0;
  for (int i=0; i<bucket.length; i++) {
      for (int j =0; j<bucket[i]; j++) {
          arr[index++]=min;
      }
      min++;
  }
}

具有最大值和最小值的桶排序

Bucket Sort with a max and min value

java

sorting

bucket-sort