JAVA十大排序算法之桶排序詳解
桶排序
桶排序是計數(shù)排序的升級,計數(shù)排序可以看成每個桶只存儲相同元素,而桶排序每個桶存儲一定范圍的元素,通過函數(shù)的某種映射關(guān)系,將待排序數(shù)組中的元素映射到各個對應(yīng)的桶中,對每個桶中的元素進(jìn)行排序(有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序),最后將非空桶中的元素逐個放入原序列中。
桶排序需要盡量保證元素分散均勻,否則當(dāng)所有數(shù)據(jù)集中在同一個桶中時,桶排序失效。
代碼實現(xiàn)
1.找出數(shù)組中的最大值max和最小值min,可以確定出數(shù)組所在范圍min~max
2.根據(jù)數(shù)據(jù)范圍確定桶的數(shù)量
1.若桶的數(shù)量太少,則桶排序失效
2.若桶的數(shù)量太多,則有的桶可能,沒有數(shù)據(jù)造成空間浪費
所以桶的數(shù)量由我們自己來確定,但盡量讓元素平均分布到每一個桶里,這里提供一個方式
(最大值 - 最小值)/每個桶所能放置多少個不同數(shù)值+1
3.確定桶的區(qū)間,一般是按照(最大值 - 最小值)/桶的數(shù)量來劃分的,且左閉右開
public class BucketSort { public static final int[] ARRAY = {35, 23, 48, 9, 16, 24, 5, 11, 32, 17}; /** * @param bucketSize 作為每個桶所能放置多少個不同數(shù)值,即數(shù)值的類型 * 例如當(dāng)BucketSize==5時,該桶可以存放{1,2,3,4,5}這幾種數(shù)字, * 但是容量不限,即可以存放100個3 */ public static List<Integer> sort(List<Integer> array, int bucketSize) { if (array == null || array.size() < 2) return array; int max = array.get(0), min = array.get(0); // 找到最大值最小值 for (int i = 0; i < array.size(); i++) { if (array.get(i) > max) max = array.get(i); if (array.get(i) < min) min = array.get(i); } //獲取桶的數(shù)量 int bucketCount = (max - min) / bucketSize + 1; //構(gòu)建桶,初始化 List<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount); List<Integer> resultArr = new ArrayList<>(); for (int i = 0; i < bucketCount; i++) { bucketArr.add(new ArrayList<>()); } //將原數(shù)組的數(shù)據(jù)分配到桶中 for (int i = 0; i < array.size(); i++) { //區(qū)間范圍 bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i)); } for (int i = 0; i < bucketCount; i++) { if (bucketSize == 1) { for (int j = 0; j < bucketArr.get(i).size(); j++) resultArr.add(bucketArr.get(i).get(j)); } else { if (bucketCount == 1) bucketSize--; //對桶中的數(shù)據(jù)再次用桶進(jìn)行排序 List<Integer> temp = sort(bucketArr.get(i), bucketSize); for (int j = 0; j < temp.size(); j++) resultArr.add(temp.get(j)); } } return resultArr; } public static void print(List<Integer> array) { for (int i : array) { System.out.print(i + " "); } System.out.println(""); } public static void main(String[] args) { print(Arrays.stream(ARRAY).boxed().collect(Collectors.toList())); System.out.println("============================================"); print(sort(Arrays.stream(ARRAY).boxed().collect(Collectors.toList()), 2)); } }
時間復(fù)雜度
桶排序算法遍歷了2次原始數(shù)組,運算量為2N,最后,遍歷桶輸出排序結(jié)果的運算量為N,初始化桶的運算量為M。
對桶進(jìn)行排序,不同的排序算法算法復(fù)雜度不同,冒泡排序算法復(fù)雜度為O(N^2),堆排序、歸并排序算法復(fù)雜度為O(NlogN),我們以排序算法復(fù)雜度為O(NlogN)進(jìn)行計算,運算量為N/M * log(N/M) * M
最終的運算量為3N+M+N/M * log(N/M) * M,即3N+M+N(logN-logM),去掉系數(shù),時間復(fù)雜度為O(N+M+N(logN-logM))
算法穩(wěn)定性
桶排序算法在對每個桶進(jìn)行排序時,若選擇穩(wěn)定的排序算法,則排序后,相同元素的位置不會發(fā)生改變,所以桶排序算法是一種穩(wěn)定的排序算法。
總結(jié)
本篇文章就到這里了,希望能給你帶來幫助,也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!
相關(guān)文章
SpringBoot整合Jackson超詳細(xì)用法(附Jackson工具類)
這篇文章主要介紹了SpringBoot整合Jackson超詳細(xì)教程,本篇講的是Jackson的詳細(xì)用法,Jackson工具類在文章最后,直接復(fù)制粘貼即可使用,需要的朋友可以參考下2023-03-03java使用任務(wù)架構(gòu)執(zhí)行任務(wù)調(diào)度示例
在Java 5.0之前啟動一個任務(wù)是通過調(diào)用Thread類的start()方法來實現(xiàn)的,5.0里提供了一個新的任務(wù)執(zhí)行架構(gòu)使你可以輕松地調(diào)度和控制任務(wù)的執(zhí)行,并且可以建立一個類似數(shù)據(jù)庫連接池的線程池來執(zhí)行任務(wù),下面看一個示例2014-01-01java調(diào)用webservice接口,并解析返回參數(shù)問題
這篇文章主要介紹了java調(diào)用webservice接口,并解析返回參數(shù)問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-07-07JAVA中String類與StringBuffer類的區(qū)別
這篇文章主要為大家詳細(xì)介紹了JAVA中String類與StringBuffer類的區(qū)別,具有一定的參考價值,感興趣的小伙伴們可以參考一下2016-12-12