文档章节

【算法】5 传说中的快排是怎样的

NoMasp
 NoMasp
发布于 2015/09/08 21:51
字数 2577
阅读 3
收藏 0

什么是快速排序

快速排序简介

快速排序(英文名:Quicksort,有时候也叫做划分交换排序)是一个高效的排序算法,由Tony Hoare在1959年发明(1961年公布)。当情况良好时,它可以比主要竞争对手的归并排序和堆排序快上大约两三倍。这是一个分治算法,而且它就在原地排序。

所谓原地排序,就是指在原来的数据区域内进行重排,就像插入排序一般。而归并排序就不一样,它需要额外的空间来进行归并排序操作。为了在线性时间与空间内归并,它不能在线性时间内实现就地排序,原地排序对它来说并不足够。而快速排序的优点就在于它是原地的,也就是说,它很节省内存。

引用一张来自维基百科的能够非常清晰表示快速排序的示意图如下:

这里写图片描述

快速排序的分治思想

由于快速排序采用了分治算法,所以:

一、分解:本质上快速排序把数据划分成几份,所以快速排序通过选取一个关键数据,再根据它的大小,把原数组分成两个子数组:第一个数组里的数都比这个主元数据小或等于,而另一个数组里的数都比这个主元数据要大或等于。

这里写图片描述

二、解决:用递归来处理两个子数组的排序。 (也就是说,递归地求上面图示中左半部分,以及递归地求上面图示中右半部分。)

三、合并:因为子数组都是原址排序,所以不需要合并操作,通过上面两步后数组已经排好序了。

所以快速排序的主要思想是递归与划分。

如何划分

当然最重要的是它的复杂度是线性的,也就是 Θ(n) 个划分的子程序。

Partition(A,p,q)   // A[p,..q] 
1   x=A[p]   // pivot=A[p] 主元 
2   i=p 
3   for j=p+1 to q
4       do if A[j]<=x
5          then i=i+1 
6             exch A[i]<->A[j] 
7   exch A[p]<->A[i] 
8   return i // i pivot 

这就是划分的伪代码,基本的结构就是一个for循环语句,中间加上了一个if条件语句,它实现了对子数组 A[p...q] 的原址排序。

这里写图片描述

刚开始时 i 等于 p j 等于 p+1 。在这个循环中查找i下标的数据,如果它比 x 大,那就将其存放到“>=x”区域并将 j 加1后进行下一次循环。而如果它比 x 小,那就要做些动作来维持循环不变量了。将 i 的下标加1后将下标i对应的数据和下标j所对应的数据互换位置。然后再移动区域的界限并开始下一次循环。

那么这个算法在n个数据下的运行时间大约是 O(n) ,因为它几乎把每个数都比较了一遍,而每个步骤所需的时间都为 O(1)

这里写图片描述

上面这幅图详细的描述了Partition过程,每一行后也加了注释。

将递归的思想作用于划分上

有了上面这些准备工作,再加上分治的思想实现快速排序的伪代码也是很简单的。

Quicksort(A,p,q) 
1   if p<q 
2     then r=Partition(A,p,q)   
3          Quicksort(A,p,r-1) 
4          Quicksort(A,r+1,q) 

为了排序一个数组A的全部元素,初始调用时 Quicksort(A,1,A.length)

快速排序的算法分析

相信通过前面的诸多实践,大家也发现了快速排序的运行时间依赖于Partition过程,也就是依赖于划分是否平衡,而归根结底这还是由于输入的元素决定的。

如果划分是平衡的,那么快速排序算法性能就和归并排序一样。

如果划分是不平衡的,那么快速排序的性能就接近于插入排序。

怎样是最坏的划分

1)输入的元素已经排序或逆向排序
2)每个划分的一边都没有元素

也就是说当划分产生的两个子问题分别包含了n-1个元素和0个元素时,快速排序的最坏情况就发生了。

T(n)=T(0)+T(n1)+ \Theta(n) =Θ(1)+T(n1)+Θ(n)=Θ(n1)+Θ(n)=Θ(n2)

这是一个等差级数,就和插入排序一样。它并不比插入排序快,因为当同样是输入元素已经逆向排好序时,插入算法的运行时间为 Θ(n) 。但快速排序仍旧是一个优秀的算法,这是因为在平均情况下它已经很高效。

