文档章节

算法——快速排序

高乐钏
 高乐钏
发布于 2018/03/04 22:28
字数 1194
阅读 33
收藏 1

快速排序可能是应用最广泛的排序算法了。原因是它实现简单,适用于各种不同的输入数据且在一般应用中比其他排序算法都要快得多。

特点:①它是原地排序(只需要一个很小的辅助栈);②且将长度为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);//将右半部分排序
	}
}

快速排序的划分

	public static int partition(Comparable [] a,int lo,int hi) {
		//将数组切分
		int i=lo,j=hi+1;//设置左右扫描指针
		Comparable v=a[lo];//将数组第一个数a[lo]设置为切分元素v
		while(true) {
			//扫描左右,检查扫描是否结束并交换元素
			while(less(a[++i],v))if(i==hi)break;//左侧从第二个数开始遍历,直到找到大于切分元素的值
			while(less(v,a[--j]))if(j==lo)break;//右侧从最后一个元素开始遍历,直到找到小于切分元素的值
			if(i>=j)break;
			each(a,i,j);//交换i和j指向的元素
		}
		each(a,lo,j);//将a[lo]和j最后指向的元素交换位置,已知j指向的元素都是小于切分元素,即a[lo]的。
		return j;//达成a[lo...j-1]<=a[j]<=a[j+1..hi]
	}

分析:将数组第一个值设为切分元素,用i指针从左向右扫描,j指针从右往左扫描。当i扫描到大于切分元素的值,停止移动并指向它;当j扫描到小于切分元素的值,停止移动并指向它。交换i和j指向的元素。当i>=j或者i、j越界时停止,最后交换切分元素和j指针指向的元素,真正实现,切分元素左侧比它小,右侧比它大。

注意:①别越界:如果切分元素是数组中最小或者最大的那个元素,我们就要防止指针跑出数组边界。可以通过哨兵改进。

            ②保持随机性:切分元素的选择对算法性能影响很大,保持随机性可以尽量大的可能性选择合适切分元素。

            ③终止循环:一个常见错误是没有考虑到数组中可能包含和切分元素的值相同的其他元素。

            ④处理切分元素值有重复的情况:左侧扫描改为小于等于,右侧扫描改为大于等于。尽管这样可能会不必要的将一些等值的元素交换,但是他能够避免算法运行时间变为平方级别。

性能:快速排序切分方法的内循环会用一个递增的索引将数组元素和一个定值比较。这种简洁性也是快速排序的一个优点。例如,归并排序和希尔排序一般都比快速排序慢,就是因为他们还在内循环中移动数据。

将长度为N的无重复数组排序,快速排序平均需要2NlnN次比较(以及1/6的交换)。

快速排序最多需要约N²/2次比较,但随即打乱数组能够预防这种情况。

算法改进

①切换到插入排序:改进使遇到小数组时使用插入排序,将if(hi<=lo)return;替换成if(hi<=lo+M){Insertion,sort(a,lo,hi);return;}。转换参数的最佳值适合系统相关的,但是5~15之间的任意值在大多数情况下都能够令人满意。

②三取样切分

③熵最优的排序:三向切分的快速排序。我们已经知道归并排序是最优的,如何突破他的下界?这个问题的答案讨论的是对于任意输入的最差性能,而我们目前在讨论时已经知道输入数组的一些信息了。对于含有以任意概率分布的重复元素的输入,归并排序无法保证最佳性能。

© 著作权归作者所有

高乐钏
粉丝 11
博文 86
码字总数 73259
作品 0
南京
程序员
私信 提问
线程基础:多任务处理(16)——Fork/Join框架(排序算法性能补充)

1、概述 在之前的一篇文章《线程基础:多任务处理(13)——Fork/Join框架(解决排序问题)》中,我们使用了fork/join框架提高归并排序的性 能。那篇文章发布后,有的读者联系我,觉得单就归...

yinwenjie
2017/06/06
0
0
各种基本算法实现小结(六)—— 查找算法

各种基本算法实现小结(六)—— 查找算法 (均已测试通过) =================================================================== 1、简单查找 在一组无序数列中,查找特定某个数值,并返...

长平狐
2013/01/06
126
0
算法-排序算法思想及实现

摘自我自己的博客园:www.cnblogs.com/myadmin/p/5… 中的部分排序算法。 插入排序 基本思想:每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置,直到全部插入完毕。 核心代...

glmapper
2017/11/28
0
0
排序——快速排序法

一、快速排序法概念 快速排序(Quick Sort)法是对冒泡排序的一种改进,其基本思想是:通过一遍排序将需要排序的数据划分成两部分,使其中一部分数据比另一部分数据小,然后再分别对这两部分...

翼动动空
2016/06/06
1K
0
我最喜欢的排序算法——快速排序和归并排序

申明:此博文转自他人,感觉不错特转载供大家分享 摘要:一般评判排序算法的标准有时间代价,空间代价和稳定性。本文主要讨论性质相对比较好且作者喜欢的快速排序算法和归并排序算法,并对此这...

mjrao
2012/03/23
3.6K
0

没有更多内容

加载失败,请刷新页面

加载更多

kubernetes pod exec接口调用

正文 一般生产环境上由于网络安全策略,大多数端口是不能为集群外部访问的。多个集群之间一般都是通过k8s的ApiServer组件提供的接口通信,如https://192.168.1.101:6443。所以在做云平台时,...

码农实战
44分钟前
6
0
3_数组

3_数组

行者终成事
今天
8
0
经典系统设计面试题解析:如何设计TinyURL(二)

原文链接:https://www.educative.io/courses/grokking-the-system-design-interview/m2ygV4E81AR 编者注:本文以一道经典的系统设计面试题:《如何设计TinyURL》的参考答案和解析为例,帮助...

APEMESH
今天
7
0
使用logstash同步MySQL数据到ES

概述   在生成业务常有将MySQL数据同步到ES的需求,如果需要很高的定制化,往往需要开发同步程序用于处理数据。但没有特殊业务需求,官方提供的logstash就很有优势了。   在使用logstas...

zxiaofan666
今天
10
0
X-MSG-IM-分布式信令跟踪能力

经过一周多的鏖战, X-MSG-IM的分布式信令跟踪能力已基本具备, 特点是: 实时. 只有要RX/TX就会实时产生信令跟踪事件, 先入kafka, 再入influxdb待查. 同时提供实时sub/pub接口. 完备. 可以完整...

dev5
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部