Java怎么实现count排序
这篇文章主要讲解了“Java怎么实现count排序”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“Java怎么实现count排序”吧!
专注于为中小企业提供成都网站制作、网站建设、外贸网站建设服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业祁县免费做网站提供优质的服务。我们立足成都,凝聚了一批互联网行业人才,有力地推动了上1000+企业的稳健成长,帮助中小企业通过网站建设实现规模扩充和转变。
简介
count排序是一种空间换时间的算法,我们借助一个外部的count数组来统计各个元素出现的次数,从而最终完成排序。
count排序的例子
count排序有一定的限制,因为外部的count数组长度是和原数组的元素范围是一致的,所以count排序一般只适合数组中元素范围比较小的情况。
我们举一个0-9的元素的排序的例子:3,4,2,5,6,2,4,9,1,3,5。
先看一个动画,看看是怎么排序的:
count数组里面存放的是从0到9这些元素出现的次数。
我们遍历原始数组,遇到相应的数字就给相应的count+1。
等所有的元素都count之后,再根据count数组中的值还原排序过后的数组。
count排序的java实现
count排序很简单,我们主要掌握下面两个大的步骤:
遍历原始数组,构建count数组。
根据count数组中的count值,重新构建排序数组。
public class CountingSort { public void doCountingSort(int[] array){ int n = array.length; // 存储排序过后的数组 int output[] = new int[n]; // count数组,用来存储统计各个元素出现的次数 int count[] = new int[10]; for (int i=0; i<10; ++i) { count[i] = 0; } log.info("初始化count值:{}",count); // 将原始数组中数据出现次数存入count数组 for (int i=0; i0){ output[j++]=i; } } log.info("构建output之后的output值:{}",output); //将排序后的数组写回原数组 for (int i = 0; i 上面的注释应该很清楚了。
运行的结果如下:
count排序的第二种方法
在我们获得count数组中每个元素的个数之后,其实我们还有另外一个生成结果数组的办法:
// 这里是一个小技巧,我们根据count中元素出现的次数计算对应元素第一次应该出现在output中的下标。 //这里的下标是从右往左数的 for (int i=1; i<10; i++) { count[i] += count[i - 1]; } log.info("整理count对应的output下标:{}",count); // 根据count中的下标,构建排序后的数组 //插入一个之后,相应的count下标要减一 for (int i = n-1; i>=0; i--) { output[count[array[i]]-1] = array[i]; --count[array[i]]; } log.info("构建output之后的output值:{}",output);主要分为两步:
第一步我们根据count中元素出现的次数计算对应元素第一次应该出现在output中的下标。这里的下标是从右往左数的。
第二步根据count中的下标,构建排序后的数组,插入一个之后,相应的count下标要减一。
感谢各位的阅读,以上就是“Java怎么实现count排序”的内容了,经过本文的学习后,相信大家对Java怎么实现count排序这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是创新互联,小编将为大家推送更多相关知识点的文章,欢迎关注!
网页标题:Java怎么实现count排序
网页网址:http://scyanting.com/article/jgjhjh.html