文档章节

排序算法笔记:基数排序 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
08《Java核心技术》之Vector、ArrayList、LinkedList有何区别?

一、提出问题 我们在日常的工作中,能够高效地管理和操作数据是非常重要的。由于每个编程语言支持的数据结构不尽相同,比如我们最早接触到的 C 语言,需要自己实现很多基础数据结构,管理和操...

飞鱼说编程
10/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

小程序异步操作 跨js执行 在微信小程序里面实现跨页面通信

我们知道,在小程序里面一个页面的变化,是通过调用 setData 函数来实现的。所以想做到在二级页面里让一级页面产生变化,最 Quick And Dirty 的做法就是把一级页面的 this 传入到二级页面去,...

xiaogg
31分钟前
1
0
授于管理员登录其它用户

1.沙盒中,授予管理员登录 安全性控制==>登录访问权限政策

在山的那边
33分钟前
4
0
线程安全的CopyOnWriteArrayList介绍

证明CopyOnWriteArrayList是线程安全的 先写一段代码证明CopyOnWriteArrayList确实是线程安全的。 ReadThread.java import java.util.List; public class ReadThread implements Runnable {......

绝地逢生
35分钟前
1
0
Java重写的7个规则

几年前你可能会遇到这样一个面试题:“重写和重载的区别”、而现在随着科技的更迭、面试的问题越来越高级、面试官的问题也越来越深入、此文是上述面试题的一个延伸、让你从简单的重写规则中更...

architect刘源源
36分钟前
3
0
JavaScript异步编程:Generator与Async

从Promise开始,JavaScript就在引入新功能,来帮助更简单的方法来处理异步编程,帮助我们远离回调地狱。 Promise是下边要讲的Generator/yield与async/await的基础,希望你已经提前了解了它。...

前端攻城老湿
36分钟前
16
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部