为什么说任何基于比较的算法将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 图：

原文链接：http:///other/2013/04/10/why-any-sort-algorithm-based-on-the-comparison-of-the-five-elements-are-needed-7-times.html

【编辑推荐】

1. 道家·老子的算法思想分析
2. 天猫程序猿高端算法找妹子
3. 创业企业的十二种死法
4. 程序员如何快速准备面试中的算法
5. 坐在马桶上看算法：快速排序

【责任编辑：林师授 TEL：[phone]】

原文：为什么说任何基于比较的算法将5个元素排序都需要7次？ 返回开发首页