Bucket Sort in Java – Java中的桶式分类

最后修改: 2019年 9月 19日

中文/混合/英文(键盘快捷键：t)

1. Introduction

1.绪论

In this article, we’ll dive into the bucket sort algorithm. We’ll start with a quick bit of theory, before working on the Java implementation alongside unit testing our solution. Finally, we’ll look at the time complexity of bucket sorting.

在这篇文章中，我们将深入探讨bucket sort算法。我们将从快速的位理论开始，然后进行Java实现，并对我们的解决方案进行单元测试。最后，我们将看看桶式排序的时间复杂性。

2. The Theory of Bucket Sorting

2.桶式分拣的理论

Bucket sorting, sometimes known as bin sorting, is a specific sorting algorithm. The sort works by distributing the elements we want to sort into several individually sorted buckets. By doing this, we can reduce the number of comparisons between the elements and help cut the sorting time.

桶式排序，有时也被称为仓式排序，是一种特定的排序算法。该排序的工作原理是将我们要排序的元素分配到几个单独排序的桶中。通过这样做，我们可以减少元素之间的比较次数，有助于缩短排序时间。

Let’s take a quick look at the steps required to perform a bucket sort:

让我们快速浏览一下执行桶式排序所需的步骤。

  1. Set up an array of our initially empty buckets
  2. Distribute our elements into their appropriate buckets
  3. Sort each bucket
  4. Concatenate the sorted buckets together to recreate the full list

3. Java Implementation

3.java实现

While this algorithm isn’t language-specific, we’ll be implementing the sort in Java. Let’s go through the above list step by step and write the code to sort a list of integers.

虽然这种算法并不是特定的语言，但我们将在Java中实现这种排序。让我们一步一步地浏览上面的列表，写出代码来对整数列表进行排序。

3.1. Bucket Setup

3.1 桶的设置

First, we need to determine a hashing algorithm to decide which of our elements gets placed into which bucket:

首先，我们需要确定一种散列算法来决定我们的哪个元素被放入哪个桶中。

private int hash(int i, int max, int numberOfBuckets) {
    return (int) ((double) i / max * (numberOfBuckets - 1));
}

With our hash method defined, we can now specify the number of bins as a square root of the input list size:

有了我们的哈希方法的定义，我们现在可以指定输入列表大小的平方根作为bin的数目。

final int numberOfBuckets = (int) Math.sqrt(initialList.size());
List<List<Integer>> buckets = new ArrayList<>(numberOfBuckets);
for(int i = 0; i < numberOfBuckets; i++) {
    buckets.add(new ArrayList<>());
}

Finally, we need a short method to determine the maximum integer in our input list:

最后，我们需要一个简短的方法来确定我们输入列表中的最大整数。

private int findMax(List<Integer> input) {
    int m = Integer.MIN_VALUE;
    for (int i : input) {
        m = Math.max(i, m);
    }
    return m;
}

3.2. Distributing the Elements

3.2.分布要素

Now that we have our buckets defined, we can distribute each element of our input list into its relevant bucket using the hash method:

现在我们已经定义了我们的桶，我们可以使用hash方法将我们输入列表中的每个元素分配到相关的桶中。

int max = findMax(initialList);

for (int i : initialList) {
    buckets.get(hash(i, max, numberOfBuckets)).add(i);
}

3.3. Sorting the Individual Buckets

3.3.对单个桶进行分类

With our buckets defined and full of integers, let’s use a Comparator to sort them:

在定义了我们的桶并装满了整数之后，让我们用一个比较器来对它们进行排序。

Comparator<Integer> comparator = Comparator.naturalOrder();

for(List<Integer> bucket  : buckets){
    bucket.sort(comparator);
}

3.4. Concatenating Our Buckets

3.4.连接我们的桶

Finally, we need to pull our buckets together to recreate the single list. Since our buckets are sorted, we only need to loop through each bucket once and append the elements to a master list:

最后，我们需要把我们的桶拉到一起，重新创建一个单一的列表。由于我们的水桶是经过排序的，我们只需要在每个水桶中循环一次，并将这些元素追加到一个主列表。

List<Integer> sortedArray = new LinkedList<>();

for(List<Integer> bucket : buckets) {
    sortedArray.addAll(bucket);
} 

return sortedArray;

4. Testing Our Code

4.测试我们的代码

With our implementation complete, let’s write a quick unit test to make sure it works as expected:

随着我们的实现的完成，让我们写一个快速的单元测试，以确保它能按预期工作。

BucketSorter sorter = new IntegerBucketSorter();

List<Integer> unsorted = Arrays.asList(80,50,60,30,20,10,70,0,40,500,600,602,200,15);
List<Integer> expected = Arrays.asList(0,10,15,20,30,40,50,60,70,80,200,500,600,602);

List<Integer> sorted = sorter.sort(unsorted);

assertEquals(expected, sorted);

5. Time Complexity

5.时间的复杂性

Next, let’s take a quick look at the time complexity of performing a bucket sort.

接下来，让我们快速看一下执行桶式排序的时间复杂度。

5.1. Worst Case Scenario

5.1.最坏情况下的设想

In our worst-case scenario, we’d find all of our elements in the same bucket and in reverse order. When this case occurs, we’re reducing our bucket sort to a simple sort in which every element is compared to every other element, yielding a time complexity of O(n²).

在我们最坏的情况下，我们会发现我们所有的元素都在同一个桶里，而且顺序相反。当这种情况发生时，我们会将我们的桶排序减少到一个简单的排序，其中每个元素都与其他元素进行比较，产生一个O(n²)的时间复杂性。

5.2. Average Case Scenario

5.2.平均案例情况

In our average case, we find that the elements are relatively evenly distributed among our input buckets. Since each of our steps requires just one iteration through our input buckets, we find that our bucket sort completes in O(n) time.

在我们的平均情况下，我们发现元素相对均匀地分布在我们的输入桶中。由于我们的每个步骤只需要在输入桶中进行一次迭代，我们发现我们的桶排序在O(n)时间内完成。

6. Conclusion

6.结论

In this article, we saw how to implement a bucket sort in Java. We also looked at the time complexity of the bucket sort algorithm.

在这篇文章中，我们看到了如何在Java中实现一个桶状排序。我们还研究了桶式排序算法的时间复杂度。

As always, the code shown in this article is available over on GitHub.

一如既往，本文中显示的代码可在GitHub上获得。