文档章节

快速排序详解 Java实现

小车车
 小车车
发布于 2016/09/03 10:16
字数 632
阅读 57
收藏 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;
	}
}

 

 

© 著作权归作者所有

共有 人打赏支持
小车车
粉丝 4
博文 82
码字总数 72325
作品 0
深圳
程序员
JAVA中运用数组的四种排序方法

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

IceRainYWC
2014/03/17
0
0
JAVA中运用数组的四种排序方法

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

闫三
2012/05/08
0
0
Android--面试中遇到的问题总结(三)

《Android 开发工程师面试指南 LearningNotes 》,作者是陶程,由梁观全贡献部分。大家可以去知乎关注这两位用心的少年。这份指南包含了大部分Android开发的基础、进阶知识,不仅可以帮助准备...

sealin
2017/02/22
0
0
大数据开发培训:0基础学习Java编程语言有哪些知识点?

Java 技术通用、高效、具有平台移植性和安全性,广泛应用于PC、数据中心、游戏控制台、科学超级计算机、移动电话和互联网等,学习Java首先要知道学习知识点有哪些。在这就用加米谷大数据培训...

加米谷大数据
07/25
0
0
一份关于 Java、Kotlin 与 Android 的学习笔记

JavaKotlinAndroidLearn 这是一份关于 Java 、Kotlin 、Android 的学习笔记,既包含对基础知识点的介绍,也包含对一些重要知识点的源码解析,笔记的大纲如下所示: Java 重拾Java(0)-基础知...

叶应是叶
08/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Bash工作管理详解

Bash工作管理 Bash的工作是对具体任务的一个抽象表述,更确切的说是对管道的应用上的表述。Bash中的工作在形式上表现为一组相关进程或单个进程。工作进程组分为前台和后台,前台进程会对键盘...

小陶小陶
14分钟前
2
0
Qt那些事0.0.1

LIBS += -L$$PWD/lib/ -lStv1QMAKE_POST_LINK += $$QMAKE_COPY $$replace(PWD,"/","\\")\lib\Stv1.dll $$replace(OUT_PWD,"/","\\")\debug\Stv1.dll pro文件里,写起来按理说应该是轻松地......

Ev4n
23分钟前
2
0
如何正确的使用动态VPS(Linux)自动更换IP

背景 现在越来越多的人开始玩网赚项目,蚂蚁再小也是肉,薅羊毛的羊毛党越来越多,一些网赚项目也越来越受欢迎,但是一般的网赚项目都是要求真实用户的,所以要想获得大量的真实ip,一种动态...

bengozhong
30分钟前
1
0
分布式任务系统(LTS)部署学习使用

章节速览 背景介绍 环境部署 LTS架构原理&代码样例 个人心得经验 一、背景介绍 很多公司应该都会遇到job服务部署执行时:定时、并发、分布式这些问题。有的人就是只跑一个job服务,这样会简单...

硅步积千里
39分钟前
29
0
kotlin使用spring data redis(一)

1.引包 #忘记引用这个包的下场就是#nested exception is java.lang.NoClassDefFoundError: org/apache/commons/pool2/impl/GenericObjectPoolConfigcompile 'org.apache.commons:commons-p......

weidedong
42分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部