但是证明过程是用比较法，
能否用更加形象的方式解释这个nlgn是怎么来的呢？
（比如我尝试这样解释：对于n个数的排序，每个数至少需要比较lgn次，那么这个lgn又是怎么来的呢？）
决策树排序的下界
如果决策树是针对n个元素排序，那么它的高度至少是nlgn。
在最坏情况下，任何比较排序算法都需要做Ω(nlgn)次比较。
因为输入数据的Ann种可能的排列都是叶结点，所以Ann≤l，由于在一棵高位h的二叉树中，叶结点的数目不多于2h，所以有：
n!≤l≤2h
对两边取对数：
=> lg2h≥lgn!
=> lg2h=hlg2≥lgn!
又因为：
lg2<1
所以：
n≥lgn!=Ω(nlgn) （此处涉及对n阶乘的变换，需要使用斯特林公式）
因为堆排序和归并排序的运行时间上界均为O(nlgn)，因此它们都是渐近最优的比较排序算法。
8 个解决方案
#1
#2
今年是考试作弊被判刑的第一年，刚进*，狱友就问小伙儿犯什么事儿了进来了，小伙儿犹豫半天，说出来你们可能不信！
狱友问：“什么事啊？有什么不相信的，不就是杀人放火，偷抢拐骗么？”
“我是通过考试进来的！”
狱友问：“什么事啊？有什么不相信的，不就是杀人放火，偷抢拐骗么？”
“我是通过考试进来的！”
#3
这里是水区
#4
请不要侮辱广大水友的智商！
#5
和智商有啥关系？
你喜欢加班，留公司里加班，别抱着个电脑在夜总会里码代码
#6
#7
正经回复下，这问题该发去C/C++大版，应该有人会解答。
#8
算法导论？真高深啊~~~~
#1
#2
今年是考试作弊被判刑的第一年，刚进*，狱友就问小伙儿犯什么事儿了进来了，小伙儿犹豫半天，说出来你们可能不信！
狱友问：“什么事啊？有什么不相信的，不就是杀人放火，偷抢拐骗么？”
“我是通过考试进来的！”
狱友问：“什么事啊？有什么不相信的，不就是杀人放火，偷抢拐骗么？”
“我是通过考试进来的！”
#3
这里是水区
#4
请不要侮辱广大水友的智商！
#5
和智商有啥关系？
你喜欢加班，留公司里加班，别抱着个电脑在夜总会里码代码
#6
#7
正经回复下，这问题该发去C/C++大版，应该有人会解答。
#8
算法导论？真高深啊~~~~