文档章节

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

CheN_exe
 CheN_exe
发布于 2014/01/04 13:40
字数 387
阅读 30
收藏 0
点赞 0
评论 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
博文 31
码字总数 16744
作品 0
海淀
程序员
【Java小收获】使用Collection对ArrayList排序

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

HustWolf ⋅ 05/12 ⋅ 0

阿里一面 京东一面+二面 | 掘金技术征文

阿里一面 简单说说在学校做过最有成就感的事情(和技术相关的) 你的项目用到了数据库,谈谈对事务的理解 假设你要做一个银行app,有可能碰到多个人同时向一个账户打钱的情况,有可能碰到什么...

京东一面 ⋅ 04/18 ⋅ 0

MySQL多数据源笔记5-ShardingJDBC实战

Sharding-JDBC集分库分表、读写分离、分布式主键、柔性事务和数据治理与一身,提供一站式的解决分布式关系型数据库的解决方案。 从2.x版本开始,Sharding-JDBC正式将包名、Maven坐标、码云仓...

狂小白 ⋅ 03/19 ⋅ 0

Scala笔记整理(二):Scala数据结构—数组、map与tuple

[TOC] 数组 定长数组 如果你需要一个长度不变的数组,可以用Scala中的Array。例如: 在JVM中,Scala的Array以Java数组方式实现。示例中的数组在JVM中的类型为java.lang.String[]。Int、Doubl...

xpleaf ⋅ 04/18 ⋅ 0

几大排序算法的Java实现(原创)

几大排序算法的Java实现 更新中... 注: 该类中附有随机生成[min, max)范围不重复整数的方法,如果各位看官对此方法有什么更好的建议,欢迎提出交流。 各个算法的思路都写在该类的注释中了,...

loveuwp ⋅ 04/23 ⋅ 0

java排序之快速排序、归并排序、基数排序

前两篇说了Java排序中的冒泡、选择、插入、希尔等排序算法,今天就探讨一下剩下的三种常用排序。 快速排序: 当要求时间最快时,就可以用快速排序算法。 选择第一个数为p,小于p的数放在左边...

野小疯 ⋅ 06/05 ⋅ 0

Java并发基础你需要知道的基础知识

多线程和并发编程是Java里面的核心内容,通常有以下一些概念需要重点掌握。 线程; 锁; 同步器; 并发容器和框架; Java并发工具类; 原子操作类; Executor框架(执行机制); 并发基础概念 ...

异步社区 ⋅ 05/30 ⋅ 0

Java 面试知识点解析(三)——JVM篇

前言: 在遨游了一番 Java Web 的世界之后,发现了自己的一些缺失,所以就着一篇深度好文:知名互联网公司校招 Java 开发岗面试知识点解析 ,来好好的对 Java 知识点进行复习和学习一番,大部...

我没有三颗心脏 ⋅ 05/16 ⋅ 0

JavaWeb07-HTML篇笔记(二)

1.1 案例一:使用JDBC完成CRUD的操作:1.1.1 需求: 对分类管理使用JDBC进行CRUD的操作. 1.1.2 分析:1.1.2.1 技术分析: 【JDBC的概述】 Ø JDBC:Java DataBase Connectivity Java数据库的连...

我是小谷粒 ⋅ 05/16 ⋅ 0

Java 编程之美:并发编程基础晋级篇

本文来自作者 加多 在 GitChat 上分享 「Java 并发编程之美:并发编程基础晋级篇」 编辑 | Mc Jin 借用 Java 并发编程实践中的话,编写正确的程序并不容易,而编写正常的并发程序就更难了! ...

gitchat ⋅ 04/18 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

vim基础-编辑模式-命令模式

编辑模式:可以编辑修改文件。编辑模式下 按“esc”键返回一般模式。 按一次“Insert”键 (一般在键盘回格键右边)作用和“i”一样表示“插入”。按两次“Insert”键表示“替换”,作用为:...

ZHENG-JY ⋅ 10分钟前 ⋅ 0

MaxCompute读取分析OSS非结构化数据的实践经验总结

摘要: 本文背景 很多行业的信息系统中,例如金融行业的信息系统,相当多的数据交互工作是通过传统的文本文件进行交互的。此外,很多系统的业务日志和系统日志由于各种原因并没有进入ELK之类...

阿里云云栖社区 ⋅ 15分钟前 ⋅ 0

Linux操作系统有何优势?Linux学习

  当今世界流行的操作系统有3大类,Linux、Mac OS和Windows操作系统,Linux操作系统因其开源、免费、跨平台、良好的界面等特性,深受广大程序员们的青睐!   Linux操作系统被广泛的应用于...

老男孩Linux培训 ⋅ 17分钟前 ⋅ 0

Spring Cloud Spring Boot mybatis分布式微服务云架构 开发Web应用

静态资源访问 在我们开发Web应用的时候,需要引用大量的js、css、图片等静态资源。 默认配置 Spring Boot默认提供静态资源目录位置需置于classpath下,目录名需符合如下规则: /static /pub...

itcloud ⋅ 21分钟前 ⋅ 0

6月19日任务 设置更改root密码、连接mysql、mysql常用命令

13.1 设置更改root密码 1. /usr/local/mysql/bin/mysql -uroot 设置环境变量 : export PATH=$PATH:/usr/local/mysql/bin/ 永久生效: vim /etc/profile 加入 export PATH=$PATH:/usr/local/m......

吕湘颖 ⋅ 22分钟前 ⋅ 0

MaxCompute读取分析OSS非结构化数据的实践经验总结

摘要: 本文背景 很多行业的信息系统中,例如金融行业的信息系统,相当多的数据交互工作是通过传统的文本文件进行交互的。此外,很多系统的业务日志和系统日志由于各种原因并没有进入ELK之类...

猫耳m ⋅ 23分钟前 ⋅ 0

Spring MVC controller,return重定向redirect:

@RequestMapping(value="/save",method=RequestMethod.POST)public String doSave(Course course) {log.debug("Info of Course");log.debug(ReflectionToStringBuilder.toStr......

颖伙虫 ⋅ 31分钟前 ⋅ 0

JavaSE——线程介绍

声明:本栏目所使用的素材都是凯哥学堂VIP学员所写,学员有权匿名,对文章有最终解释权;凯哥学堂旨在促进VIP学员互相学习的基础上公开笔记。 线程: 介绍:管线程叫多任务处理,首先你得知道...

凯哥学堂 ⋅ 35分钟前 ⋅ 0

ORM——使用spring jpa data实现逻辑删除

前言 在业务中是忌讳物理删除数据的,数据的这个对于一个IT公司可以说是最核心的资产,如果删除直接就物理删除,无疑是对核心资产的不重视,可能扯的比较远,本文最主要是想通过spring jpa ...

alexzhu592 ⋅ 41分钟前 ⋅ 0

CDN caching

Incapsula应用感知CDN使用智能分析和频率分析来动态缓存内容,并最大限度地提高效率。确保可直接从RAM获取最常访问的资源,而不依赖于较慢的访问机制。 1、 静态内容缓存 Incapsula缓存静态内...

上树的熊 ⋅ 44分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部