雅乐网

在排序的结果中，各个元素的次序依赖于他们之间的比较，这种排序算法叫做比较排序。基于比较的排序有O(n^2)的冒泡排序、插入排序等，也有O(nlogn)复杂度的归并排序、堆排序等。实际上，O(nlogn)在渐进意义上是最优的。

假设我们有n个元素需要排序，所有可能的情况是n个元素的全排列，共有n! 种。假设其中的两个元素时a和b，我们可以通过比较a和b这一次比较，我们可以缩小结果的范围。

下面是一个3个元素排序的决策树，来自《数据结构和算法分析c语言描述》

树中的每个叶子节点对应了最后的结果，n个元素可能的排列有n!种，所以有n!个叶子节点。

而每个叶子结点的深度就是得到该结果所需要的比较次数。在最坏情况下，只需要考虑最深的叶子结点，数值上等于树的高度。

高度为h的二叉树，叶子结点最多有2^h个

则叶子结点n!的二叉树，高度至少是log(n!)

这也就是说，基于比较排序的复杂度下界是log(n!)

$$log(n!) = log(n*(n-1)*(n-2)* … * 3 * 2 * 1)$$

$$= log(n) + log (n-1) + log(n-2) + … + log(3) + log(2) + log(1)$$

$$\ge log(n)+ log(n-1) + … + log(n/2) $$

$$> \frac{n}{2} log(\frac{n}{2})$$

$$ = \Omega(nlogn)$$