文档章节

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

CheN_exe
 CheN_exe
发布于 2014/01/04 13:44
字数 406
阅读 111
收藏 4
/**
 * 基数排序
 * 简述:
 * 		先按照个位排序,将结果串起,再按照十位排序,再将数字串起,再按照排序...
 * 时间复杂度:
 * 		当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
博文 40
码字总数 17192
作品 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
读《深入理解Java虚拟机》- 笔记08

《深入理解Java虚拟机:JVM高级特性与最佳实践》第2版 第10章 早期(编译期)优化 59. 语法糖 在计算机语言中添加某种语法,对语言的功能没有影响,但是方便开发人员使用。 泛型是一种语法糖...

阿历Ali
08/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Web系统大规模并发:电商秒杀与抢购

一、大规模并发带来的挑战 在过去的工作中,我曾经面对过5w每秒的高并发秒杀功能,在这个过程中,整个Web系统遇到了很多的问题和挑战。如果Web系统不做针对性的优化,会轻而易举地陷入到异常...

xtof
今天
1
0
代码质量管理平台-sonarqube

在工作中,往往开发的时候会不怎么注重代码质量的人很多,存在着很多的漏洞和隐患等问题,sonarqube可以进行代码质量的审核,而且十分的残酷。。。。。接下来我们说下怎么安装 进入官网下载:...

落叶清风
今天
6
0
在Ubuntu安装和配置Sphinx

Ubuntu系统默认是配置有sphinx的,先检查一下,别多此一举。。。。。 在开始本指南之前,您需要: 一个Ubuntu 16.04服务器。 sudo的一个非root用户,您可以通过以下设置本教程 。 安装在服务...

阿锋zxf
今天
1
0
Qt编写输入法V2018超级终结版

对于qt嵌入式linux开发人员来说,输入法一直是个鸡肋问题,要么不支持实体键盘同步,要么不能汉字输入,要么不支持网页输入等,这几年通过陆续接触大量的各种输入法应用场景客户,得到真实需...

飞扬青云
今天
2
0
TypeScript基础入门之高级类型的多态的 this类型

转发 TypeScript基础入门之高级类型的多态的 this类型 高级类型 多态的this类型 多态的this类型表示的是某个包含类或接口的子类型。 这被称做F-bounded多态性。 它能很容易的表现连贯接口间的...

durban
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部