桶排序
桶排序是一种比较型排序算法。它通过将元素分布到桶或仓中，并使用不同的算法（通常是插入排序）对各个桶的内容进行排序。然后将各个排序后的桶加在一起，得到最终的排序数组。这种排序算法的方法也被称为分散收集法。它主要用于当输入的内容均匀分布在一个范围内，比如浮点数从 0.00 到 1.00。
桶排序算法
假设我们有一个包含 n 元素的无序数组 A[]。
-
创建
k(理想的情况是k是n)个空桶，将输入的范围分成相等的部分。 -
对于数组
A中出现的每一个元素A[i]，执行以下操作。 -
将
A[i]插入到索引为n*A[i]的桶中。 -
使用插入排序算法对各个桶进行排序。
-
按顺序检查各桶，并将排序后的桶进行连接，形成最终的排序数组。
桶排序示例
假设我们有数组：(0.22,0.33,0.1,0.45,0.38,0.55,0.21,0.31). 我们将使用桶排序算法对其进行排序。
- 制作
10个范围为0.1的桶
| 桶 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
- 将元素插入到桶后，我们得到，
| 桶 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 0.1 | 0.22, 0.21 | 0.33, 0.38, 0.31 | 0.45 | 0.55 |
- 对各个桶进行排序，得到。
| 桶 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| 0.1 | 0.21, 0.22 | 0.31, 0.33, 0.38 | 0.45 | 0.55 |
将所有的结果加在一起，我们得到最终的排序数组为。(0.1,0.21,0.22,0.31,0.33,0.38,0.45,0.55)。
桶排序算法的实现
#include<bits/stdc++.h>
using namespace std;
void bucketSort(float *array, int size) {
vector<float> bucket[size];
//insert elements into different buckets.
for (int i = 0; i < size; i++) {
bucket[int(size * array[i])].push_back(array[i]);
}
//sort individual buckets.
for (int i = 0; i < size; i++) {
sort(bucket[i].begin(), bucket[i].end());
}
int index = 0;
for (int i = 0; i < size; i++) {
while (!bucket[i].empty()) {
array[index++] = *(bucket[i].begin());
bucket[i].erase(bucket[i].begin());
}
}
}
int main() {
int n = 8;
float arr[8] = {0.22,0.33,0.1,0.45,0.38,0.55,0.21,0.31};
cout << "Input arr: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
bucketSort(arr, n); // Sort elements in ascending order
cout << "Output arr: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
桶排序算法的复杂度
时间复杂度
- 平均情况
如果元素是随机分布的，则会出现平均情况，该算法可以得到非常有效的结果。时间复杂度为[大 Theta]量级：O(n+k)。它是少数几个具有平均线性时间复杂度的算法之一，如果桶大小的平方和是线性的 n，这个复杂度就会成立。
- 最坏情况
最坏的情况发生在许多元素在数组中距离很近的情况下，并被聚集在同一个桶中。它剥夺了将输入划分到桶中的所有优势，总复杂度变得取决于所使用的排序算法。当元素顺序相反时，插入排序的最坏情况时间复杂度为 O(n2)。因此，最坏情况下的时间复杂度为 [Big O]。O(n2)。
- 最佳情况
最好的情况是，元素均匀分布在所有的桶中，或者我们得到一个已经排序的数组。总时间复杂度包括创建桶 O(n) 和排序 O(k) 所需的时间。最佳情况下的时间复杂度是 [Big Omega]：O(n+k)。
空间复杂度
桶式排序算法最差的空间复杂度是 O(n*k)，其中 n 是元素的数量，k 是桶的数量。通过减少容纳所有元素的空间和存储指向桶起始的指针，空间复杂度可以降低到 O(n+k)。
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn