|
接着上面的例子我们讨论基数排序(LSD):是以某一关键字进行排序，然后在以其他关键字作为排序 时间复杂度:像对三位数的十进制整数进行基数排序的话，n为纪录个数， 每次需要d=3是关键字位数，即关键码个数，将是基数排序进行多个趟的依据， radix=10为关键码的取值范围。所以每一趟的分配时间复杂度为O(n)，每一 趟收集时间复杂度为O(radix)，总共要进行d趟，所以时间复杂度总计为O(d(n+radix))。 空间复杂度:O(radix*d+n) 稳定性:稳定 public class RadixSort { public static void radixsort(int []array,int d)//d代表桶的个数 { int k=0; int m=1; int n=1;//控制位数 //临时集合,对应每个桶的数据 int [][]temp=new int[array.length][array.length]; //对应位数的key int [] order=new int[array.length]; //根据key值分配数据到临时的集合 while(m<=3)//3代表需要位数 { //存储数据 for(int i=0;i<array.length;i++) { //按lsd的方式(个位,十位,百位) int lsd=(array/n)%10; //存值 temp[lsd][order[lsd]]=array; order[lsd]++; } //重新把桶数据放在array中 for(int i=0;i<d;i++) { if(order!=0) { for(int j=0;j<order;j++) { array[k]=temp[j]; k++; } } order = 0;//清空key值,以便下次使用 } n*=10;//对位数的移动 k=0; m++; } } public static void main(String[] args) { int[] data = {73,22,93,43,55,14,28,65,39,81,33,100,345,5,6,8}; RadixSort.radixsort(data,10);//10就是桶数 for (int i = 0; i < data.length; i++) { System.out.print(data + " "); } } } |
行业聚焦 面试交流 职位推荐 开发视频 技术交流 腾讯微博 新浪微博
友情链接：课课家教育 阿里云 鲜果 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
收藏