文档章节

排序算法笔记:基数排序 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的数放在左边...

野小疯
2018/06/05
0
0
各种排序算法及其java程序实现

各种排序算法:冒择路(入)兮(稀)快归堆,桶式排序,基数排序 冒泡排序,选择排序,插入排序,稀尔排序,快速排序,归并排序,堆排序,桶式排序,基数排序 一、冒泡排序(BubbleSort) 1. 基本思...

长平狐
2012/11/12
198
0
各种排序算法及其java程序实现

各种排序算法:冒择路(入)兮(稀)快归堆,桶式排序,基数排序 冒泡排序,选择排序,插入排序,稀尔排序,快速排序,归并排序,堆排序,桶式排序,基数排序 一、冒泡排序(BubbleSort) 1. 基本思...

长平狐
2012/09/03
7.8K
0
java 通配符的应用— java 排序算法

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

天地一MADAO_
2014/03/02
0
0

没有更多内容

加载失败,请刷新页面

加载更多

从 for of 聊到 Generator

你能学到什么 对 for of 更深入的理解 iterator 到底是何方神圣? 数组也是对象,为什么不能用 for of 来遍历对象呢? 如何实现对象的 for of? Generator 又是何方神圣? Generator 有什么用呢...

Jack088
13分钟前
0
0
怎么判断go-sql-driver 安装成功

.下载安装   执行下面两个命令:     下载:go get github.com/Go-SQL-Driver/MySQL     安装:go install github.com/Go-SQL-Driver/MySQL   怎么判断go-sql-driver 安装成功 ...

dragon_tech
21分钟前
0
0
刚入职阿里,告诉你真实的职场生活,兼谈P6、P7、P8的等级

一:拿下offer的人,基本上都有什么特征? 二:为什么选择阿里? 三:阿里的工作氛围什么样? 四:阿里的薪资情况? 五:阿里的晋升空间有多大? 最近部门招聘,很多工程师,包括我在内都参与...

java知识分子
34分钟前
2
0

中国龙-扬科
38分钟前
1
0
windows 安装nvm

1、nvw-windows的官网:https://github.com/coreybutler/nvm-windows/releases 2、选择nvm-setup.zip安装 3、配置环境变量 4、检查nvm是否安装成功 使用管理员权限打开一个命令行。输入nvm v...

灰白发
51分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部