昨天和74LS138学长聊天的时候，突然想到一个问题：
基于比较的排序算法中，有很多可以达到\(O\left( {n\log n} \right)\)的时间复杂度，但是能不能找到一种在时间复杂度意义上更快速的排序算法？
在网上查了一下，答案是不能，而且竟然可以很简单地证明出这个结论。
\(n\)个数顺序的可能情况一共有\(n!\)种，如果把每种情况当做二叉树的一个叶子结点，那么每一次比较判断就相当于在二叉树的分叉处选择一个分支，一次排序就可以看做从根节点到一个叶子结点的路径。
根据叶子结点有\(n!\)个可以得出二叉树的高度至少为\(\log _2 \left(n! \right)+1\)，也就是说至少存在一种情况使得需要比较\(\log _2 \left(n! \right)\)次。
根据Stirling公式（\(n!\sim\sqrt {2\pi n} {\left( {\frac{n}{e}} \right)^n}\)）近似，可以得出基于比较的排序算法时间复杂度下限为\(O\left( {n\log n} \right)\)。
没事就多看看算法导论吧
这是平均复杂度下限。实际中排序操作不与比较操作一一对应，也就是有可能复杂度不及nlog(n)或者远大于nlogn。对于随机优化简单快速排序，总有可能会产生实际代价为O(n^2)的排序过称(每次都恰好没有二分)。对于插入排序（完全依赖比较），最好的情况为n。但博主的证明似乎表示最优复杂度不低于nlogn。这点似乎有问题。请注意。当然Quicksort 太过时了。标准库都用Introsort了（我喜欢叫它复合排序）
最好情况不能代表算法的时间复杂度。74LS138学长说根据平摊分析，平均情况与最坏情况应该是一样的。
我说的有问题。对于快排，平均情况比最坏情况下的复杂度低阶。我来给一个粗糙的平摊分析，仅供参考：
T(n) = Tp(n) + T(k) + T(n – k – 1)
其中k为枢轴左侧元素个数，T(n)为将n个元素快排的时间，Tp(n)是将n个元素partition的时间，满足：Tp(n)=Θ(n)，取近似Tp(n) = C * n
所以有：T(n) = C * n + T(k) + T(n – k – 1)
此处均摊假定k服从0..n上的均匀分布，则：T(n) = C * n + Σ{T(k) + T(n – k – 1), k = 0..n} / (n + 1)，代入T(n) = Θ(nlogn)，等式成立
所以：T(n) = Θ(nlogn)
啧啧啧。占沙发
数据结构与算法分析书里也有讲 不过我还没看到=w=
我现在看到了。。这个是最坏的情形。可以证明有L片叶子的完全二叉树的叶子平均深度大于等于ceil(logL) 。这样就证明了平均的时间下界
错了⊙_⊙ 大于等于logL