文档章节

快速排序详解 Java实现

小车车
 小车车
发布于 2016/09/03 10:16
字数 632
阅读 58
收藏 2

一、快速排序的优缺点

        对一个东西,首先要讲他的利与弊,才知道怎么使用它。快速排序适用于各种不同的输入数据且在一般应用中比其他排序都要快得多。快速排序引人注目的特点包括它是原地排序(只需要一个很小的辅助栈),且长度为N的数组排序所需的时间和NlgN成正比。它的主要缺点是非常脆弱,在实现时要非常小心才能避免低劣的性能。

        有了对比,才能知道它的好处。其实快速排序是一种分治的排序算法。它将一个数组分成两个子数组,将两部分独立地排序。讲到这里,有人就会有个疑问,那不是和归并排序一样吗?合并排序也是分治算法的一种,也是将一个数组分成两个子数组。快速排序和归并排序时互补的:归并排序将数组分成两个子数组分别排序,并将有序的子数组归并以整个数组排序;而快速排序将数组排序的方式则是当两个数组都有序时整个数组也就自然有序了。在第一种情况下,递归调用发生在处理整个数组之前;在第二种情况下,递归调用发生在处理整个数组之后。在归并排序中,一个数组被等分为两半;在快速排序中,切分的位置取决于数组的内容。这句话最重要。

二、快速排序的实现

public class Quick{
	public static void sort(Comparable[] a){
		StdRandom.shuffle(a);//消除对输入的依赖,直接生成随机数
		
		sort(a,0,a.length-1);
		
	}
	private static void sort(Comparable[] a, int lo, int hi){
		if(hi <= lo) return;
		int j= partition(a,lo,hi);//切分
		sort(a,lo,j-1);
		sort(a,j+1,hi);
	}
	private static int partition(Comparable[] a, int lo ,int hi){
		int i = io,j=hi+1;
		Comparable v = a[lo];
		while(true){
			while(less(a[++i],v)) if(i==hi) break;
			while(less(v,a[--j])) if(j==lo) break;
			if(i>=j) break;
			exch(a,i,j)
		}
		exch(a,lo,j);
		return j;
	}
	
	private static void exch(Comparable[] a ,int i ,int j){
		Comparable t = a[i];a[i]=a[j];a[j]=t;
	}
	private static boolean less(Comparable v , Comparable w){
		return v.compareTo(w)<0;
	}
}

 

 

© 著作权归作者所有

共有 人打赏支持
小车车
粉丝 5
博文 85
码字总数 77384
作品 0
深圳
程序员
私信 提问
《数据结构与算法系列》合集整理

《数据结构与算法系列》合集整理 整理来自博客园skywang12345,以下摘自作者介绍: “最近抽空整理了"数据结构和算法"的相关文章。在整理过程中,对于每种数据结构和算法分别给出"C"、"C++"...

kaixin_code
2018/12/01
0
0
JAVA中运用数组的四种排序方法

JAVA中在运用数组进行排序功能时,一般有四种方法:快速排序法、冒泡法、选择排序法、插入排序法。 快速排序法主要是运用了Arrays中的一个方法Arrays.sort()实现。 冒泡法是运用遍历数组进...

IceRainYWC
2014/03/17
0
0
Java程序员进化为架构师需要掌握的知识

Java程序员进化为架构师掌握的知识: 一:Java知识 1、进制转换 2、Java基本数据类型 面向对象相关知识 3、类、接口、抽象类 this关键字、static关键字、final关键字 方法的参数传递机制 Ja...

andogo
2014/05/16
1K
2
JAVA中运用数组的四种排序方法

JAVA中在运用数组进行排序功能时,一般有四种方法:快速排序法、冒泡法、选择排序法、插入排序法。 快速排序法主要是运用了Arrays中的一个方法Arrays.sort()实现。 冒泡法是运用遍历数组进...

闫三
2012/05/08
0
0
Java程序员从笨鸟到菜鸟全部博客目录【2012年十一月七日更新】

本文来自:曹胜欢博客专栏。转载请注明出处:http://blog.csdn.net/csh624366188 大学上了一年半,接触java也一年半了,虽然中间也有其他东西的学习,但是还是以java为主路线,想想这一年半,...

长平狐
2012/11/12
103
0

没有更多内容

加载失败,请刷新页面

加载更多

nginx日志自动切割

1.日志配置(Nginx 日志) access.log----记录哪些用户,哪些页面以及用户浏览器,IP等访问信息;error.log------记录服务器错误的日志 #配置日志存储路径:location / {      a...

em_aaron
昨天
0
0
java 反射

基本概念 RTTI,即Run-Time Type Identification,运行时类型识别。RTTI能在运行时就能够自动识别每个编译时已知的类型。   要想理解反射的原理,首先要了解什么是类型信息。Java让我们在运...

细节探索者
昨天
1
0
推荐转载连接

https://www.cnblogs.com/ysocean/p/7409779.html#_label0

小橙子的曼曼
昨天
3
0
雷军亲自打造的套餐了解下:用多少付多少

12月28日消息,小米科技创始人兼CEO雷军微博表示,小米移动任我行套餐方案,原则上就是明明白白消费,用多少付多少,不用不花钱!上网、电话和短信都是一毛钱,上网0.1元/M,电话0.1元/分钟,...

linuxCool
昨天
6
0
协议简史:如何学习网络协议?

大学时,学到网络协议的7层模型时,老师教了大家一个顺口溜:物数网传会表应。并说这是重点,年年必考,5分的题目摆在这里,你们爱背不背。 考试的时候,果然遇到这个问题,搜索枯肠,只能想...

Java干货分享
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部