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

枢纽元选择也有学问
服务器君一共花费了322.824 ms进行了5次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

选择首尾元素做枢纽元

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

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

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

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

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

随机选取枢纽元

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

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

三数中分割法

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

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

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

快速排序还很有很多各种变种,我们这里只研究几个有代表性的算法。

延伸阅读

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

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

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

不打个分吗?

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

http://www.nowamagic.net/librarys/veda/detail/2397

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

大家都在看

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

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

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

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

《大话设计模式》 程杰 (作者)

《大话设计模式》通篇都是以情景对话的形式,用多个小故事或编程示例来组织讲解GoF(设计模式的经典名著——Design Patterns: Elements of Reusable Object-Oriented Software,中译本名为《设计模式——可复用面向对象软件的基础》的四位作者Erich Gamma、Richard Helm、Ralph Johnson,以及JohnVlissides,这四人常被称为GangofFour,即四人组,简称GoF)总结的23个设计模式。本书共分为29章。其中,第1、3、4、5章着重讲解了面向对象的意义、好处以及几个重要的设计原则;第2章,以及第6到第28章详细讲解了23个设计模式;第29章是对设计模式的全面总结。

更多计算机宝库...