|
接着我们讨论计数排序：适合知道范围的排序(小范围) 范围大会浪费很多的空间.设被排序的数组为A,排序后存储到B，C为临时数组。所谓计数， 计数排序的原理：设被排序的数组为A,排序后存储到B，C为临时数组。所谓计数，首先是通过一个数组C计算大小等于i的元素个数， 此过程只需要一次循环遍历就可以；在此基础上，计算小于或者等于i的元素个数，也是一重循环就完成。下一步是关键： 逆序循环，从length[A]到1，将A放到B中第C[A]个位置上。原理是：C[A]表示小于等于a的元素个数， 正好是A排序后应该在的位置。而且从length[A]到1逆序循环，可以保证相同元素间的相对顺序不变，这也是计数排序稳定性的体现 时间复杂度:O(n) 空间复杂度:O(k) max-min k越大浪费很多空间 稳定性:稳定 public class CountSort { public static void countSort(int a[],int b[],int k){ //初始化计数数组 int c[] = new int[k]; for(int i=0; i<k; i++) { c = 0; } //计算数组中重复的次数就是说c[0]代表的是A数组中0的个数 for(int i=0;i<a.length;i++) { c[a]=c[a]+1; } //然后c中的个数代表b数组中对应的下标 for(int i=1;i<k;i++) { c=c+c[i-1]; } //将a数组中的元素按照顺序复制到b中 for(int i = a.length-1;i>=0;i--) { b[c[a]-1]=a; c[a]=c[a]-1; } } public static void main(String args[]){ //需要排序的数组 int[] a = new int[]{2,5,3,0,2,3,0,3}; int[] b = new int[8]; countSort(a,b,6);//max=6 min=0, 6=6-0 for (int i = 0; i < 8; i++) { System.out.print(b + " "); } } |
行业聚焦 面试交流 职位推荐 开发视频 技术交流 腾讯微博 新浪微博
友情链接：课课家教育 阿里云 鲜果 W3Cfuns前端网 中国企业家 环球企业家 投资界 传媒梦工场 MSN中文网 Android开发者社区 cnbeta 投资中国网 又拍云存储 美通说传播 IT茶馆 网商在线 商业评论网 TechOrange IT时代周刊 3W创新传媒 开源中国社区 二维工坊 Iconfans 推酷 智能电视网 FreeBuf黑客与极客 财经网 DoNews 凤凰财经 新财富 eoe移动开发者社区 i黑马 网易科技 新浪科技 搜狐IT 创业家 创业邦 腾讯财经 福布斯中文网 天下网商 TechWeb 雷锋网 新浪创业 和讯科技 品途O2O 极客公园 艾瑞网 抽屉新热榜 卖家网 人民网通信频道 拉勾网 创新派 简单云主机
手机版|黑名单|守望者 成才网 在线教育 linux 高级程序设计 C/C++ 大数据
( 蜀ICP备14029946号 ) 
成都守望者科技有限公司 © 2013-2016 All Rights Reserved
收藏