为什么说任何基于比较的算法将 5 个元素排序都需要 7 次？

排序算法对结果的唯一要求就是操作数满足全序关系：

1. 如果 a≤b 并且 b≤c 那么 a≤c（传递性）。
2. 对于 a 或 b，要不 a≤b，要不 b≤a（完全性）。

这个问题可以用信息论来回答。

我从 1 到 5 中挑一个数字出来让你来猜，每回合你都可以问我一个问题，我的回答“是”或“不是”（1 或 0），那么你至少需要几个回合才能保证猜出这个数字？

比较符合这个游戏精神的玩法是从自己的幸运数字（比如我的是7）开始猜起，一个一个地问我“是不是X？”， 可能你的运气足够好，一个回合就能够猜对，但是在最坏的情况下可能就需要5个回合，所以你的答案应该是“至少需要5个回合” （事实上你至少只需要一次就“有可能”猜出来，但为了“保证能”猜出来，你只好委曲求全地说 5）， 换句话说这种猜法的最优下界是 5。 （平均性能是 1×1/5+2×1/5+…+5×1/5=（1+…+5）/5 = 3）

但因为你会二分，所以会这样问“是不是比3大？”……而且无论我挑出的数字是几，都只用3个回合。 二分显然是一种更佳的策略，那么它好在什么地方呢？ 用信息论理解: 最大的熵。

英文版维基百科词条有个大致的解释：Comparison_sort， 最少次数为 log(5!) = 6.91，取整的话，就是 7。

决策树如下：

如果我们用归并排序的话，比较次数是O（nlogn），因为归并排序是 全局最优解，但是在局部，归并并不都保证是最优的。

附一张快速排序的 gif 图：

相关阅读：

面试算法有必要吗？

评论

12 楼 haiyupeter 2013-04-23  

牛逼的gif图片

11 楼 tidelee 2013-04-23  

只为GIF

10 楼 venrains 2013-04-22  

taolei0628 写道

这个不难理解吧。一次比较只能识别两种状态。6次比较最多识别2^6=64种状态。
5个元素有120种排列，当然至少需要7次比较（2^7=128)才能把所有排列（状态)正确识别。

9 楼 justjavac 2013-04-22  

taolei0628 写道

这个不难理解吧。一次比较只能识别两种状态。6次比较最多识别2^6=64种状态。
5个元素有120种排列，当然至少需要7次比较（2^7=128)才能把所有排列（状态)正确识别。

8 楼 taolei0628 2013-04-22  

这个不难理解吧。一次比较只能识别两种状态。6次比较最多识别2^6=64种状态。
5个元素有120种排列，当然至少需要7次比较（2^7=128)才能把所有排列（状态)正确识别。

7 楼 wusuobuai 2013-04-22  

光看gif图就牛啊

6 楼 leaow567 2013-04-22  

哎～～老忘

5 楼 wupuyuan 2013-04-21  

只为gif图顶下。

4 楼 elan1986 2013-04-19  

3 楼 nodejs 2013-04-19  

coffeescript 写道

学习了。有个问题楼主：所有的比较排序算法应该都达不到 7 次吧？

手动排序。呵呵。

2 楼 coffeescript 2013-04-19  

学习了。有个问题楼主：所有的比较排序算法应该都达不到 7 次吧？

1 楼 artdialog 2013-04-19  

配图很好，一目了然。