Java算法之桶排序Bucket?Sort詳解
1. 概述
桶排序(Bucket Sort)又稱箱排序,是一種比較常用的排序算法。其算法原理是將數組分到有限數量的桶里,再對每個桶分別排好序(可以是遞歸使用桶排序,也可以是使用其他排序算法將每個桶分別排好序),最后一次將每個桶中排好序的數輸出。
2. 算法詳解
桶排序的思想就是把待排序的數盡量均勻地放到各個桶中,再對各個桶進行局部的排序,最后再按序將各個桶中的數輸出,即可得到排好序的數。
1.首先確定桶的個數。因為桶排序最好是將數據均勻地分散在各個桶中,那么桶的個數最好是應該根據數據的分散情況來確定。首先找出所有數據中的最大值mx和最小值mn;
根據mx和mn確定每個桶所裝的數據的范圍 size,有 size = (mx - mn) / n + 1,n為數據的個數,需要保證至少有一個桶,故而需要加個1;
求得了size即知道了每個桶所裝數據的范圍,還需要計算出所需的桶的個數cnt,有 cnt = (mx - mn) / size + 1,需要保證每個桶至少要能裝1個數,故而需要加個1;
2.求得了size和cnt后,即可知第一個桶裝的數據范圍為 [mn, mn + size),第二個桶為 [mn + size, mn + 2 * size),…,以此類推 因此步驟2中需要再掃描一遍數組,將待排序的各個數放進對應的桶中。
3.對各個桶中的數據進行排序,可以使用其他的排序算法排序,例如快速排序;也可以遞歸使用桶排序進行排序;
4.將各個桶中排好序的數據依次輸出,最后得到的數據即為最終有序。
例子
例如,待排序的數為: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個數,第一個桶數的范圍為 [1, 4),第二個[4, 7),第三個[7, 10) 掃描一遍待排序的數,將各個數放到其對應的桶中,放完后如下圖所示:
3)對各個桶中的數進行排序,得到如下圖所示:
4)依次輸出各個排好序的桶中的數據,即為: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]; // 找出數組中的最大最小值 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; // 每個桶存儲數的范圍大小,使得數盡量均勻地分布在各個桶中,保證最少存儲一個 int cnt = (mx - mn) / size + 1; // 桶的個數,保證桶的個數至少為1 List<Integer>[] buckets = new List[cnt]; // 聲明cnt個桶 for (int i = 0; i < cnt; i++) { buckets[i] = new ArrayList<>(); } // 掃描一遍數組,將數放進桶里 for (int i = 0; i < n; i++) { int idx = (nums[i] - mn) / size; buckets[idx].add(nums[i]); } // 對各個桶中的數進行排序,這里用庫函數快速排序 for (int i = 0; i < cnt; i++) { buckets[i].sort(null); // 默認是按從小打到排序 } // 依次將各個桶中的數據放入返回數組中 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; // 桶的個數至少要為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. 時間復雜度和空間復雜度分析
最好時間復雜度 : O(n + k) 其中k為桶的個數。即當數據是均勻分散排列的,那么每個桶分到的數據個數都是一樣的,這個步驟需要O(k)的書劍復雜度,在對每個桶進行排序的時候,最好情況下是數據都已經是有序的了,那么最好的排序算法的時間復雜度會是O(n),因此總的時間復雜度是 O(n + k) 。
最壞時間復雜度:O(n^2) 當對每個桶中的數據進行排序的時候,所使用的排序算法,最壞情況下是O(n^2),因此總的最壞情況下的時間復雜度為O(n^2)。
平均時間復雜度:O(n + n²/k + k) <=> O(n) 如果k是根據Θ(n)來獲取的,那么平均時間復雜度就是 O(n)。
到此這篇關于Java算法之桶排序Bucket Sort詳解的文章就介紹到這了,更多相關Java桶排序Bucket Sort內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
Spring Boot配置特定屬性spring.profiles的方法
這篇文章主要介紹了Spring Boot配置特定屬性spring.profiles的方法,非常不錯,具有一定的參考借鑒價值,需要的朋友可以參考下2018-11-11SSH框架網上商城項目第23戰(zhàn)之在線支付功能實現
這篇文章主要為大家詳細介紹了SSH框架網上商城項目第23戰(zhàn)之在線支付功能實現,感興趣的小伙伴們可以參考一下2016-06-06Springboot MDC+logback實現日志追蹤的方法
MDC(Mapped Diagnostic Contexts)映射診斷上下文,該特征是logback提供的一種方便在多線程條件下的記錄日志的功能,這篇文章主要介紹了Springboot MDC+logback實現日志追蹤的方法,需要的朋友可以參考下2024-04-04