桶排序
桶排序是一種比較型排序演算法。它通過將元素分佈到桶或倉中,並使用不同的演算法(通常是插入排序)對各個桶的內容進行排序。然後將各個排序後的桶加在一起,得到最終的排序陣列。這種排序演算法的方法也被稱為分散收集法。它主要用於當輸入的內容均勻分佈在一個範圍內,比如浮點數從 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