有极速快乐十分吗|极速快乐十分走势图|

快速排序里的学问:枢纽元选择与算法效率

枢纽元选择也有学问
服务器君一?#19981;?#36153;了219.176 ms进行了6?#38382;?#25454;库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

选择首尾元素做枢纽元

通常的、没有经过充分考虑的选择是将第一个或最后一个元素用作枢纽元。选择第一个元素作为枢纽元的程序例子可以参考专题的前一篇《快速排序里的学问:霍尔快排的实现》,而选择最后一个元素用作枢纽元的程序例子则可以参考《快速排序里的学问:快速排序的过程》这个算法导论里的例子。

选择最后一个元素作为枢纽元的排序过程是这样的:

如果输入是随机的,那么这是可以接受的,但是如果输入是预排序的或者是反序的,那么这样的枢纽元就产生一个劣质的分割,因为所有的元素不是被划入S1就是被划入S2。更有甚者,这种情况发生在所有的递归调用中。

?#23548;?#19978;,如果第一个元素用作枢纽元而且输入是预先排序的,那么快速排序所花费的时间将是二次的。然而,预排序的输入(或者有一大段预排序数据的输入)也是相当常见的,因此,使用第一个元素作为枢纽元的算法效率不是很高的。

另一种想法是选取前两个互异的键中的较大者作为枢纽元,但这和只选取第一个元素作为枢纽元效率也差不多。

随机选取枢纽元

一种安全的方针是随机选取枢纽元。

一般?#27492;?#36825;种策略非常安全,除非随机数生成器有问题,因为随机的枢纽元不可能总在接连不断地产生劣质的分割。另一方面,随机数的生成一般是昂贵的,根本减少不了算法其余部分的平均运行时间。

三数中分割法

一组N个数的中值是第[N/2]个最大的数。枢纽元的最好的选择是数组的中值。

可是,这很难算出来,并?#19968;?#26126;显减慢快速排序的速?#21462;?#36825;样的中值的估计可以通过随机选取三个元素并用它们的中值作为枢纽元而得到。?#29575;?#19978;,随机性并没有多大的帮助,因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为枢纽元。显然使用三数中值分割法消除了预排序输入的不好情形。

这种枢纽元选择的的快排,效率可是相当高的。

快速排序还很有很多各种变种,我们这里只研?#32771;?#20010;有代表性的算法。

延伸阅读

此文章所在专题列表如下:

  1. 快速排序里的学问:从?#29575;?#23383;开始
  2. 快速排序里的学问:再看看称球问题
  3. 快速排序里的学问:信息熵
  4. 快速排序里的学问:快速排序的过程
  5. 快速排序里的学问:霍尔与快速排序
  6. 快速排序里的学问:霍尔快排的实现
  7. 快速排序里的学问:枢纽元选择与算法效率
  8. 快速排序里的学问:随机化快排

本文地址:http://www.bavugt.tw/librarys/veda/detail/2397,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.bavugt.tw/librarys/veda/detail/2397

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不?#20302;常?#22240;为在特定领域有一个足够量的知?#35835;?足够良好的知识结构,?#20302;?#21270;以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知?#28010;?#35201;表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《代码大全(第2版)》 史蒂夫?迈克?#30340;?#23572; (Steve McConnell) (作者), 金戈 (译者)

代码大全(第2版)是著名IT畅销书作者、《IEEE Software》杂志前主编、具有20年编程与项目管理经验的Steve McConnell十余年前的经典著作的全新演绎:第2版做了全面的更新,增加了很多与?#26412;?#36827;的内容,包括对新语言、新的开发过程与方法论的讨论等?#21462;?#36825;是一本百科全书式的软件构建手册,涵盖了软件构建活动的方方面面,尤其强调提高软件质量的种?#36136;导?#26041;法。

更多计算机宝库...

有极速快乐十分吗
股票配资名片 头彩娱乐首页 实力单双中特 澳洲幸运10群 福彩中奖三同号 顶呱刮blue 乐视股票 北京赛车自动挂机软件 西甲皇马对巴萨 彩都会彩票苹果