数学之美番外篇：快排为什么那样快
Posted on数学之美番外篇：快排为什么那样快
刘未鹏 | Mind Hacks 思维改变生活
数学之美番外篇：快排为什么那样快
By ??? – June 13, 2008Posted in:数学, 算法, 计算机科学
目录
前言
猜数字
称球
排序
3.1 为什么堆排比快排慢
3.2 为什么快排其实也不是那么快
3.3 基排又为什么那么快呢
信息论！信息论？
小结
0.**前言**
知道这个理论是在TopLanguage上的一次讨论，先是g9转了David MacKay的一篇文章，然后引发了牛人们的一场关于信息论的讨论。Anyway，正如g9很久以前在Blog里面所说的： 有时无知是福。俺看到一点新鲜的科普也能觉得造化神奇。刚才读Gerald Jay Sussman（SICP作者）的文章，Building Robust Systems – an essay，竟然心如小鹿乱撞，手心湿润，仿佛第一次握住初恋情人温柔的手。
而看到MacKay的这篇文章我也有这种感觉——以前模糊的东西忽然有了深刻的解释，一切顿时变得明白无比。原来看问题的角度或层面能够带来这么大的变化。再一次印证了越是深刻的原理往往越是简单和强大。所以说，土鳖也有土鳖的幸福:P
这篇文章相当于MacKay原文的白话文版。MacKay在原文中用到了信息论的知识，后者在我看来并不是必须的，尽管计算的时候方便，但与本质无关。所以我用大白话解释了一通。
1.**猜数字**
我们先来玩一个猜数字游戏：我心里默念一个1~64之间的数，你来猜（你只能问答案是“是”或“否”的问题）。为了保证不论在什么情况下都能以尽量少的次数猜中，你应该采取什么策略呢？很显然，二分。先是猜是不是位于1~32之间，排除掉一半可能性，然后对区间继续二分。这种策略能够保证无论数字怎么跟你捉迷藏，都能在log_2{n}次以内猜中。用算法的术语来说就是它的下界是最好的。
我们再来回顾一下这个游戏所蕴含的本质：为什么这种策略具有最优下界？答案也很简单，这个策略是平衡的。反之如果策略不是平衡的，比如问是不是在1~10之间，那么一旦发现不是在1~10之间的话就会剩下比N/2更多的可能性需要去考察了。
徐宥在讨论中提到，这种策略的本质可以概括成“让未知世界无机可乘”。它是没有“弱点的”，答案的任何一个分支都是等概率的。反之，一旦某个分支蕴含的可能性更多，当情况落到那个分支上的时候你就郁闷了。比如猜数字游戏最糟糕的策略就是一个一个的猜：是1吗？是2吗？… 因为这种猜法最差的情况下需要64次才能猜对，下界非常糟糕。二分搜索为什么好，就是因为它每次都将可能性排除一半并且无论如何都能排除一半（它是最糟情况下表现最好的）。
2.**称球**
12个小球，其中有一个是坏球。有一架天平。需要你用最少的称次数来确定哪个小球是坏的并且它到底是轻还是重。
这个问题是一道流传已久的智力题。网络上也有很多讲解，还有泛化到N个球的情况下的严格证明。也有零星的一些地方提到从信息论的角度来看待最优解法。本来我一直认为这道题目除了试错之外没有其它高妙的思路了，只能一个个方法试，并尽量从结果中寻找信息，然后看看哪种方案最少。
然而，实际上它的确有其它的思路，一个更本质的思路，而且根本用不着信息论这么拗口的知识。
我们先回顾一下猜数字游戏。为了保证任何情况下以最少次数猜中，我们的策略是每次都排除恰好一半的可能性。类比到称球问题上：坏球可能是12个球中的任意一个，这就是12种可能性；而其中每种可能性下坏球可能轻也可能重。于是“坏球是哪个球，是轻是重”这个问题的答案就有12×2=24种可能性。现在我们用天平来称球，就等同于对这24种可能性发问，由于天平的输出结果有三种“平衡、左倾、右倾”，这就相当于我们的问题有三个答案，即可以将所有的可能性切成三份，根据猜数字游戏的启发，我们应当尽量让这三个分支概率均等，即平均切分所有的可能性为三等份。如此一来的话一次称量就可以将答案的可能性缩减为原来的1/3，三次就能缩减为1/27。而总共才有24种可能性，所以理论上是完全可以3次称出来的。
如何称的指导原则有了，构造一个称的策略就不是什么太困难的事情了。首先不妨解释一下为什么最直观的称法不是最优的——6、6称：在6、6称的时候，天平平衡的可能性是0。刚才说了，最优策略应该使得天平三种状态的概率均等，这样才能三等分答案的所有可能性。
为了更清楚的看待这个问题，我们不妨假设有6个球，来考虑一下3、3称和2、2称的区别：
在未称之前，一共有12种可能性：1轻、1重、2轻、2重、…、6轻、6重。现在将1、2、3号放在左边，4、5、6放在右边3、3称了之后，不失一般性假设天平左倾，那么小球的可能性就变成了原来的一半（6种）：1重、2重、3重、4轻、5轻、6轻。即这种称法能排除一半可能性。
现在再来看2、2称法，即1、2放左边，3、4放右边，剩下的5、6不称，放一边。假设结果是天平平衡，那么可能性剩下——4种：5重、5轻、6重、6轻。假设天平左倾，可能性也剩下4种：1重、2重、3轻、4轻。右倾和左倾的情况类似。总之，这种称法，不管天平结果如何，情况都被我们缩小到了原来的三分之一！我们充分利用了“天平的结果状态可能有三种”这个条件来三等分所有可能性，而不是二等分。
说到这里，剩下的事情就实在很简单了：第二步称法，只要记着这样一个指导思想——你选择的称法必须使得当天平平衡的时候答案剩下的可能性和天平左倾（右倾）的时候答案剩下的可能性一样多。实际上，这等同于你得选择一种称法，使得天平输出三种结果的概率是均等的，因为天平输出某个结果的概率就等同于所有支持这个结果（左倾、右倾、平衡）的答案可能性的和，并且答案的每个可能性都是等概率的。
MacKay在他的书《Information Theory: Inference and Learning Algorithms》（作者开放免费电子书）里面4.1节专门讲了这个称球问题，还画了一张不错的图，我就照抄了：
图中“1+”是指“1号小球为重”这一可能性。一开始一共有24种可能性。4、4称了之后不管哪种情况（分支），剩下来的可能性总是4种。这是一个完美的三分。然后对每个分支构造第二次称法，这里你只要稍加演算就可以发现，分支1上的第二次称法，即“1、2、6对3、4、5”这种称法，天平输出三种结果的可能性是均等的（严格来说是几乎均等）。这就是为什么这个称法能够在最坏的情况下也能表现最好的原因，没有哪个分支是它的弱点，它必然能将情况缩小到原来的1/3。
3.**排序**
用前面的看问题视角，排序的本质可以这样来表述：一组未排序的N个数字，它们一共有N!种重排，其中只有一种排列是满足题意的（譬如从大到小排列）。换句话说，排序问题的可能性一共有N!种。任何基于比较的排序的基本操作单元都是“比较a和b”，这就相当于猜数字游戏里面的一个问句，显然这个问句的答案只能是“是”或“否”，一个只有两种输出的问题最多只能将可能性空间切成两半，根据上面的思路，最佳切法就是切成1/2和1/2。也就是说，我们希望在比较了a和b的大小关系之后，如果发现a
我们希望每次在比较a和b的时候，a
一个直接的推论是，如果每次都像上面这样的完美比较，那么N个元素的N!种可能排列只需要log_2{N!}就排查玩了，而log_2{N!}近似于NlogN。这正是快排的复杂度。
3.1**为什么堆排比快排慢**
回顾一下堆排的过程：
建立最大堆（堆顶的元素大于其两个儿子，两个儿子又分别大于它们各自下属的两个儿子… 以此类推）
将堆顶的元素和最后一个元素对调（相当于将堆顶元素（最大值）拿走，然后将堆底的那个元素补上它的空缺），然后让那最后一个元素从顶上往下滑到恰当的位置（重新使堆最大化）。
重复第2步。
这里的关键问题就在于第2步，堆底的元素肯定很小，将它拿到堆顶和原本属于最大元素的两个子节点比较，它比它们大的可能性是微乎其微的。实际上它肯定小于其中的一个儿子。而大于另一个儿子的可能性非常小。于是，这一次比较的结果就是概率不均等的，根据前面的分析，概率不均等的比较是不明智的，因为它并不能保证在糟糕情况下也能将问题的可能性削减到原本的1/2。可以想像一种极端情况，如果a肯定小于b，那么比较a和b就会什么信息也得不到——原本剩下多少可能性还是剩下多少可能性。
在堆排里面有大量这种近乎无效的比较，因为被拿到堆顶的那个元素几乎肯定是很小的，而靠近堆顶的元素又几乎肯定是很大的，将一个很小的数和一个很大的数比较，结果几乎肯定是“小于”的，这就意味着问题的可能性只被排除掉了很小一部分。
这就是为什么堆排比较慢（堆排虽然和快排一样复杂度都是O(NlogN)但堆排复杂度的常系数更大）。
MacKay也提供了一个修改版的堆排：每次不是将堆底的元素拿到上面去，而是直接比较堆顶（最大）元素的两个儿子，即选出次大的元素。由于这两个儿子之间的大小关系是很不确定的，两者都很大，说不好哪个更大哪个更小，所以这次比较的两个结果就是概率均等的了。具体参考这里。
3.2**为什么快排其实也不是那么快**
我们考虑快排的过程：随机选择一个元素做“轴元素”，将所有大于轴元素的移到左边，其余移到右边。根据这个过程，快排的第一次比较就是将一个元素和轴元素比较，这个时候显而易见的是，“大于”和“小于”的可能性各占一半。这是一次漂亮的比较。
然而，快排的第二次比较就不那么高明了：我们不妨令轴元素为pivot，第一次比较结果是a1
再进一步，如果第二步比较果真发现a2<pivot的话，第三步比较就更不妙了，模仿上面的推理，a3<pivot的概率将会是3/4！
这就是快排也不那么快的原因，因为它也没有做到每次比较都能将剩下的可能性砍掉一半。
3.3**鸡排为什么又那么快呢？**
传统的解释是：基排不是基于比较的，所以不具有后者的局限性。话是没错，但其实还可以将它和基于比较的排序做一个类比。
基排的过程也许是源于我们理顺一副牌的过程：如果你有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的宿命。
4.**信息论！信息论？**
本来呢，MacKay写那篇文章是想用信息论来解释为什么堆排慢，以及为什么快排也慢的。MacKay在他的文章中的解释是，只有提出每种答案的概率都均等的问题，才能获得最大信息量。然而，仔细一想，其实这里信息论并不是因，而是果。这里不需要用信息论就完全能够解释，而且更明白。信息论只是对这个解释的一个形式化。当然，信息论在其它地方还是有应用的。但这里其实用不着信息论这么重量级的东西（也许具体计算一些数据的时候是需要的），而是只需要一种看问题的本质视角：将排序问题看成和猜数字一样，是通过问问题来缩小/排除（narrow down）结果的可能性区间，这样一来，就会发现，“最好的问题”就是那些能够均分所有可能性的问题，因为那样的话不管问题的答案如何，都能排除掉k-1/k（k为问题的答案有多少种输出——猜数字里面是2，称球里面是3）种可能性，而不均衡的问题总会有一个或一些答案分支排除掉的可能性要小于k-1/k。于是策略的下界就被拖累了。
5.**小结**
这的确是“小结”，因为两点：
这个问题可以有信息论的理论解释，而信息论则是一个相当大的领域了。
文中提到的这种看问题的视角除了用于排序、称球，还能够运用到哪些问题上（比如搜索）。
Update(06/13/2008) : 徐宥在讨论中继续提到： 另外，这几天我重新把TAOCP 第三卷(第二版)翻出来看了看 Knuth 怎么说这个问题的, 发现真是牛大了：
先说性能：
pp148, section 5.2.3 说：
When N = 1000, the approximate average runiing time on MIX are 160000u for heapsort 130000u for shellsort 80000u for quicksort
这里, Knuth 同学发现一般情况下 heapsort 表现很不好. 于是，在下文他就说，习题18 (pp156, 难度21)
(R.W.Floyd) During the selection phase of heapsort, the key K tends to be quite small, so that nearly all the comparisons in step H6 find K<K_j. Show how to modify the algorithm so that K is not compared with K_j in the main loop of the computation, thereby nearly cutting the average number of comparisons in half.
答案里面的方法和DMK的方法是一样的。(我觉得DMK是看了这个论文或者TAoCP的) 这里说 by half，就正好和快排差不多了。
再说信息论分析：
在5.3.1 (pp181) 高爷爷就说, “排序问题可以看成是一个树上的鸟儿排排站的问题. (还特地画了一棵树), 下一段就说, 其实这个也 有等价说法, 就是信息论, 我们从称球问题说起…”
然后后面一直讲信息论和最小比较排序…
高爷爷真不愧是姓高的，囧rz.. Tags: 数学, 算法, 计算机科学
About ???
喜欢取消喜欢2 人喜欢
chaonin
@@之前就在你的卢浮宫看到了，写的直白明了！ 小弟学的是编码，呵呵。 Mackay的那本书重点是介绍编码的，具体的说是纠错码的。编码理论的重要基础是信息论。 他对这些问题的分析不是专门要来分析这写问题的，而只是用信息论的方法来解释这些现象。
受益良多 每每看到一些精妙的解法(算法),都想拍手称快.
关注toplanguage很久了.只是一直不敢在上面留言,看上面的聊天就感觉自己是沧海一粟.今天看到一篇.可能你是幸运的吧.我大概算了下,你应该是和我同届的.不过我比你小一岁.马上就毕业两年了.研究生们也快毕业了....回忆这些日子,感觉偏离了自己的目标,也感觉工作后并没有自己希望的成长着.一直觉得学校的东西很迂腐,什么都需要自己去学习.曾经也深深相信自己能好好成长起来.只是,到了今天,不知道自己是否还跟着大家的脚步....
metal-fan
写的太棒了～深入本质～受益匪浅！！！
raymond
这是最大熵原则的几个例子，即保留最大的不确定性，因为这样才能保留最大的信息。生活中很多问题都可以归结为一些简单的法则，而在实际处理问题的时候，这些简单的法则会被以各种各样的形式掩盖，从而让我们失去探索的机会。博主是个有心人啊
bigining
在说到12个的例子时，第二次称时：“这是一个完美的三分。然后对每个分支构造第二次称法，这里你只要稍加演算就可以发现，分支1上的第二次称法，即“1、2、6对3、4、5”这种称法，天平输出三种结果的可能性是均等的（严格来说是几乎均等）。”，但是这样好像是找不出那个不同的球的。不知道1、2、6对3、4、5之后要怎么进行判断？（可以假设1、2、6比3、4、5重，然后只能说明1、 2较重或5较轻，然后第三次要怎么进行？）
Ted
晕，你都说了“然后只能说明1、 2较重或5较轻”，这还不明显，再把1，2分别放2边，哪个重，哪个就是，否则就是平衡，那5就是目标。
simple
以6个球的例子来说，这个策略的“答案”是随着剩下的可能性（或者说剩下的球）的数量而发生变化的，比如，当球剩下2个时，那么天平的输出结果只可能有两种：左或右倾。因此，这时候应该是以以2去平分剩下的可能性。
rrison
离散数学里的博弈树
dell latitude d620 laptop battery
非常感谢。受益良多。
kmplayer
"那么可以证明第二次比较a2也小于pivot的可能性是2/3！" ”a3<pivot的概率将会是3/4！“ 这两个地方的”叹号“很容易误解为”阶层“
hit_alex
把这西抽象出来确实也挺有意思的。另外，我注意到标题：鸡排为什么又那么快呢？中“鸡排”是不是写错了？莫非是作者故意为之？
4、4称了之后不管哪种情况（分支），剩下来的可能性总是》 8 《种吧
wosunziwuwan
"那么可以证明第二次比较a2也小于pivot的可能性是2/3"这句话有问题吧，可能性应该还是1/2吧？因为只是a2和pivot相对次序的比较，和a1无关，是一次独立的比较。这和取排问题不同，确定了2张牌后，第3张牌只有从剩下的牌中去取
更为本质一些，我觉得跟最大熵原理有些关系。 参考http://yeasy.blogspot.com/2011/11/blog-post.html
LittleJ
"第一次比较结果是a1<pivot，那么可以证明第二次比较a2也小于pivot的可能性是2/3！"这里我也不是很明白。这里指的第一次第二次都是相对于快排的一次排序来说的吧？那么第一次将a1和pivot比较，大或者小的概率是相等的这里没有问题。为什么第二次比较a2要“也”小于pivot呢？我的意思就是第一次比较和第二次比较之间有什么关联？这里我没有看明白，能不能解释一下呢？谢谢：）
看起来很多人不理解这个，反复想不明白，坐等解答啊
“然而，快排的第二次比较就不那么高明了：我们不妨令轴元素为pivot，第一次比较结果是a1pivot的话，那么a1，a2，pivot这三个元素之间的关系就完全确定了——a1
关于快排的部分，其实本质是指轴元素如果选取的不够“中间”，会导致第一次排序后左右不均，从而导致较差的效率表现。刘大牛从缩减可能性这个角度出发，让人耳目一新。受教了。
simple
鸡排之所以快，我觉得还可以用另一种说法（以13张牌的例子为例）：第i张牌确定位置后，放第i+1张牌时，桌上剩下的位置还有 13-i 个，即放牌的可能性为13-i种，然后，摸牌再看是什么点数就相当于公布答案，而这个答案刚好也是有 13-i 种，即，13-i种答案把13-i种可能性平均分为了13-i/13-i = 1种，最后得到鸡排需要的时间复杂度为O（1）
imgen
关于称球问题，我正是用了信息论的方法为指引，三分而称球，而且我也给出了推广到N的解法，从中获得了很多乐趣和满足。不过那是在大学时代了，久远了
真心佩服了。之前觉得称球问题没有什么，看这文章才知道原来有这么多的东西！
高爷爷是谁？
哇高爷爷果然是神人也，查了一下73年v3的第一版就有神论1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
2012年11月6日[回复]()[顶]()[转发]()[举报]()
* [![ouqi]()](http://weibo.com/xianqings "ouqi")
[ouqi](http://weibo.com/xianqings)
同不明白这一块：
然而，快排的第二次比较就不那么高明了：我们不妨令轴元素为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之间的数字的排序，那么第二次的privot又是重新选定的。也就是说在第一次排序之后，任何一个值跟第一次的privot的大小关系都是确定了的，要么比他大 要么比他小。那您说a2是什么？
4月10日[回复]()[顶]()[转发]()[举报]()
* [![ナイキ 通販]()](http://www.abcsnk.com/ "ナイキ 通販")
[ナイキ 通販](http://www.abcsnk.com/)
searching is another thing no doubt you like to accomplish (specially me), when i don't recognize how but searching is one particular activity which offers us eminence delight and relaxation whenever we are generally tired as well as frustrated as well as irritated, but while using ever raising targets along with office update they have became next to impossible for us to determine some time for it to hang out with his friends and enjoy that period while rooming around for the streets involving market.
But even as we always say there's [http://www.abcsnk.com/adidas-スパイクサッカー-アディピュア-11pro-c-22_23_29.html](http://www.abcsnk.com/adidas-スパイクサッカー-アディピュア-11pro-c-22_23_29.html) アディピュア11pro a option for just about every problem along with situation on the [http:///www.sportrakuten.com](http:/www.sportrakuten.com) サングラス通販 globe, all you want to do is seek out that option with [http://www.sportrakuten.com/categories/1369471366-179.html](http://www.sportrakuten.com/categories/1369471366-179.html) レイバン サングラス 'something different' perspective. And which is the very reason we invented a many new method involving shopping which in turn know while online searching method. But staying this strategy new types of quarries that happen to be there inside mind of folks related on the same and were here to unravel those themselves.
But today you'll find thousands involving products that is purchased via an web shop starting coming from a bugger to your flat in fact it is impossible for individuals to cover hundreds of in one particular discussion themselves therefore today we'll be only talking over facts pertains to [http://www.abcsnk.com](http://www.abcsnk.com/) ナイキ 通販 online searching of sneakers for adult men.
Buying some your favourite Adidas [http://www.abcsnk.com/adidas-スパイクサッカー-プレデター-アディダス-11-c-22_23_25.html](http://www.abcsnk.com/adidas-スパイクサッカー-プレデター-アディダス-11-c-22_23_25.html) adidas プレデター sneakers from these websites is just about the easiest thing on the [http:///www.sportrakuten.com/categories/1369471516-183.html](http:/www.sportrakuten.com/categories/1369471516-183.html) レイバン(RAY BAN) globe, but to generate it truly easy you've got to keep up few in the things as well as points that happen to be listed down below.
6月19日[回复]()[顶]()[转发]()[举报]()
[1]()[]()
社交帐号登录:
* [微博](http://pongba.duoshuo.com/login/weibo/?sso=1&redirect_uri=http%3A%2F%2Fmindhacks.cn%2Fwp-login.php%3Faction%3Dduoshuo_login&redirect_to%3Dhttp%3A%2F%2Fmindhacks.cn%2F2008%2F06%2F13%2Fwhy-is-quicksort-so-quick%2F)
* [QQ](http://pongba.duoshuo.com/login/qq/?sso=1&redirect_uri=http%3A%2F%2Fmindhacks.cn%2Fwp-login.php%3Faction%3Dduoshuo_login&redirect_to%3Dhttp%3A%2F%2Fmindhacks.cn%2F2008%2F06%2F13%2Fwhy-is-quicksort-so-quick%2F)
* [人人](http://pongba.duoshuo.com/login/renren/?sso=1&redirect_uri=http%3A%2F%2Fmindhacks.cn%2Fwp-login.php%3Faction%3Dduoshuo_login&redirect_to%3Dhttp%3A%2F%2Fmindhacks.cn%2F2008%2F06%2F13%2Fwhy-is-quicksort-so-quick%2F)
* [豆瓣](http://pongba.duoshuo.com/login/douban/?sso=1&redirect_uri=http%3A%2F%2Fmindhacks.cn%2Fwp-login.php%3Faction%3Dduoshuo_login&redirect_to%3Dhttp%3A%2F%2Fmindhacks.cn%2F2008%2F06%2F13%2Fwhy-is-quicksort-so-quick%2F)
* [更多»]()
* [开心](http://pongba.duoshuo.com/login/kaixin/?sso=1&redirect_uri=http%3A%2F%2Fmindhacks.cn%2Fwp-login.php%3Faction%3Dduoshuo_login&redirect_to%3Dhttp%3A%2F%2Fmindhacks.cn%2F2008%2F06%2F13%2Fwhy-is-quicksort-so-quick%2F)
* [网易](http://pongba.duoshuo.com/login/netease/?sso=1&redirect_uri=http%3A%2F%2Fmindhacks.cn%2Fwp-login.php%3Faction%3Dduoshuo_login&redirect_to%3Dhttp%3A%2F%2Fmindhacks.cn%2F2008%2F06%2F13%2Fwhy-is-quicksort-so-quick%2F)
* [搜狐](http://pongba.duoshuo.com/login/sohu/?sso=1&redirect_uri=http%3A%2F%2Fmindhacks.cn%2Fwp-login.php%3Faction%3Dduoshuo_login&redirect_to%3Dhttp%3A%2F%2Fmindhacks.cn%2F2008%2F06%2F13%2Fwhy-is-quicksort-so-quick%2F)
* [百度](http://pongba.duoshuo.com/login/baidu/?sso=1&redirect_uri=http%3A%2F%2Fmindhacks.cn%2Fwp-login.php%3Faction%3Dduoshuo_login&redirect_to%3Dhttp%3A%2F%2Fmindhacks.cn%2F2008%2F06%2F13%2Fwhy-is-quicksort-so-quick%2F)
* [谷歌](http://pongba.duoshuo.com/login/google/?sso=1&redirect_uri=http%3A%2F%2Fmindhacks.cn%2Fwp-login.php%3Faction%3Dduoshuo_login&redirect_to%3Dhttp%3A%2F%2Fmindhacks.cn%2F2008%2F06%2F13%2Fwhy-is-quicksort-so-quick%2F)
[![]()]()
发布
[]( "插入表情")
[刘未鹏 | Mind Hacks正在使用多说](http://duoshuo.com/)
1. chaonin on [February 17, 2009 at 10:34 am](http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/comment-page-1/#comment-93) said:
@@之前就在你的卢浮宫看到了，写的直白明了！
小弟学的是编码，呵呵。
Mackay的那本书重点是介绍编码的，具体的说是纠错码的。编码理论的重要基础是信息论。
他对这些问题的分析不是专门要来分析这写问题的，而只是用信息论的方法来解释这些现象。
1. [帅得不敢出门](http://stupidpig.cublog.cn/) on [March 23, 2009 at 8:46 pm](http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/comment-page-1/#comment-292) said:
受益良多
每每看到一些精妙的解法(算法),都想拍手称快.
1. [conan](http://www.cloved.cn/) on [May 11, 2009 at 9:43 am](http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/comment-page-1/#comment-407) said:
关注toplanguage很久了.只是一直不敢在上面留言,看上面的聊天就感觉自己是沧海一粟.今天看到一篇.可能你是幸运的吧.我大概算了下,你应该是和我同届的.不过我比你小一岁.马上就毕业两年了.研究生们也快毕业了….回忆这些日子,感觉偏离了自己的目标,也感觉工作后并没有自己希望的成长着.一直觉得学校的东西很迂腐,什么都需要自己去学习.曾经也深深相信自己能好好成长起来.只是,到了今天,不知道自己是否还跟着大家的脚步….
1. metal-fan on [October 15, 2009 at 9:13 pm](http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/comment-page-1/#comment-616) said:
写的太棒了～深入本质～受益匪浅！！！
1. raymond on [December 25, 2009 at 10:38 pm](http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/comment-page-1/#comment-709) said:
这是最大熵原则的几个例子，即保留最大的不确定性，因为这样才能保留最大的信息。生活中很多问题都可以归结为一些简单的法则，而在实际处理问题的时候，这些简单的法则会被以各种各样的形式掩盖，从而让我们失去探索的机会。博主是个有心人啊
1. bigining on [April 24, 2010 at 6:10 pm](http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/comment-page-1/#comment-888) said:
在说到12个的例子时，第二次称时：“这是一个完美的三分。然后对每个分支构造第二次称法，这里你只要稍加演算就可以发现，分支1上的第二次称法，即“1、2、6对3、4、5”这种称法，天平输出三种结果的可能性是均等的（严格来说是几乎均等）。”，但是这样好像是找不出那个不同的球的。不知道1、2、6对3、4、5之后要怎么进行判断？（可以假设1、2、6比3、4、5重，然后只能说明1、 2较重或5较轻，然后第三次要怎么进行？）
* Ted on [November 28, 2011 at 3:30 am](http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/comment-page-1/#comment-18264) said:
晕，你都说了“然后只能说明1、 2较重或5较轻”，这还不明显，再把1，2分别放2边，哪个重，哪个就是，否则就是平衡，那5就是目标。
* rrison on [May 6, 2010 at 11:26 am](http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/comment-page-1/#comment-904) said:
离散数学里的博弈树
* [dell latitude d620 laptop battery](http://www.usbphoneworld.com/lbded6620.html) on [June 13, 2010 at 10:56 am](http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/comment-page-1/#comment-934) said:
非常感谢。受益良多。
*
Pingback: [数学之美番外篇：快排为什么那样快 | 天道酬勤](http://www.iskycloud.com/blog/algorithm/52.html)
* kmplayer on [December 16, 2010 at 3:25 pm](http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/comment-page-1/#comment-11214) said:
“那么可以证明第二次比较a2也小于pivot的可能性是2/3！”
”a3<pivot的概率将会是3/4！“
这两个地方的”叹号“很容易误解为”阶层“
* hit_alex on [December 26, 2010 at 5:15 pm](http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/comment-page-1/#comment-11319) said:
把这西抽象出来确实也挺有意思的。另外，我注意到标题：**鸡排为什么又那么快呢？**中“鸡排”是不是写错了？莫非是作者故意为之？
* [Miller](http://www.lisher.tk/) on [February 14, 2011 at 10:23 pm](http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/comment-page-1/#comment-12358) said:
4、4称了之后不管哪种情况（分支），剩下来的可能性总是》 8 《种吧
*
Pingback: [知其所以然（续） - 东莞律师网](http://www.lawyer888.com/?p=122)
*
Pingback: [知其所以然（续） | w3er](http://w3er.com/%e6%9c%aa%e5%88%86%e7%b1%bb/%e7%9f%a5%e5%85%b6%e6%89%80%e4%bb%a5%e7%84%b6%ef%bc%88%e7%bb%ad%ef%bc%89/)
*
Pingback: [知其所以然（三）——为什么算法这么难？](http://mindhacks.cn/2011/07/10/the-importance-of-knowing-why-part3/)
*
Pingback: [推荐读书《暗时间》](http://www.whoisnerd.com/2011/07/31/%e6%8e%a8%e8%8d%90%e8%af%bb%e4%b9%a6%e3%80%8a%e6%9a%97%e6%97%b6%e9%97%b4%e3%80%8b/)
*
Pingback: [转：为什么算法这么难？ | South♂楠个人博客](http://southmagic.sinaapp.com/?p=18)
*
Pingback: [知其所以然（续） | 风的天地](http://blog69.tk/?p=540)
*
Pingback: [知其所以然（三）：为什么算法这么难？ | 风的天地](http://blog69.tk/?p=114)
* wosunziwuwan on [November 27, 2011 at 9:55 pm](http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/comment-page-1/#comment-18259) said:
“那么可以证明第二次比较a2也小于pivot的可能性是2/3″这句话有问题吧，可能性应该还是1/2吧？因为只是a2和pivot相对次序的比较，和a1无关，是一次独立的比较。这和取排问题不同，确定了2张牌后，第3张牌只有从剩下的牌中去取
* [yeasy](http://yeasy.blogspot.com/) on [December 15, 2011 at 4:23 pm](http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/comment-page-1/#comment-18653) said:
更为本质一些，我觉得跟最大熵原理有些关系。
参考http://yeasy.blogspot.com/2011/11/blog-post.html
*
Pingback: [罗青-技术博客 | [re]趣谈二分法](http://tsingroo.sinaapp.com/?p=302)
*
Pingback: [趣题：天平找假币 - Aikilis' Blog](http://aikilis.tk/1398)
*
Pingback: [快排_quicksort() - C++](http://cblog.lylzone.info/2012/03/6/quicksort.html)
* LittleJ on [March 19, 2012 at 6:12 pm](http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/comment-page-1/#comment-20448) said:
“第一次比较结果是a1<pivot，那么可以证明第二次比较a2也小于pivot的可能性是2/3！"这里我也不是很明白。这里指的第一次第二次都是相对于快排的一次排序来说的吧？那么第一次将a1和pivot比较，大或者小的概率是相等的这里没有问题。为什么第二次比较a2要“也”小于pivot呢？我的意思就是第一次比较和第二次比较之间有什么关联？这里我没有看明白，能不能解释一下呢？谢谢：）
*
Pingback: [知其所以然（三）：为什么算法这么难？ | 吃杂烩](http://blog.chiapp.com/html/2012-08-09/4159.html)
*
Pingback: [所有排序总结（内排序）（续）——基于比较排序下界 | 编程·早晨](http://code.zc4u.com/articles/5362.html)
*
Pingback: [孙吾饭的游乐场 | 暗时间](http://patdelphi.com/wordpress/?p=508)
* [透明的沙子](http://www.douban.com/people/49902334/) on [September 3, 2012 at 8:51 pm](http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/comment-page-1/#comment-31818) said:
“然而，快排的第二次比较就不那么高明了：我们不妨令轴元素为pivot，第一次比较结果是a1pivot的话，那么a1，a2，pivot这三个元素之间的关系就完全确定了——a1
* [透明的沙子](http://www.douban.com/people/49902334/) on [September 3, 2012 at 8:53 pm](http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/comment-page-1/#comment-31819) said:
看起来很多人不理解这个，反复想不明白，坐等解答啊
* [滔要考研](http://weibo.com/1742521405) on [September 7, 2012 at 1:06 am](http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/comment-page-1/#comment-31827) said:
关于快排的部分，其实本质是指轴元素如果选取的不够“中间”，会导致第一次排序后左右不均，从而导致较差的效率表现。刘大牛从缩减可能性这个角度出发，让人耳目一新。受教了。
* simple on [September 21, 2012 at 11:34 pm](http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/comment-page-1/#comment-31875) said:
以6个球的例子来说，这个策略的“答案”是随着剩下的可能性（或者说剩下的球）的数量而发生变化的，比如，当球剩下2个时，那么天平的输出结果只可能有两种：左或右倾。因此，这时候应该是以以2去平分剩下的可能性。
* simple on [September 22, 2012 at 1:35 am](http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/comment-page-1/#comment-31876) said:
鸡排之所以快，我觉得还可以用另一种说法（以13张牌的例子为例）：第i张牌确定位置后，放第i+1张牌时，桌上剩下的位置还有 13-i 个，即放牌的可能性为13-i种，然后，摸牌再看是什么点数就相当于公布答案，而这个答案刚好也是有 13-i 种，即，13-i种答案把13-i种可能性平均分为了13-i/13-i = 1种，最后得到鸡排需要的时间复杂度为O（1）
* imgen on [September 29, 2012 at 5:45 pm](http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/comment-page-1/#comment-31903) said:
关于称球问题，我正是用了信息论的方法为指引，三分而称球，而且我也给出了推广到N的解法，从中获得了很多乐趣和满足。不过那是在大学时代了，久远了
* [icrt_](http://weibo.com/2177249280) on [October 10, 2012 at 9:03 pm](http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/comment-page-1/#comment-31922) said:
真心佩服了。之前觉得称球问题没有什么，看这文章才知道原来有这么多的东西！
* [_小毛童鞋_](http://weibo.com/1238983263) on [October 16, 2012 at 6:25 pm](http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/comment-page-1/#comment-31942) said:
高爷爷是谁？
* [鸡翅呀鸡翅](http://weibo.com/brightown) on [November 6, 2012 at 3:21 pm](http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/comment-page-1/#comment-32004) said:
哇高爷爷果然是神人也，查了一下73年v3的第一版就有神论~~~膜拜orz
- ouqi on April 10, 2013 at 9:46 pm said:
同不明白这一块：
然而，快排的第二次比较就不那么高明了：我们不妨令轴元素为pivot，第一次比较结果是a1
我的疑惑在于，第一次的a2是什么，为什么要把第二次的排序和第一次的排序相关联? 不明白您定义的第二次排序是什么，我以为的第二次排序是对第一次的起始位置到第一次的pivot之间的数字的排序，那么第二次的privot又是重新选定的。也就是说在第一次排序之后，任何一个值跟第一次的privot的大小关系都是确定了的，要么比他大 要么比他小。那您说a2是什么？
- ナイキ 通販 on June 19, 2013 at 10:11 am said:
searching is another thing no doubt you like to accomplish (specially me), when i don’t recognize how but searching is one particular activity which offers us eminence delight and relaxation whenever we are generally tired as well as frustrated as well as irritated, but while using ever raising targets along with office update they have became next to impossible for us to determine some time for it to hang out with his friends and enjoy that period while rooming around for the streets involving market.
But even as we always say there’s http://www.abcsnk.com/adidas-スパイクサッカー-アディピュア-11pro-c-22_23_29.html アディピュア11pro a option for just about every problem along with situation on the http:///www.sportrakuten.com サングラス通販 globe, all you want to do is seek out that option with http://www.sportrakuten.com/categories/1369471366-179.html レイバン サングラス ‘something different’ perspective. And which is the very reason we invented a many new method involving shopping which in turn know while online searching method. But staying this strategy new types of quarries that happen to be there inside mind of folks related on the same and were here to unravel those themselves.
But today you’ll find thousands involving products that is purchased via an web shop starting coming from a bugger to your flat in fact it is impossible for individuals to cover hundreds of in one particular discussion themselves therefore today we’ll be only talking over facts pertains to http://www.abcsnk.com ナイキ 通販 online searching of sneakers for adult men.
Buying some your favourite Adidas http://www.abcsnk.com/adidas-スパイクサッカー-プレデター-アディダス-11-c-22_23_25.html adidas プレデター sneakers from these websites is just about the easiest thing on the http:///www.sportrakuten.com/categories/1369471516-183.html レイバン(RAY BAN) globe, but to generate it truly easy you’ve got to keep up few in the things as well as points that happen to be listed down below.
- wang on July 5, 2013 at 10:12 am said:
http://www.allsnk.com/nddbc.html http://www.allsnk.com/nddbc.html http://www.allsnk.com/nddbc.html
关于
如果你对我的文章感兴趣，那么很可能你也对我平时的阅读感兴趣，以下是一些你可以参考或订阅的资源：
我在豆瓣上的豆列列举了一些看过的好书：[只读经典]思维改变生活 | [只读经典]思考的技术与艺术 | 决策与判断 | 机器学习与人工智能书籍资源导引 我翻译的书：
- 《Exceptional C++ Style 中文版》
《修改代码的艺术》 我写的书：
被阅读得最多的
- [BetterExplained]为什么你应该（从现在开始就）写博客 - 210,263 views
- 怎样花两年时间去面试一个人 - 207,509 views
- 逃出你的肖申克（二）：仁者见仁智者见智？从视觉错觉到偏见 - 194,733 views
- 暗时间 - 193,494 views
- 我在南大的七年 - 176,349 views
- [BetterExplained]如何有效地记忆与学习 - 169,039 views
- 数学之美番外篇：平凡而又神奇的贝叶斯方法 - 166,636 views
- 逃出你的肖申克（一）：为什么一定要亲身经历了之后才能明白？ - 139,011 views
- 逃出你的肖申克（三）：遇见20万年前的自己 - 135,486 views
- [BetterExplained]书写是为了更好的思考 - 118,613 views
我的微博
你可能也会喜欢以下文章
数学之美番外篇：平凡而又神奇的贝叶斯方法 (113)
- 数学之美番外篇：进化论中的概率论 (16)
- 康托尔、哥德尔、图灵——永恒的金色对角线(rev/#2) (56)
- 知其所以然（三）：为什么算法这么难？ (74)
- 知其所以然（续） (54)
- 机器学习与人工智能学习资源导引 (18)
- 知其所以然（以算法学习为例） (46)
- 跟波利亚学解题(rev/#3) (32) *
*
Copyright 刘未鹏 | Mind Hacks. All Rights Reserved. 苏ICP备09004067号. Powered by Wordpress. Using Arras Theme.
