文档章节

排序算法笔记:快速排序 QuickSort in java

CheN_exe
 CheN_exe
发布于 2014/01/04 13:40
字数 281
阅读 261
收藏 0
点赞 0
评论 0
/**
 * 快速排序
 * 简述:
 * 		取array[high],将之前小于array[high]的数字置于array[high]之前,大于array[high]的置于array[high]之后,最后将array[high]放置于比它大的数字和比它小的数字之间.再利用递归重复之前的步骤至low < high为止.
 * 时间复杂度:
 * 		the best case: T(n)=T(n - 1)+Θ(n) = Θ(n^2)
 * 		the worst case: T(n)<=2T(n/2)+Θ(n)=Θ(nlgn)
 * 		average case: T(n)<=T(9n/10)+T(n/10)+cn=O(nlgn)
 * 空间复杂度:
 * 		O(logn)
 * 优点:
 * 		常见通用性较高的算法中,时间复杂度非常低的算法.推荐算法.
 * 缺点:
 * 		
 * 可改进:
 * 		
 * @author CheN
 *
 */
public class QuickSort {
	public static int[] asc(int[] array) {
		quickSort(array, 0 , array.length - 1 );
		return array;
	}
	
	private static void quickSort(int[] array, int low , int high ){
		if( low < high ){
			int middle = getMiddle( array , low , high );
			quickSort( array , low , middle - 1 );
			quickSort( array , middle + 1 , high );
		}
	}
	
	private static int getMiddle(int[] array, int low , int high ){
		int x = array[high];
		for( int j = low ; j < high ; j++ ){
			if( array[j] <= x ){
				int temp = array[low];
				array[low] = array[j];
				array[j] = temp;
				low++;
			}
		}
		int temp = array[low];
		array[low] = array[high];
		array[high] = temp;
		return low;
	}
	
}


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

© 著作权归作者所有

共有 人打赏支持
CheN_exe
粉丝 2
博文 31
码字总数 16744
作品 0
海淀
程序员
java排序之快速排序、归并排序、基数排序

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

野小疯 ⋅ 06/05 ⋅ 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

深入理解JVM学习笔记(一、总览)

1、JVM历史 2、JVM内存结构 3、JVM垃圾回收机制 4、JVM性能监控工具 5、JVM性能调优案例时间 6、JVM类文件结构 7、JVM类加载机制 8、JVM字节码执行引擎 9、JVM虚拟机编译及其运行时优化 10、...

jintaohahahaha ⋅ 05/28 ⋅ 0

JDK 11 特性抢先看:5 月新增三个 JEP

一周前(2018年5月7日),JDK11 新增了三个 JEP 。在 jdk-dev 邮件列表中出现了三封邮件,Mark Reinhold 发表了以下公告: JDK 11 实现了 JEP:324:关于 Curve25519 和 Curve448 的重要协议...

oschina ⋅ 05/16 ⋅ 0

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

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

京东一面 ⋅ 04/18 ⋅ 0

【JVM】 java内存区域与内存溢出异常

前言 此系列博客是读《深入理解java虚拟机》所做的笔记整理。 No1. JVM内存管理这堵墙? 对C和C++的开发人员来说,在内存管理领域,他们既拥有每一个对象的“所有权”,也担负着每一个对象生...

binggetong ⋅ 05/07 ⋅ 0

继 Java 版权案之后,甲骨文公司开始向 JavaScript 伸手!

就在 JavaScript 成为 GitHub 网站最为流行、越来越受到广大开发者热衷的编程语言之际,国外网站 reddit 的一篇求助性帖子引发行业内的热议。 帖子大意就是,该作者收到苹果公司的一封邮件,...

亦枫 ⋅ 04/19 ⋅ 0

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

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

xpleaf ⋅ 04/18 ⋅ 0

ZooKeeper学习笔记八 ZooKeeper典型应用场景——命名服务

