文档章节

排序算法笔记:基数排序 RadixSort in java

CheN_exe
 CheN_exe
发布于 2014/01/04 13:44
字数 406
阅读 111
收藏 4
点赞 0
评论 0
/**
 * 基数排序
 * 简述:
 * 		先按照个位排序,将结果串起,再按照十位排序,再将数字串起,再按照排序...
 * 时间复杂度:
 * 		当k=O(n)时,O(n)
 * 空间复杂度:
 * 		O(n)
 * 优点:
 * 		
 * 缺点:
 * 		要求全为自然数
 * 可改进:
 * 		可以自建Map或List,将字母顺序加入,则可以进行更多种类排序.但是小数比较麻烦
 * @author CheN
 *
 */
public class RadixSort {
	
	public static int[] asc( int[] array ){
		int index = 1; // 最大数字位数(如100为3位数字,2000为4位数字)
		// 取得最大数字位数
		for( int i = 0 ; i < array.length ; i++ ){
			int length = Integer.toString(array[i]).length();
			if( index < length ){
				index = length;
			}
		}
		return sort( array , 0 , index);
	}
	
	/**
	 * @param array 数组
	 * @param exponent 起始位数(代码中实际意义为:10的exponent次方。起始位数即为10的0次方,所以为个位) 
	 * @param index 最大数字位数(如100为3位数字,2000为4位数字)
	 * @return
	 */
	private static int[] sort( int[] array , int exponent , int index){
		int length = array.length;
		// 此处我选择用List,而不是int[n][n]的数组
		List<List<Integer>> list = new ArrayList<List<Integer>>();
		for( int i = 0 ; i < 10  ; i++ ){
			list.add(new ArrayList<Integer>());
		}
		// 按照各个位数排序统计
		for( int i = 0 ; i < length ; i++ ){
			int num = 0;
			String str = Integer.toString(array[i]);
			if( str.length() - exponent - 1 >= 0 )
				num = Integer.parseInt(str.substring(str.length() - exponent - 1, str.length() - exponent));
			list.get(num).add(array[i]);
		}
		// 串起桶中数据
		for( int k = 0 , i = 0 ; i < list.size() ; i++ ){
			for( int j = 0 ; j < list.get(i).size() ; j++ ){
				array[ k++ ] = list.get(i).get(j);
			}
		}
		// 若还有更高位数,则按照下一位数进行排序
		if( index == ++exponent ){
			return array;
		}else{
			return sort( array , exponent , index );
		}
	}
}

 


若有错误或不妥之处,敬请谅解并指点。

© 著作权归作者所有

共有 人打赏支持
CheN_exe
粉丝 2
博文 31
码字总数 16744
作品 0
海淀
程序员
android ndk 基数排序

由于工作需要需要了解一下android的ndk开发,就做了一个简单的例子。 环境jdk1.6,ndk=android-ndk-r8-windows,eclips3.7,androidsdk=10 功能:android的调用一个c99写的基数排序方法 工程结构...

貌似高手
2012/07/09
0
0
java排序之快速排序、归并排序、基数排序

前两篇说了Java排序中的冒泡、选择、插入、希尔等排序算法,今天就探讨一下剩下的三种常用排序。 快速排序: 当要求时间最快时,就可以用快速排序算法。 选择第一个数为p,小于p的数放在左边...

野小疯
06/05
0
0
java 通配符的应用— java 排序算法

这几天无聊,又重新学起java的排序算法,为DualPivotQuickSort做准备。为了更好地适应各种情况,我们选择使用通用类型T和通配符的上下界来实现,同时这次谈的是对数组对象的排序。如果你对j...

天地一MADAO_
2014/03/02
0
0
几种排序算法的JAVA语言实现

1、选择排序最差时间复杂度О(n²)最优时间复杂度О(n²)平均时间复杂度О(n²)最差空间复杂度О(n) total, O(1) auxiliary选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理...

奔跑的蛮牛
2013/12/22
0
0
排序算法汇总——转载自http://blog.csdn.net/zhanglong_daniel/article/details/52513058

