文档章节

排序算法笔记:计数排序 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
码字总数 17135
作品 0
海淀
程序员
java 通配符的应用— java 排序算法

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

天地一MADAO_
2014/03/02
0
0
【Java小收获】使用Collection对ArrayList排序

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

HustWolf
05/12
0
0
读《深入理解Java虚拟机》- 笔记08

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

阿历Ali
08/18
0
0
BAT等大厂Android面试书单和知识点清单

java是Android开发的基础,在BAT的初面中,会涉及到比较多的java基础知识,所以比较重要,下面我介绍的书籍内容是由浅到深。 1.Thinking in java:这本书被称为Java的三大圣经之一,虽然书比...

android自学
07/25
0
0
读书笔记之《Java并发编程的艺术》-并发编程容器和框架(重要)

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

Hi徐敏
2015/11/11
0
1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Go语言_通神之路(2)

1、包 每个Go程序都是由包构成,从main包开始运行,就是我上一篇讲到的,都是从main函数开始执行,但是必须在main包下面! package mainimport ( "fmt" "math/rand")func ...

木九天
昨天
5
0
51.php-fpm的pool 慢日志 open_basedir 进程管理

12.21 php-fpm的pool 12.22 php-fpm慢执行日志(测试时报错) 12.23 open_basedir 12.24 php-fpm进程管理 12.21 php-fpm的pool: php-fpm里的pool也叫池子,咱们之前加入过www的配置,这个w...

王鑫linux
昨天
0
0
java内存模型概述

1、Java虚拟机运行时数据分区图 程序计数器:线程私有,是一块较小的内存空间,它是当前线程所执行的字节码文件的行号指示器 java虚拟机栈:线程私有,其生命周期与线程相同,这也就是我们平...

京一
昨天
1
0
shell学习之test语法

因为if-then语句不能测试退出状态码之外的条件,所以提供了test, 如果test命令中列出的条件成立,test命令就会退出并返回退出状态码0;如果条件不成立,test命令就会退出并返回非零的退出状态...

woshixin
昨天
0
0
openJDK之如何下载各个版本的openJDK源码

如果我们需要阅读openJDK的源码,那么需要下载,那么该去哪下载呢? 现在JDK已经发展到版本10了,11已经处于计划中,如果需要特定版本的openJDK,它们的下载链接在哪呢? 1.openJDK的项目 链接...

汉斯-冯-拉特
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部