《从Paxos到ZooKeeper分布式一致性原理与实践》 电子工业出版社 命名服务是分布式系统中比较常见的一类场景。命名服务是分布式系统最基本的公共服务之一。在分布式系统中,被命名的实体通常可...

xundh ⋅ 05/02 ⋅ 0

Kotlin学习笔记(三) 条件.循环

1.if条件判断 (1)直接赋值: 与java不同的是,kotlin的if条件判断后的结果可以直接赋值给一个变量,如下: (2)区间: 2.when 在kotlin中,when的用法与java中的switch...case的效果相同; 3.for循环...

JackyRiver ⋅ 05/31 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Boost库编译应用

版本:Boost 1.66.0 Windows库编译 官网指南:直接执行bootstrap.bat处理文件即可,可以我却遇到一堆的问题。 环境:Windows 10 + Visual Studio 2017 Boost编译出来库命名 boost库生成文件命...

水海云 ⋅ 27分钟前 ⋅ 0

解决Eclipse发布到Tomcat丢失依赖jar包的问题

如果jar文件是以外部依赖的形式导入的。Eclipse将web项目发布到Tomcat时,是不会自动发布这些依赖的。 可以通过Eclipse在项目上右击 - Propertics - Deployment Assembly,添加“Java Build ...

ArlenXu ⋅ 27分钟前 ⋅ 0

iview tree组件层级过多时可左右滚动

使用vue+iview的tree组件,iview官网iview的tree树形控件 问题描述:tree层级过多时左右不可滚动 问题解决:修改overflow属性值 .el-tree-node>.el-tree-node_children { overflow: vi...

YXMBetter ⋅ 29分钟前 ⋅ 0

分布式锁

1.通过数据库实现 http://www.weizijun.cn/2016/03/17/%E8%81%8A%E4%B8%80%E8%81%8A%E5%88%86%E5%B8%83%E5%BC%8F%E9%94%81%E7%9A%84%E8%AE%BE%E8%AE%A1/ 2.ZK实现:curator-recipes分布式锁的......

素雷 ⋅ 37分钟前 ⋅ 0

Sublime Text3 快捷键

选择类 Ctrl+D 选中光标所占的文本,继续操作则会选中下一个相同的文本。 Alt+F3 选中文本按下快捷键,即可一次性选择全部的相同文本进行同时编辑。举个栗子:快速选中并更改所有相同的变量名...

AndyZhouX ⋅ 44分钟前 ⋅ 0

XamarinAndroid组件教程RecylerView自定义适配器动画

XamarinAndroid组件教程RecylerView自定义适配器动画 如果RecyclerViewAnimators.Adapters命名空间中没有所需要的适配器动画,开发者可以自定义动画。此时,需要让自定义的动画继承Animation...

大学霸 ⋅ 44分钟前 ⋅ 0

eureka 基础(二)

使用Eureka服务器进行身份验证 如果其中一个eureka.client.serviceUrl.defaultZone网址中包含一个凭据(如http://user:password@localhost:8761/eureka)),HTTP基本身份验证将自动添加到您...

明理萝 ⋅ 47分钟前 ⋅ 1

Kubernetes(五) - Service

Kubernetes解决的另外一个痛点就是服务发现,服务发现机制和容器开放访问都是通过Service来实现的,把Deployment和Service关联起来只需要Label标签相同就可以关联起来形成负载均衡,基于kuberne...

喵了_个咪 ⋅ 47分钟前 ⋅ 0

更新队友POM文件后报错

打开报错的地方的pom及其引用方法所在文件的pom,观察其版本号是否一致,不一致进行更改

森火 ⋅ 今天 ⋅ 0

IDEA使用sonarLint

一、IDEA如何安装SonarLint插件 1.打开 Idea 2.点击【File】 3.点击【Settings】 4.点击【Plugins】 5.在搜索栏中输入“sonarlint”关键字 6.点击【Install】进行安装 7.重启Idea 二、IDEA如...

开源中国成都区源花 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部