我们为最坏情况画一个递归树。

这里写图片描述

这是一课高度不平衡的递归树,图中左边的那些 T(0) 的运行时间都为 Θ(1) ,而总共有n个。

所以算法的中运行时间为:

T(n)=Θ(n)+Θ(n2)=Θ(n2)

最坏划分的算法分析

通过上面的图示我们知道了在最坏情况下快速排序的复杂度是 Θ(n2) ,但以图示的方式并不是一种严谨的证明方式,我们应该使用代入法来证明它。

当输入规模为n时,时间 T(n) 有如下递归式:

T(n)=max0rn1(T(r)+T(nr1))+Θ(n)

除去主元后,在Partition函数中生成的两个子问题的规模的和为n-1,所以r的规模才是0到n-1。

假设 T(n)cn2 成立,其中c为常数这个大家都知道的。于是上面的递归式为:

T(n)max0rn1(cr2+c(nr1)2)+Θ(n)cmax0rn1(r2+(nr1)2)+Θ(n)

1)而 r2+(nr1)2 对于r的二阶导数为正,所以在区间 0rn1 的右端点取得最大值。

于是有 max0rn1(r2+(nr1)2)(n1)2=n22n+1 ,所以对于 T(n) 有:

T(n)cn2c(2n1)+Θ(n)

最终因为我们可以选择一个足够大的 c ,来使得 c(2n1) 大于 Θ(n) ,所以有 T(n)=O(n2)

2) r2+(nr1)2 对于r的二阶导数为正,所以在区间 0rn1 的左端点取得最小值。

于是有 max0rn1(r2+(nr1)2)(n1)2=n22n+1 ,所以对于 T(n) 有:

T(n)cn2c(2n1)+Θ(n)

同样我们也可以选择一个足够小的 c ,来使得 c(2n1) 小于 Θ(n) ,所以有 T(n)=Ω(n2)

综上这两点得到 T(n)=Θ(n2)

怎样是最好的划分

当Partition将数组分为 n/2 n/2 两个部分时是最高效的。此时有:

T(n)=2T(n/2)+Θ(n)=Θ(nlgn)

怎样是平衡的划分

快速排序的平均运行时间更接近于其最好情况,而非最坏情况。

此处有一个经典的示例,将数组按 19 的比例进行划分会怎样呢?这种划分看似很不平衡,但真的会因此而影响效率么?

其中此时的递归式是:

T(n)=T(110n)+T(910n)+Θ(n)

这里依旧通过递归树来观察一番。

这里写图片描述

因为每次都减少十分之一,需要减多少次才能达到n呢,也恰好也是以10为底对数的定义。所以左侧的高度为 log10n 了,相应的右侧的高度为 log109n

所有那些叶子加在一起也只有 Θ(n) ,所以有:

T(n)cnlog109n+Θ(n)

其实 T(n) 的下界也渐近为 nlgn ,所以总时间为:

T(n)=Θ(nlgn)

只要划分是常数比例的,算法的运行时间总是 O(nlgn)

随机化快速排序

随机算法的思想

在前面分析快速排序的平均情况性能时,是建立在输入数据的所有排列都是等概率的条件下的,但在实际工程中往往不会总出现这种良好的情况。

【算法】3 由招聘问题看随机算法中我们介绍了随机算法,它使得对于所有的输入都有着较好的期望性能,因此随机化快速排序在有大量数据输入的情况下是一种更好的排序算法。

以下是随机化快速排序的好处:

1)其运行时间不依赖与输入序列的顺序

2)无需对输入序列的分布做任何假设

3)没有 一种特别的输入会引起最差的运行情况

4)最差的情况由随机数产生器决定

随机抽样技术

现在我们来使用一种叫做随机抽样(random sampling)的随机化技术,使用该技术就不再始终采用A[p]作为主元,而是从A[p…q]中随机选择一个元素作为主元。

为了达到这一目的,首先将 A[p] 与从 A[p...q] 中随机选出的一个元素交换。

通过对序列 p...q 的随机抽样,我们可以保证主元元素 x=A[p] 是等概率地从子数组的 qp+1 个元素中选取的。

