JAVA十大排序算法之桶排序詳解
桶排序
桶排序是計(jì)數(shù)排序的升級(jí),計(jì)數(shù)排序可以看成每個(gè)桶只存儲(chǔ)相同元素,而桶排序每個(gè)桶存儲(chǔ)一定范圍的元素,通過函數(shù)的某種映射關(guān)系,將待排序數(shù)組中的元素映射到各個(gè)對(duì)應(yīng)的桶中,對(duì)每個(gè)桶中的元素進(jìn)行排序(有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序),最后將非空桶中的元素逐個(gè)放入原序列中。
桶排序需要盡量保證元素分散均勻,否則當(dāng)所有數(shù)據(jù)集中在同一個(gè)桶中時(shí),桶排序失效。
代碼實(shí)現(xiàn)
1.找出數(shù)組中的最大值max和最小值min,可以確定出數(shù)組所在范圍min~max
2.根據(jù)數(shù)據(jù)范圍確定桶的數(shù)量
1.若桶的數(shù)量太少,則桶排序失效
2.若桶的數(shù)量太多,則有的桶可能,沒有數(shù)據(jù)造成空間浪費(fèi)
所以桶的數(shù)量由我們自己來確定,但盡量讓元素平均分布到每一個(gè)桶里,這里提供一個(gè)方式
(最大值 - 最小值)/每個(gè)桶所能放置多少個(gè)不同數(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 作為每個(gè)桶所能放置多少個(gè)不同數(shù)值,即數(shù)值的類型 * 例如當(dāng)BucketSize==5時(shí),該桶可以存放{1,2,3,4,5}這幾種數(shù)字, * 但是容量不限,即可以存放100個(gè)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--; //對(duì)桶中的數(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)); } }
時(shí)間復(fù)雜度
桶排序算法遍歷了2次原始數(shù)組,運(yùn)算量為2N,最后,遍歷桶輸出排序結(jié)果的運(yùn)算量為N,初始化桶的運(yùn)算量為M。
對(duì)桶進(jìn)行排序,不同的排序算法算法復(fù)雜度不同,冒泡排序算法復(fù)雜度為O(N^2),堆排序、歸并排序算法復(fù)雜度為O(NlogN),我們以排序算法復(fù)雜度為O(NlogN)進(jìn)行計(jì)算,運(yùn)算量為N/M * log(N/M) * M
最終的運(yùn)算量為3N+M+N/M * log(N/M) * M,即3N+M+N(logN-logM),去掉系數(shù),時(shí)間復(fù)雜度為O(N+M+N(logN-logM))
算法穩(wěn)定性
桶排序算法在對(duì)每個(gè)桶進(jìn)行排序時(shí),若選擇穩(wěn)定的排序算法,則排序后,相同元素的位置不會(huì)發(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之前啟動(dòng)一個(gè)任務(wù)是通過調(diào)用Thread類的start()方法來實(shí)現(xiàn)的,5.0里提供了一個(gè)新的任務(wù)執(zhí)行架構(gòu)使你可以輕松地調(diào)度和控制任務(wù)的執(zhí)行,并且可以建立一個(gè)類似數(shù)據(jù)庫連接池的線程池來執(zhí)行任務(wù),下面看一個(gè)示例2014-01-01java調(diào)用webservice接口,并解析返回參數(shù)問題
這篇文章主要介紹了java調(diào)用webservice接口,并解析返回參數(shù)問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-07-07Java反射與Fastjson的危險(xiǎn)反序列化詳解
在?Java?中,Computer.class是一個(gè)引用,它表示了?Computer?的字節(jié)碼對(duì)象(Class對(duì)象),這個(gè)對(duì)象被廣泛應(yīng)用于反射、序列化等操作中,那么為什么?parseObject?需要這個(gè)引用呢,帶著這個(gè)問題我們一起通過本文學(xué)習(xí)下吧2024-07-07Java統(tǒng)計(jì)代碼的執(zhí)行時(shí)間的N種方法
在日常開發(fā)中經(jīng)常需要測(cè)試一些代碼的執(zhí)行時(shí)間,但又不想使用向 JMH(Java?Microbenchmark Harness,Java 微基準(zhǔn)測(cè)試套件)這么重的測(cè)試框架,所以本文就匯總了一些 Java 中比較常用的執(zhí)行時(shí)間統(tǒng)計(jì)方法,總共包含以下 6 種,需要的朋友可以參考下2022-08-08JAVA中String類與StringBuffer類的區(qū)別
這篇文章主要為大家詳細(xì)介紹了JAVA中String類與StringBuffer類的區(qū)別,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2016-12-12