1. 冒泡排序 1.1 算法原理: S1:从待排序序列的起始位置开始,从前往后依次比较各个位置和其后一位置的大小并执行S2。 S2:如果当前位置的值大于其后一位置的值,就把他俩的值交换(完成一次...

biubiubiu!
2016/10/09
0
0
【Java小收获】使用Collection对ArrayList排序

正文之前 毕业论文肝到14000实在是肝不动了,必须开点新模块才能走得动,不然没法搞。所以最近在琢磨离散化这个东西。主要是参考的这个文献 正文 好吧,这个只是个Part,做个笔记而已,不必较...

HustWolf
05/12
0
0
读书笔记之《Java并发编程的艺术》-并发编程容器和框架(重要)

读书笔记部分内容来源书出版书,版权归本书作者,如有错误,请指正。 欢迎star、fork,读书笔记系列会同步更新 git https://github.com/xuminwlt/j360-jdk module j360-jdk-thread/me.j360....

Hi徐敏
2015/11/11
0
1
程序员必知的8大排序(java实现)

8种排序之间的关系:  1、 直接插入排序   (1)基本思想:   在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好...

小帅帅丶
2015/01/09
0
7
阿里历年经典Java面试题汇总

Volatile的特征: A、禁止指令重排(有例外) B、可见性 Volatile的内存语义: 当写一个volatile变量时,JMM会把线程对应的本地内存中的共享变量值刷新到主内存。 当读一个volatile变量时,J...

Java团长17
07/11
0
0
几大排序算法的Java实现(原创)

几大排序算法的Java实现 更新中... 注: 该类中附有随机生成[min, max)范围不重复整数的方法,如果各位看官对此方法有什么更好的建议,欢迎提出交流。 各个算法的思路都写在该类的注释中了,...

loveuwp
04/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

TextView设置行间距、字体间距

一、设置行间距 1、设置行间距:android:lineSpacingExtra,取值范围:正数、负数和0,正数表示增加相应的大小,负数表示减少相应的大小,0表示无变化 2、设置行间距的倍数:android:lineSpa...

王先森oO
1分钟前
0
0
适配器模式

适配器模式(Adapter):将一个类的接口转换成客户端希望的另外一个接口,适配器模式使得原本由于接口不兼容而不能一起工作的那些类可以一起工作。 适配器用于连接两种不同种类的对象,使其毫...

阿元
1分钟前
0
0
CoreText进阶(四)-文字行数限制和显示更多

CoreText进阶(四)-文字行数限制和显示更多 用例和效果 Demo:CoreTextDemo 效果图: 默认的截断标识和自定义的截断标识符效果图  点击查看更多之后的效果图  为了可以设置显示的行数以...

aron1992
4分钟前
0
0
nginx的五种负载算法

nginx的五种负载算法 2017年04月26日 15:01:11 阅读数:1297 1.round robin(默认) 轮询方式,依次将请求分配到各个后台服务器中,默认的负载均衡方式。 适用于后台机器性能一致的情况。 挂...

linjin200
6分钟前
0
0
Android RecyclerView快速上手

RecyclerView mainMenu = findViewById(R.id.fragmentMain); mainMenu.setLayoutManager(new GridLayoutManager(getActivity(),4)); mainMenu.setAdapter(new MainAdapter......

燕归南
8分钟前
0
0
RabbitMQ实战:理解消息通信 

应用RabbitMQ的5种队列 一、简单队列 P:消息的生产者 C:消息的消费者 红色:队列 简单队列的生产者和消费者关系一对一 但有时我们的需求,需要一个生产者,对应多个消费者,那就可以采用第...

spinachgit
9分钟前
0
0
Linux的使用技巧:到底要不要会用?[图]

Linux的使用技巧:到底要不要会用?[图] 最近有个项目接近了尾声,要进入到调试测试阶段。这是一个使用Springboot框架为后台程序,mpvue构建的小程序项目。服务器我最终仍旧选择了Linux操作系...

原创小博客
10分钟前
0
0
记elasticdump 备份数据导出导入

版本: elasticsearch 5.5.2 elasticdump 2.2 系统 CentOS7.3 因项目需求 从生产导出一份索引到测试 帮助文档 https://github.com/taskrabbit/elasticsearch-dump?utm_source=dbweekly&utm_m......

雁南飞丶
11分钟前
0
0
saltstack配置目录管理

1.服务端配置 -接着编辑之前的 top.sls 文件 #vim /srv/salt/top.sls //修改为如下 base: 'slaver.test.com': - filedir -新建 filedir.sls 文件 # vim /srv/salt/filedir.sls file-dir: fi......

硅谷课堂
11分钟前
0
0
python日期时间

日期和时间 Python内建的datetime模块提供了datetime、date和time类型。datetime类型结合了date和time,是最常使用的: In [102]: from datetime import datetime, date, timeIn [103]:...

火力全開
18分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部