1. 概述
桶排序（Bucket Sort）又稱箱排序，是一種比較常用的排序算法。其算法原理是將數(shù)組分到有限數(shù)量的桶里，再對每個桶分別排好序（可以是遞歸使用桶排序，也可以是使用其他排序算法將每個桶分別排好序），最后一次將每個桶中排好序的數(shù)輸出。
2. 算法詳解
桶排序的思想就是把待排序的數(shù)盡量均勻地放到各個桶中，再對各個桶進(jìn)行局部的排序，最后再按序?qū)⒏鱾€桶中的數(shù)輸出，即可得到排好序的數(shù)。
-
首先確定桶的個數(shù)。因為桶排序最好是將數(shù)據(jù)均勻地分散在各個桶中，那么桶的個數(shù)最好是應(yīng)該根據(jù)數(shù)據(jù)的分散情況來確定。首先找出所有數(shù)據(jù)中的最大值mx和最小值mn；
根據(jù)mx和mn確定每個桶所裝的數(shù)據(jù)的范圍 size，有
size = (mx - mn) / n + 1，n為數(shù)據(jù)的個數(shù)，需要保證至少有一個桶，故而需要加個1；求得了
size即知道了每個桶所裝數(shù)據(jù)的范圍，還需要計算出所需的桶的個數(shù)cnt，有cnt = (mx - mn) / size + 1，需要保證每個桶至少要能裝1個數(shù)，故而需要加個1； -
求得了
size和cnt后，即可知第一個桶裝的數(shù)據(jù)范圍為 [mn, mn + size)，第二個桶為 [mn + size, mn + 2 * size)，…，以此類推
因此步驟2中需要再掃描一遍數(shù)組，將待排序的各個數(shù)放進(jìn)對應(yīng)的桶中。 -
對各個桶中的數(shù)據(jù)進(jìn)行排序，可以使用其他的排序算法排序，例如快速排序；也可以遞歸使用桶排序進(jìn)行排序；
-
將各個桶中排好序的數(shù)據(jù)依次輸出，最后得到的數(shù)據(jù)即為最終有序。
例子
例如，待排序的數(shù)為：3, 6, 9, 1
1）求得 mx = 9，mn = 1，n = 4
size = （9 - 1) / n + 1 = 3
cnt = (mx - mn) / size + 1 = 3
2）由上面的步驟可知，共3個桶，每個桶能放3個數(shù)，第一個桶數(shù)的范圍為 [1, 4)，第二個[4, 7)，第三個[7, 10)
掃描一遍待排序的數(shù)，將各個數(shù)放到其對應(yīng)的桶中，放完后如下圖所示：
3）對各個桶中的數(shù)進(jìn)行排序，得到如下圖所示：
4）依次輸出各個排好序的桶中的數(shù)據(jù)，即為：1, 3, 6, 9
可見，最終得到了有序的排列。
3. 測試
JAVA
import java.util.ArrayList;
/**
* @author yumu
* @date 2022/8/25
*/
public class BucketSort {
public void bucketSort(int[] nums) {
int n = nums.length;
int mn = nums[0], mx = nums[0];
// 找出數(shù)組中的最大最小值
for (int i = 1; i < n; i++) {
mn = Math.min(mn, nums[i]);
mx = Math.max(mx, nums[i]);
}
int size = (mx - mn) / n + 1; // 每個桶存儲數(shù)的范圍大小，使得數(shù)盡量均勻地分布在各個桶中，保證最少存儲一個
int cnt = (mx - mn) / size + 1; // 桶的個數(shù)，保證桶的個數(shù)至少為1
List<Integer>[] buckets = new List[cnt]; // 聲明cnt個桶
for (int i = 0; i < cnt; i++) {
buckets[i] = new ArrayList<>();
}
// 掃描一遍數(shù)組，將數(shù)放進(jìn)桶里
for (int i = 0; i < n; i++) {
int idx = (nums[i] - mn) / size;
buckets[idx].add(nums[i]);
}
// 對各個桶中的數(shù)進(jìn)行排序，這里用庫函數(shù)快速排序
for (int i = 0; i < cnt; i++) {
buckets[i].sort(null); // 默認(rèn)是按從小打到排序
}
// 依次將各個桶中的數(shù)據(jù)放入返回數(shù)組中
int index = 0;
for (int i = 0; i < cnt; i++) {
for (int j = 0; j < buckets[i].size(); j++) {
nums[index++] = buckets[i].get(j);
}
}
}
public static void main(String[] args) {
int[] nums = {19, 27, 35, 43, 31, 22, 54, 66, 78};
BucketSort bucketSort = new BucketSort();
bucketSort.bucketSort(nums);
for (int num: nums) {
System.out.print(num + " ");
}
System.out.println();
}
}
C++
#include <iostream>
#include <vector>
using namespace std;
class BucketSort {
public:
void bucketSort(vector<int> &nums) {
int n = nums.size();
int mn = nums[0], mx = nums[0];
for (int i = 1; i < n; i++) {
mn = min(mn, nums[i]);
mx = max(mx, nums[i]);
}
int size = (mx - mn) / n + 1; // size 至少要為1
int cnt = (mx - mn) / size + 1; // 桶的個數(shù)至少要為1
vector<vector<int>> buckets(cnt);
for (int i = 0; i < n; i++) {
int idx = (nums[i] - mn) / size;
buckets[idx].push_back(nums[i]);
}
for (int i = 0; i < cnt; i++) {
sort(buckets[i].begin(), buckets[i].end());
}
int index = 0;
for (int i = 0; i < cnt; i++) {
for (int j = 0; j < buckets[i].size(); j++) {
nums[index++] = buckets[i][j];
}
}
}
};
int main() {
vector<int> nums = {19, 27, 35, 43, 31, 22, 54, 66, 78};
BucketSort().bucketSort(nums);
for (auto num: nums) {
cout << num << " ";
}
cout << endl;
return 0;
}
4. 時間復(fù)雜度和空間復(fù)雜度分析
最好時間復(fù)雜度 : O(n + k)
其中k為桶的個數(shù)。即當(dāng)數(shù)據(jù)是均勻分散排列的，那么每個桶分到的數(shù)據(jù)個數(shù)都是一樣的，這個步驟需要O(k)的書劍復(fù)雜度，在對每個桶進(jìn)行排序的時候，最好情況下是數(shù)據(jù)都已經(jīng)是有序的了，那么最好的排序算法的時間復(fù)雜度會是O(n)，因此總的時間復(fù)雜度是 O(n + k) 。
最壞時間復(fù)雜度：O(n^2)
當(dāng)對每個桶中的數(shù)據(jù)進(jìn)行排序的時候，所使用的排序算法，最壞情況下是O(n^2)，因此總的最壞情況下的時間復(fù)雜度為O(n^2）。
平均時間復(fù)雜度：O(n + n2/k + k) <=> O(n)
如果k是根據(jù)Θ(n)來獲取的，那么平均時間復(fù)雜度就是 O(n)。文章來源：http://www.zghlxwxcb.cn/news/detail-820775.html
5. 參考文獻(xiàn)
[1] https://iq.opengenus.org/time-and-space-complexity-of-bucket-sort/
[2] https://www.programiz.com/dsa/bucket-sort文章來源地址http://www.zghlxwxcb.cn/news/detail-820775.html
到了這里，關(guān)于【算法】桶排序（Bucket Sort）詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
