文档章节

排序算法笔记:计数排序 CountingSort in java

CheN_exe
 CheN_exe
发布于 2014/01/04 13:40
字数 387
阅读 30
收藏 0
/**
 * 计数排序
 * 简述:
 * 		创建一个临时数组temp[max],max>=max(array).先统计array[i]的个数于temp[array[i]]上,再通过temp[]确定每一个数字的位置(算出有m个比n小的,则n就在m+1上),最后将数据串与result上.
 * 时间复杂度:
 * 		当k=O(n)时,为O(n)
 * 空间复杂度:
 * 		O(n)
 * 优点:
 * 		时间复杂度几乎为最低
 * 缺点:
 * 		对数组内容要求较多:1.全为自然数;2.若数字太大,则需要过多额外空间.
 * 可改进:
 * 		通过把100当做1的方式,可以实现两位小数的排序,不过太浪费空间
 * @author CheN
 *
 */
public class CountingSort {
	public static int[] asc( int[] array ){
		return sort(array);
	}
	
	private static int[] sort( int[] array ){
		int max = 0;//max为某个整数,该整数大于array中最大的整数
		for( int i = 0 ; i < array.length ; i++ ){
			if( max < array[i]){
				max = array[i];
			}
		}
		int[] result = new int[array.length] , temp = new int[max];
//		for( int i = 0 ; i < k ; i++ ){
//			temp[i] = 0;
//		}
		// 计数
		for( int i = 0 ; i < array.length ; i++ ){
			temp[array[i]] = temp[array[i]]+1;
		}
		// 统计比第i位小的数字个数的总和,即统计数组中每一位之前的值之和。
		for( int i = 1 ; i < max ; i++ ){
			temp[i] = temp[i]+temp[i-1];
		}
		// 将临时数组中的不为零的位,分别按照它的值的数量,填入result数组中,从而完成排序
		for( int i = array.length - 1 ; i >= 0 ; i-- ){
			result[temp[array[i]]-1] = array[i];
			temp[array[i]] = temp[array[i]]-1;
		}
		return result;
	}
}


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

© 著作权归作者所有

共有 人打赏支持
CheN_exe
粉丝 2
博文 40
码字总数 17192
作品 0
海淀
程序员
私信 提问
java 通配符的应用— java 排序算法

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

天地一MADAO_
2014/03/02
0
0
输入排序算法的名字与待排序的数据列可完成数据排序?

拜托各位大神了 1.通过程序实现排序算法,算法支持冒泡排序、插入排序、希尔选择,且可扩展算法。只需要输入排序算法的名字与待排序的数据列表即可完成数据排序; 三个算法的代码写出来了,后...

禧禧的禧
2014/06/07
107
0
08《Java核心技术》之Vector、ArrayList、LinkedList有何区别?

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

飞鱼说编程
2018/10/11
0
0
Redis学习笔记之基本数据结构

Redis基础数据结构 Redis有5种基本数据结构:String(字符串)、list(列表)、set(集合)、hash(哈希)、zset(有序集合) 字符串string 字符串类型是Redis的value最简单的数据结构,类似与Java语言...

smileNicky
2018/09/26
0
0
可视化的数据结构和算法

还记得之前发布过的那个关于可视化排序的文章吗?在网上又看到了一个旧金山大学David Galles做的各种可视化的数据结构和基本算法的主页,网址在这里,大家可以看看。我把这个页面的目录列在下...

戴威
2011/05/12
962
5

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周二乱弹 —— 以后我偷小鱼干养你

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @庞巴哥 :只有这节奏瞬间变得轻松。。。。。。。。。分享Talking Eyes的单曲《In the sun (Extended Version)》: 《In the sun (Extended Ve...

小小编辑
12分钟前
0
0
多表查询

第1章 多表关系实战 1.1 实战1:省和市  方案1:多张表,一对多  方案2:一张表,自关联一对多 1.2 实战2:用户和角色 (比如演员和扮演人物)  多对多关系 1.3 实战3:角色和权限 (比如...

stars永恒
今天
7
0
求推广,德邦快递坑人!!!!

完全没想好怎么来吐槽自己这次苦逼的德邦物流过程了,只好来记一个流水账。 从寄快递开始: 2019年1月15日从 德邦物流 微信小app上下单,截图如下: 可笑的是什么,我预约的是17号上门收件,...

o0无忧亦无怖
昨天
7
0
Mac Vim配置

1.升级 vim   我自己 MacBook Pro 的系统还是 10.11 ,其自带的 vim 版本为 7.3 ,我们将其升至最新版: 使用 homebrew : brew install vim --with-lua --with-override-system-vim 这将下...

Pasenger
昨天
8
0
vmware安装Ubuntu上不了网?上网了安装不了net-tools,无法执行ifconfig?

1.重新设置网络适配器还是不行,如下指定nat 2.还需要指定共享网络,我是在无线环境下 3.无法执行ifconfig https://packages.ubuntu.com/bionic/net-tools到这个网站下载net-tools的deb文件...

noob_chr
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部