搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 伊斯电子编程 > JAVA 算法---桶排序算法与基数排序算法

JAVA 算法---桶排序算法与基数排序算法

伊斯电子编程 2020-07-29


桶排序的基本思想是:把数组 arr 划分为 n 个大小相同子区间(桶),每个子区间各自排序,最后合并 。计数排序是桶排序的一种特殊情况,可以把计数排序当成每个桶里只有一个元素的情况。

1.找出待排序数组中的最大值 max、最小值 min

2.我们使用 动态数组 ArrayList 作为桶,桶里放的元素也用 ArrayList 存储。桶的数量为(maxmin)/arr.length+1

3.遍历数组 arr,计算每个元素 arr[i] 放的桶

4.每个桶各自排序


public static void bucketSort(int[] arr){int max = Integer.MIN_VALUE;int min = Integer.MAX_VALUE;for(int i = 0; i < arr.length; i++){max = Math.max(max, arr[i]);min = Math.min(min, arr[i]);}//创建桶int bucketNum = (max - min) / arr.length + 1;ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);for(int i = 0; i < bucketNum; i++){bucketArr.add(new ArrayList<Integer>());}//将每个元素放入桶for(int i = 0; i < arr.length; i++){int num = (arr[i] - min) / (arr.length);bucketArr.get(num).add(arr[i]);}//对每个桶进行排序for(int i = 0; i < bucketArr.size(); i++){Collections.sort(bucketArr.get(i));}}



将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列


 public class radixSort {inta[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,101,56,17,18,23,34,15,35,25,53,51};public radixSort(){sort(a);for(inti=0;i<a.length;i++){System.out.println(a[i]);} }public void sort(int[] array){//首先确定排序的趟数;int max=array[0];for(inti=1;i<array.length;i++){if(array[i]>max){max=array[i];} }int time=0;//判断位数;while(max>0){max/=10;time++;}//建立 10 个队列;List<ArrayList> queue=newArrayList<ArrayList>();for(int i=0;i<10;i++){ArrayList<Integer>queue1=new ArrayList<Integer>();queue.add(queue1);}//进行 time 次分配和收集;for(int i=0;i<time;i++){//分配数组元素;for(intj=0;j<array.length;j++){//得到数字的第 time+1 位数;int x=array[j]%(int)Math.pow(10,i+1)/(int)Math.pow(10, i);ArrayList<Integer>queue2=queue.get(x);queue2.add(array[j]);queue.set(x, queue2);}int count=0;//元素计数器;//收集队列元素;for(int k=0;k<10;k++){while(queue.get(k).size()>0){ArrayList<Integer>queue3=queue.get(k);array[count]=queue3.get(0);queue3.remove(0);count++;} } } } }



版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《JAVA 算法---桶排序算法与基数排序算法》的版权归原作者「伊斯电子编程」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注伊斯电子编程微信公众号

伊斯电子编程微信公众号:ESDZBC

伊斯电子编程

手机扫描上方二维码即可关注伊斯电子编程微信公众号

伊斯电子编程最新文章

精品公众号随机推荐

上一篇 >>

挤时间学JDK源码