Coding Man桶排序
Contents
1. 简介
在本文中，我们将深入研究**桶排序 算法。在处理 Java 实现以及对我们的解决方案进行单元测试之前，我们将从一些简单的理论开始。最后，我们将看看**桶排序的时间复杂度。
2、桶排序理论
桶排序，有时也称为 bin 排序，是一种特定的排序算法。排序通过将我们想要排序的元素分配到几个单独排序的桶中来工作。通过这样做，我们可以减少元素之间的比较次数并帮助缩短排序时间。
让我们快速浏览一下执行桶排序所需的步骤：
- 设置我们最初为空的存储桶的数组
- 将我们的元素分配到适当的桶中
- 对每个桶进行排序
- 将已排序的存储桶连接在一起以重新创建完整列表
3.Java实现
虽然此算法不是特定于语言的，但我们将在 Java 中实现排序。让我们一步一步地浏览上面的列表，编写代码来对整数列表进行排序。
3.1. 存储桶设置
首先，我们需要确定一个散列算法来决定将哪些元素放入哪个桶中：
private int hash(int i, int max, int numberOfBuckets) {
return (int) ((double) i / max * (numberOfBuckets - 1));
}
定义了哈希方法后，我们现在可以将 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<>());
}
最后，我们需要一个简短的方法来确定输入列表中的最大整数：
private int findMax(List<Integer> input) {
int m = Integer.MIN_VALUE;
for (int i : input) {
m = Math.max(i, m);
}
return m;
}
3.2. 分配元素
现在我们已经定义了桶，我们可以使用hash方法将输入列表的每个元素分配到其相关的桶中：
int max = findMax(initialList);
for (int i : initialList) {
buckets.get(hash(i, max, numberOfBuckets)).add(i);
}
3.3. 对单个存储桶进行排序
随着我们的桶定义并充满整数，让我们使用Comparator对它们进行排序：
Comparator<Integer> comparator = Comparator.naturalOrder();
for(List<Integer> bucket : buckets){
bucket.sort(comparator);
}
3.4. 连接我们的桶
最后，我们需要将我们的存储桶拉在一起以重新创建单个列表。由于我们的桶是排序的，我们只需要遍历每个桶一次并将元素附加到主列表：
List<Integer> sortedArray = new LinkedList<>();
for(List<Integer> bucket : buckets) {
sortedArray.addAll(bucket);
}
return sortedArray;
4. 测试我们的代码
随着我们的实现完成，让我们编写一个快速的单元测试以确保它按预期工作：
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. 时间复杂度
接下来，让我们快速看一下执行桶排序的时间复杂度。
5.1. 最坏的情况是
在最坏的情况下，我们会**在同一个存储桶中以相反的顺序找到所有元素。**当这种情况发生时，我们将桶排序简化为一个简单的排序，其中每个元素都与其他元素进行比较，从而产生 O(n^2) 的时间复杂度。
5.2. 平均案例场景
在我们的平均情况下，我们发现元素在我们的输入桶中分布相对均匀。由于我们的每个步骤只需要对输入桶进行一次迭代，因此我们发现桶排序在 O(n) 时间内完成。