[节选]
http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/
1,排序的本质可以这样来表述:一组未排序的N个数字,它们一共有N!种重排,其中只有一种排列是满足题意的(譬如从大到小排列)。
换句话说,排序问题的可能性一共有N!种。任何基于比较的排序的基本操作单元都是“比较a和b”,这就相当于猜数字游戏里面的一个问句,显然这个问句的答案只能是“是”或“否”,一个只有两种输出的问题最多只能将可能性空间切成两半,根据上面的思路,最佳切法就是切成1/2和1/2。
也就是说,我们希望在比较了a和b的大小关系之后,如果发现a<b的话剩下的排列可能性就变成N!/2,如果发现a>b也是剩下N!/2种可能性。由于假设每种排列的概率是均等的,所以这也就意味着支持a<b的排列一共有N!/2个,支持a>b的也是N!/2个,换言之,a<b的概率等于a>b的概率。
一个直接的推论是,
如果每次都像上面这样的完美比较,那么N个元素的N!种可能排列只需要log_2{N!}就排查玩了,而log_2{N!}近似于NlogN。这正是快排的复杂度。
2,为什么堆排比快排慢
回顾一下堆排的过程:
(1). 建立最大堆(堆顶的元素大于其两个儿子,两个儿子又分别大于它们各自下属的两个儿子… 以此类推)
(2). 将堆顶的元素和最后一个元素对调(相当于将堆顶元素(最大值)拿走,然后将堆底的那个元素补上它的空缺),然后让那最后一个元素从顶上往下滑到恰当的位置(重新使堆最大化)。
(3). 重复第2步。
这里的关键问题就在于第2步,堆底的元素肯定很小,将它拿到堆顶和原本属于最大元素的两个子节点比较,它比它们大的可能性是微乎其微的。实际上它肯定小于其中的一个儿子。而大于另一个儿子的可能性非常小。于是,
这一次比较的结果就是概率不均等的,根据前面的分析,概率不均等的比较是不明智的,因为它并不能保证在糟糕情况下也能将问题的可能性削减到原本的1/2。可以想像一种极端情况,如果a肯定小于b,那么比较a和b就会什么信息也得不到——原本剩下多少可能性还是剩下多少可能性。
在堆排里面有大量这种近乎无效的比较,因为被拿到堆顶的那个元素几乎肯定是很小的,而靠近堆顶的元素又几乎肯定是很大的,将一个很小的数和一个很大的数比较,结果几乎肯定是“小于”的,这就意味着问题的可能性只被排除掉了很小一部分。
这就是为什么堆排比较慢(堆排虽然和快排一样复杂度都是O(NlogN)但堆排复杂度的常系数更大)。
MacKay也提供了一个修改版的堆排:每次不是将堆底的元素拿到上面去,而是直接比较堆顶(最大)元素的两个儿子,即选出次大的元素。由于这两个儿子之间的大小关系是很不确定的,两者都很大,说不好哪个更大哪个更小,所以这次比较的两个结果就是概率均等的了。具体参考
这里。
3.为什么快排其实也不是那么快
我们考虑快排的过程:随机选择一个元素做“轴元素”,将所有大于轴元素的移到左边,其余移到右边。根据这个过程,快排的第一次比较就是将一个元素和轴元素比较,这个时候显而易见的是,“大于”和“小于”的可能性各占一半。这是一次漂亮的比较。
然而,快排的第二次比较就不那么高明了:我们不妨令轴元素为pivot,第一次比较结果是a1<pivot,那么可以证明第二次比较a2也小于pivot的可能性是2/3
这容易证明:如果a2>pivot的话,那么a1,a2,pivot这三个元素之间的关系就完全确定了—— a1<pivot<a2,剩下来的元素排列的可能性我们不妨记为P(不需要具体算出来)。而如果a2<pivot呢?那么a1和a2的关系就仍然是不确定的,也就是说,这个分支里面含有两种情况:a1<a2<pivot,以及a2<a1<pivot。对于其中任一种情况,剩下的元素排列的可能性都是P,于是这个分支里面剩下的排列可能性就是2P。所以当a2<pivot的时候,还剩下2/3的可能性需要排查。
再进一步,如果第二步比较果真发现a2<pivot的话,第三步比较就更不妙了,模仿上面的推理,a3<pivot的概率将会是3/4
这就是快排也不那么快的原因,因为它也没有做到每次比较都能将剩下的可能性砍掉一半。
一些其他的说法:
引用
giving quantitative details: `On average the number of comparisons done in HEAPSORT is about twice as much as in QUICKSORT, but HEAPSORT avoids the slight possibility of a catastrophic degradation of performance.'
4,只需要一种看问题的本质视角:
将排序问题看成和猜数字一样,是通过问问题来缩小/排除(narrow down)结果的可能性区间,这样一来,就会发现,“最好的问题”就是那些能够均分所有可能性的问题,因为那样的话不管问题的答案如何,都能排除掉k- 1/k(k为问题的答案有多少种输出——猜数字里面是2,称球里面是3)种可能性,而不均衡的问题总会有一个或一些答案分支排除掉的可能性要小于k-1 /k。于是策略的下界就被拖累了。
5,鸡排为什么又那么快呢?
引用
不是很明白这段话。
传统的解释是:基排不是基于比较的,所以不具有后者的局限性。话是没错,但其实还可以将它和基于比较的排序做一个类比。
基排的过程也许是源于我们理顺一副牌的过程:如果你有N(N<=13)张牌,乱序,如何理顺呢?我们假象桌上有十三个位置,然后我们将手里的牌一张一张放出去,如果是3,就放在位置3上,如果是J,就放在位置11上,放完了之后从位置1到位置13收集所有的牌(没有牌的位置上不收集任何牌)。
我们可以这样来理解基排高效的本质原因:假设前i张牌都已经放到了它们对应的位置上,第i+1张牌放出去的时候,实际上就相当于“一下子”就确立了它和前i张牌的大小关系,用O(1)的操作就将这张牌正确地插入到了前i张牌中的正确位置上,这个效果就相当于插入排序的第i轮原本需要比较O(i)次的,现在只需要O(1)了。
但是,为什么基排能够达到这个效果呢?上面只是解释了过程,解释了过程不代表解释了本质。
当i张牌放到位之后,放置第i+1张牌的时候有多少种可能性?大约i+1种,因为前i张牌将13个位置分割成了i+1个区间——第i+1张牌可以落在任意一个区间。所以放置第i+1张牌就好比是询问这样一个问题:“这张牌落在哪个区间呢?”而这个问题的答案有i+1种可能性?所以它就将剩下来的可能性均分成了i+1份(换句话说,砍掉了i/i+1的可能性!)。再看看基于比较的排序吧:由于每次比较只有两种结果,所以最多只能将剩下的可能性砍掉一半。
这就是为什么基排要快得多。而所有基于比较的排序都逃脱不了NlogN的宿命。
分享到:
相关推荐
【小学生排比句训练】是针对小学生语文教育中的一种写作技巧——排比句的训练材料。排比句是指在句子中使用结构相同、意思相近或相反的词语或短语,以增强语言的表现力和感染力。 1. 排比句在表达生活观念时能起到...
本篇PPT课件主要介绍了几位美国总统在讲话中使用的排比句实例,展示了如何巧妙运用排比句来提升语言的魅力和影响力。 1. Julius Caesar的"I came; I saw; I conquered." 是一个经典的三元排比句,简洁有力地表达了...
作文素材排比句.pdf
梦想是什么排比句.doc
这个文档为学习者提供了丰富的素材,帮助他们在写作中更好地运用排比句,提升作品的艺术效果。通过理解和模仿这些精巧的排比,不仅可以增强文字功底,也能丰富个人的表达方式,使语言更具魅力和深度。
【标题】和【描述】提及的是高中语文教育中的作文素材,特别是关于精美排比句的仿写,旨在提升学生的写作技巧和表达能力。排比句是通过结构相似、意思相关或相反的句子来增强语言的表现力,使得文章更加生动、有力。...
排比叙例是一种常见的议论文写作技巧,它通过列举并排比不同时间、地点、人物、事件或观点的例子,形成一种强大的说服力。这种方法不仅能够增强文章的气势和视觉冲击力,还能让论证的内容更加丰富、论据更加充分,...
首先,让我们了解什么是排比句。排比句是一种特殊的句式,它可以用来叙述、描写、抒情、说理等多种方式。排比句的特点是句式工整,内涵丰富,语气连贯,可以增添语言的气势美,可以构建形式的整齐美,可以打造文章的...
【标题】和【描述】提及的是高考作文议论文中运用精彩排比段落的重要性,而文档的【部分内容】则是展示了不同文学元素如何丰富议论文的表达,并提供了多个具体例子,如历史人物、自然景观以及诗词中的情感表达。...
【排比句在小学教育中的应用】 排比句是一种修辞手法,通过使用结构相似、意义相关的一...通过排比句的运用,小学教育旨在培养学生的创造力、想象力以及对美好事物的感知能力,从而为他们的全面发展打下坚实的基础。
“比拼竞赛”有关排比句大全(40条)
6. **叙事排比**:如“我和书的故事实在是太多了,为书而欢乐,为书而哀愁,为书而被处分……”这样的排比有助于构建故事的连贯性和情感深度。 总之,排比句作为一种修辞手法,能够极大地提升文本的艺术性和表达...
例如,将老师比喻为溪流、星星和沙砾,突出其默默奉献和价值。这教导学生学会表达敬意,并理解奉献的意义。 2. **友谊**: 描述友谊的排比句强调朋友在快乐、忧伤、成功和失败时的作用,教会孩子们珍视友谊,理解...
标题中提到的“作文素材:排比句大全30句”直接指出了文件的内容属性,它是一份集合了30个排比句的教育类素材。排比句是汉语修辞手法中的一种,通过使用结构相同或相似、意义相关、语气一致的语句,来表达作者的思想...
综上所述,排比句作为一种有效的修辞手段,能够丰富文本内容,加深主题内涵,同时提高语言的表现力,为读者带来多感官的阅读体验。在写作中,合理运用排比句可以使文章更加生动、有力,更好地传达作者的思想和情感。
文档标题和描述中提到的是关于排比句的范文模板,主要展示了如何运用排比句来增强语言的表现力和说服力。排比句是通过结构相同或相似、意思相关的语句排列,达到强调、渲染效果的一种修辞手法。以下将根据标签“范文...
【标题】:“100组经典排比句.doc” 【描述】:“100组经典排比句.doc” 【标签】: 【部分内容】: 这些排比句展现了丰富的修辞手法和表达力,它们用于增强语言的美感和情感的深度。排比句在写作中能够使观点更...