Java关于桶排序的知识点总结

发布于 2020-11-22|标签java
复制链接
摘记: 前言:Java数据结构与算法专题会不定时更新,欢迎各位读者监督。本文从最简单的一个排序算法——桶排序开始,分析桶排序的实现思路,代码实现,性能特点以及适用场景。0、其他排序算法索引1、桶排序思想一个简单例子: 对6个人的英语测试成绩(1~10分)进行排序。 ..
前言:Java数据结构与算法专题会不定时更新,欢迎各位读者监督。本文从最简单的一个排序算法——桶排序开始,分析桶排序的实现思路,代码实现,性能特点以及适用场景。0、其他排序算法索引1、桶排序思想一个简单例子:对6个人的英语测试成绩(1~10分)进行排序。假如分数是[6,5,8,8,10,9],用桶排序的思想就是准备10个桶,编号依次为1~10,将成绩放入对应的桶中,例如6分放入6号桶,两个8分放入8号桶...然后按照桶的标号顺序逐一输出(有就输出,没有就不输出),这就是桶排序的基本思想。事实上,这只是一个简易版,试想一下,如果待排序的元素跨度范围比较大,例如1~10000,是不是需要10000个桶?实际上这种情况下,一个桶里并非总放一个元素,很多时候一个桶里放多个元素。其实真正的桶排序和散列表有一样的原理。实际排序中,通常对每个桶中的元素继续使用其他排序算法进行排序,所以更多时候,桶排序会结合其他排序算法一起使用。2、桶排序代码在分析了桶排序的思想后,首先要知道待排序元素的范围,以上述为例,声明一个长度为10的数组作为10个桶,然后将成绩逐一往桶中放时,该桶的值+1,最终输出倒序输出数组下标,数组每个位置的值为几就输出几次,这样就能实现基本的桶排序。 ```java public class BucketSort { private int[] buckets; private int[] array; public BucketSort(int range,int[] array){ this.buckets = new int[range]; this.array = array; } /*排序*/ public void sort(){ if(array!=null && array.length>1){ for(int i=0;i=0; i--){ for(int j=0;j测试代码: ```java public class SortTest { public static void main(String[] args) { testBucketsSort(); } private static void testBucketsSort(){ int[] array = {5,7,3,5,4,8,6,4,1,2}; BucketSort bs = new BucketSort(10, array); bs.sort(); bs.sortOut();//输出打印排序 } } ``` 3、桶排序性能特点桶排序实际上只需要遍历一遍所有的待排元素,然后依次放入指定的位置。如果加上输出排序的时间,就要遍历所有的桶。因此桶排序的时间复杂度是O(n+m),n是待排元素的个数,m是桶的个数,也就是待排元素的范围。这个算法算是相当快的排序算法了,但是空间复杂度比较大。当待排元素的大小范围比较大,但待排元素个数比较少时,空间浪费就比较严重,待排元素分布月均匀,空间利用率越高,事实上这种情况很少见。通过以上性能分析,可以得出桶排序的特点:速度快且简单,但同时空间利用率较低。当待排数据跨度很大时,空间利用率是无法忍受的。4、桶排序适用场景
冀ICP备17029012号-4 | 版权所有©鲍亚龙 |免责声明  | GIF图库  | NUXT版