Java排序算法之桶排序算法解析
Java桶排序算法
桶排序 (Bucket sort)或所謂的箱排序,是一個排序算法。
工作原理是將數(shù)組分到有限數(shù)量的桶子里,每個桶子再個別排序(有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進行排序)。桶排序是鴿巢排序的一種歸納結(jié)果。當要被排序的數(shù)組內(nèi)的數(shù)值是均勻分配的時候,桶排序使用線性時間 O ( n ) O(n) O(n)。
桶排序是計數(shù)排序的升級版。它利用了函數(shù)的映射關(guān)系,高效與否的關(guān)鍵就在于這個映射函數(shù)的確定。為了使桶排序更加高效,我們需要做到以下兩點:
1. 在額外空間充足的情況下,盡量增大桶的數(shù)量;
2. 使用的映射函數(shù)能夠?qū)⑤斎氲?N 個數(shù)據(jù)均勻的分配到 K 個桶中。 同時,對于桶中元素的排序,選擇何種比較排序算法對于性能的影響至關(guān)重要。
什么時候最快:當輸入的數(shù)據(jù)可以均勻的分配到每一個桶中。
什么時候最慢:當輸入的數(shù)據(jù)被分配到了同一個桶中。
桶排序的基本思想:假設數(shù)據(jù)在[min,max]之間均勻分布,其中min、max分別指數(shù)據(jù)中的最小值和最大值。那么將區(qū)間[min,max]等分成n份,這n個區(qū)間便稱為n個桶。將數(shù)據(jù)加入對應的桶中,然后每個桶內(nèi)單獨排序。由于桶之間有大小關(guān)系,因此可以從大到小(或從小到大)將桶中元素放入到數(shù)組中。
例如: 使用桶排序算法將數(shù)組{ 21,3,30,44,15,36,6,10,9,19,25,48,5,23,47 }進行升序排序。
實現(xiàn)代碼如下所示。
#include<iostream> using namespace std; #include<algorithm> void BubbleSort(int arr[], int len) { for (int i = 0; i < len - 1; i++) { for (int j = 0; j < len - i - 1; j++) { if (arr[j] > arr[j + 1]) { std::swap(arr[j], arr[j + 1]); } } } } void BucketSort(int* arr, int len) { int bucket[5][5]; //分配5個桶 int bucketsize[5]; //每個桶中元素個數(shù)的計數(shù)器 //初始化桶和桶計數(shù)器 memset(bucket, 0, sizeof(bucket)); memset(bucketsize, 0, sizeof(bucketsize)); for (int i = 0; i < len; i++) //把數(shù)組中的數(shù)據(jù)放入桶中 { bucket[arr[i] / 10][bucketsize[arr[i] / 10]++] = arr[i]; } for (int i = 0; i < len; i++) //對每個桶中的數(shù)據(jù)進行排序 BubbleSort(bucket[i],bucketsize[i]); int k = 0; for (int i = 0; i < 5; i++) { for (int j = 0; j < bucketsize[i]; j++) { arr[k++] = bucket[i][j]; //將每個桶中的元素填充到數(shù)組中去 } } } int main() { int a[] = { 21,3,30,44,15,36,6,10,9,19,25,48,5,23,47 }; int len = sizeof(a) / sizeof(a[0]); cout << "排序前:" << endl; for (int i = 0; i < len; i++) { cout << a[i] << " "; } cout << endl; BucketSort(a, len); cout << "排序后:" << endl; for (int i = 0; i < len; i++) { cout << a[i] << " "; } cout << endl; system("pause"); return 0; }
排序前:
21 3 30 44 15 36 6 10 9 19 25 48 5 23 47
排序后:
3 5 6 9 10 15 19 21 23 25 30 36 44 47 48
時間復雜度: O ( n + k ) O(n+k) O(n+k)。
空間復雜度: O ( n + k ) O(n+k) O(n+k)。
穩(wěn)定性: 穩(wěn)定。
到此這篇關(guān)于Java排序算法之桶排序算法解析的文章就介紹到這了,更多相關(guān)Java桶排序算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
java?實現(xiàn)獲取指定位置后的第一個數(shù)字
這篇文章主要介紹了java?實現(xiàn)獲取指定位置后的第一個數(shù)字,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2022-01-01Springboot整合PageOffice 實現(xiàn)word在線編輯保存功能
這篇文章主要介紹了Springboot整合PageOffice 實現(xiàn)word在線編輯保存,本文以Samples5 為示例文件結(jié)合示例代碼給大家詳細介紹,需要的朋友可以參考下2021-08-08SpringBoot使用Nacos進行application.yml配置管理
Nacos是阿里巴巴開源的一個微服務配置管理和服務發(fā)現(xiàn)的解決方案,它提供了動態(tài)服務發(fā)現(xiàn)、配置管理和?服務管理平臺,Nacos使用Raft協(xié)議保證配置的一致性,同時支持多種配置?格式,如properties、yaml等,本文介紹了SpringBoot使用Nacos進行application.yml配置管理2024-12-12SpringBoot中引入MyBatisPlus的常規(guī)操作
這篇文章主要介紹了SpringBoot中引入MyBatisPlus的常規(guī)操作,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2020-11-11