因为主元元素是随机选择的,我们可以期望在平均情况下对输入数组的划分是比较均衡的。所以对前面的两份伪代码做如下修改:

RANDOMIZED-PARTITION(A,p,q)
1   i=RANDOM(p,q)
2   exchange A[p] with A[i]
3   return PARTITION(A,p,q)
RANDOMIZED-QUICKSORT(A,p,q)
1   if p<q
2       r=RANDOMIZED-PARTITION(A,p,q)
3       RANDOMIZED-QUICKSORT(A,p,r-1)
4       RANDOMIZED-QUICKSORT(A,r+1,q)

有了随机抽样技术后再也不用担心快速排序遇到最坏划分的情况啦,所以说随机化快速排序的期望运行时间是 O(nlgn)



感谢您的访问,希望对您有所帮助。 欢迎大家关注、收藏以及评论。


为使本文得到斧正和提问,转载请注明出处:
http://blog.csdn.net/nomasp


版权声明:本文为 NoMasp柯于旺 原创文章,未经许可严禁转载!欢迎访问我的博客:http://blog.csdn.net/nomasp

本文转载自:http://blog.csdn.net/nomasp/article/details/46314763

NoMasp
粉丝 7
博文 334
码字总数 0
作品 0
镇江
程序员
私信 提问
支持向量机(SVM)的故事是这样子的

支持向量机(SVM)是什么意思? 来源:https://www.reddit.com/r/MachineLearning/comments/15zrpp/pleaseexplainsupportvectormachinessvmlike_i/ 编辑:Gemini 什么是SVM? 首先看一下wiki.......

算法与数学之美
2017/07/21
0
0
【算法】5 传说中的快排是怎样的,附实现示例

版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/46314763 什么是快速排序 快速排序简介 快速排序(英文名:Qui...

nomasp
2015/06/02
0
0
数据结构学习(一)

数据结构与算法 1. 链表与数组。 2. 队列和栈,出栈与入栈。 3. 链表的删除、插入、反向。 4. 字符串操作。 5. Hash表的hash函数,冲突解决方法有哪些。 6. 各种排序:冒泡、选择、插入、希尔...

技术小甜
2017/11/16
0
0
双枢轴快排(JDK7快排)(译文)

双枢轴快排算法 Vladimir Yaroslavskiy iaroslavski@mail.ru 第一版:2009-02-16 最后更新:2009-09-11 译者:黑狗 Email:blackdog@gmail.com 介绍 在计算机科学中数据排序是最基础的一个问题...

黑狗
2012/08/29
602
1
排序算法之——快速排序(剖析)

对于快速排序,相信大家都有听过,这是一个被封为圣经的算法,足以体现算法的神奇的伟大。接下来本人将从算法思想、算法具体实现、不同情况下的复杂度、算法的优化和代码展示等几个方面为读者...

脑热
2018/08/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

nginx学习笔记

中间件位于客户机/ 服务器的操作系统之上,管理计算机资源和网络通讯。 是连接两个独立应用程序或独立系统的软件。 web请求通过中间件可以直接调用操作系统,也可以经过中间件把请求分发到多...

码农实战
今天
5
0
Spring Security 实战干货:玩转自定义登录

1. 前言 前面的关于 Spring Security 相关的文章只是一个预热。为了接下来更好的实战,如果你错过了请从 Spring Security 实战系列 开始。安全访问的第一步就是认证(Authentication),认证...

码农小胖哥
今天
11
0
JAVA 实现雪花算法生成唯一订单号工具类

import lombok.SneakyThrows;import lombok.extern.slf4j.Slf4j;import java.util.Calendar;/** * Default distributed primary key generator. * * <p> * Use snowflake......

huangkejie
昨天
12
0
PhotoShop 色调:RGB/CMYK 颜色模式

一·、 RGB : 三原色:红绿蓝 1.通道:通道中的红绿蓝通道分别对应的是红绿蓝三种原色(RGB)的显示范围 1.差值模式能模拟三种原色叠加之后的效果 2.添加-颜色曲线:调整图像RGB颜色----R色增强...

东方墨天
昨天
11
1
将博客搬至CSDN

将博客搬至CSDN

算法与编程之美
昨天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部