快速排序 | 算法必看系列十二-阿里云开发者社区

开发者社区> 被纵养的懒猫> 正文

快速排序 | 算法必看系列十二

简介: 快速排序的思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序的目的。
+关注继续查看

原文链接

快速排序属性

image.png

上一篇文章介绍了 冒泡排序和它的优化 。这次介绍的快速排序是冒泡排序演变而来的算法,比冒泡排序要高效的很多。

快速排序之所以快,是因为它使用了分治法。它虽然也是通过不断的比较和移动来实现排序的,只不过它的实现,增大了比较的距离和移动的距离。而冒泡排序只是相邻的比较和交换。

快速排序的思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序的目的。

从字面上感觉不到它的好处,我们通过一个示例来理解基本的快速排序算法,假设当前数组元素是:5, 1, 9, 3, 7, 4, 8, 6, 2。

基本的快速排序算法

初始状态:5, 1, 9, 3, 7, 4, 8, 6, 2

选择5作为一个基准元素,然后从右向左移动hight下标,进行基准元素和下标为hight的元素进行比较。

如果基准元素要大,则进行hight的左移一位;如果基准元素要小,则进行元素的交换。

在hight下标左移的过程中,我们目的是找出比基准元素小的,然后进行交换。

交换完之后,进行left的右移,找出比基准元素大的,找到则进行交换。

视频动画

Code

image.png

Result

image.png

优化枢轴的选取

举一个恰当的例子,假设数组元素是9,8,7,6,5,4,3,2,1。

进行hight左移的时候第一个就发生了交换,1,8,7,6,5,4,3,2,9。嗯看似效率蛮快,但是进行low右移的时候一个个做了不必要的计算,没有一个元素比枢轴值要大。和冒泡排序一样,这一趟进行了8次比较,时间复杂度达到最坏程度O(n^2)。和快排的O(nlongn)相悖。

那拿什么更好的方式选取枢轴值呢?

我看到网上都说是,随机选取一个数作为基准元素。嗯看似一个好的方法,但是和上面大概率出现的最坏情况还是有可能发生的。每次选取枢轴值都有可能是最大的或者最小的。如果是庞大的数据量第一个随机选到了最大的数,程序卡的半死不活的,只有kill掉再重新运行吗?

改进情况,取三数之中的中间数的一个数。什么意思呢?

就是在一组数中取三个关键数字,将中间数作为枢轴,一般可以取左端,右端和中间三个数,也可以随机选取。那你可能说了,要是三个数都是最小的或者都是最大的那什么办呢?

没错,这样选取还是会带来时间上的开销,并不证明选取到一个好的枢轴值。那要是取九数之中的中间数呢?

这当然不是采用随机取九个数然后再排序排一半取中间数那一个。

它是从数组中分三次取样,每次取三个数,三个样品中各取出中间数,然后在这三个中枢当中再取一个中间数作为枢轴。如果一次极端就算了,但是分三次取样还会碰到三次极端那显然是微乎其微的。这样的方法增加选到好的枢轴的概率。

优化不必要的交换

回到基本的快速排序算法,回顾上面的视频动画。我们可以发现,这其中发生了不必要的移动方式。

我们最终要求一趟选的枢轴值,大的数在它的右边,小的数在它左边。但是这个枢轴值每次符合条件去了不该去的地方。我认为它前面的地方不要动,等一趟完了就去自己该去的地方,减少时间上的消耗。

视频动画

Code

image.png

Result

image.png

优化递归操作

我们都知道,递归对性能是有一定影响的,quickSort函数尾部有两次递归操作。如果待排序的序列极为极端不平衡,递归的深度几乎接近于n的高度(没有了二分法的优势)。这样的时间复杂度也是达到了最坏的程度O(n^2),而不是平衡时的O(nlogn)。

时间慢也就算了,但是栈的大小也是有限的,每次递归操作都消耗一定的栈空间,函数的参数越多,每次递归调用参数耗费的空间也是越多。

如果能减少递归,性能也因此大大提高。

那拿什么方式优化递归操作呢?

来看下面代码。

Code

image.png

Result

image.png

执行结果之后和前面两个结果无异。这是一个很好的方法。我们把if改成while,然后一次递归之后,low已经没有用处了,所以把pivot+1赋值给low作为下一个参数。结果你也看到了,结果都相同。

因此采用迭代而不是递归的方法可以缩减堆栈深度,从而提高了整体性能。

-----End-----

来源 | 算法无遗策
作者 | 我脱下短袖

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
java 算法基础之二快速排序算法
java 算法基础之二快速排序算法
1859 0
排序算法(七):快速排序
快速排序是通过分治的方式,根据选定元素将待排序集合拆分为两个值域的子集合,并对子集合递归拆分,当拆分后的每个子集合中元素个数为一时,自然就是有序状态。
697 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
4479 0
算法笔记--基数排序
基数排序是一种数据格式相关的算法,适用范围有限,当数据位数较小时,基数排序法的时间复杂度近似为O(n),效率高于其它的稳定性排序算法。 1. 算法思想           以十进制数为例,现将元素按个位出入一次基数桶,再按十位出入基数桶……直至按最高位出入基数桶,此时序列整体有序。
652 0
【算法导论】快速排序
快速排序         快速排序的最坏运行时间为O(n2),虽然这最坏情况的时间复杂度比较大,但快速排序通常是用于排序的最佳实用选择,这是因为其平均性能相当好,平均时间复杂度为O(nlogn),并且O(nlogn)中的隐含常数因子很小。
797 0
【算法导论】基数排序
基数排序 时间复杂度:O(n). 基本思路:两个数比较大小,我们的直观感觉是先比较高位,若相同则比较低位。但是这样做需要记录额外的数据,浪费空间。
782 0
算法研究之快速排序
所谓的快速排序的思想就是,首先把数组的第一个数拿出来做为一个key,在前后分别设置一个i,j做为标识,然后拿这个key对这个数组从后面往前遍历,及j--,直到找到第一个小于这个key的那个数,然后交换这两个值,交换完成后,我们拿着这个key要从i往后遍历了,及i++;一直循环到i=j结束,当这里结束后,我们会发现大于这个key的值都会跑到这个key的后面,不是的话就可能你写错了,小于这个key的就会跑到这个值的前面;然后我们对这个分段的数组再时行递归调用就可以完成整个数组的排序。
454 0
560
文章
1795
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载