N个数最少比较多少次才能保证知道大小顺序?

先说第 1 种情况：

这个问题在 Donald Knuth 所著的 TAOCP 里有详细的讨论，中文好像译为最少比较排序。

（当然应该有很多paper 讨论过这个问题，但我只看过书）

首先有个下界很容易算，因为 n 个数排序最多有 n! 种可能，一次比较产生两种结果，

所以至少需要 \log_2 n! = \Theta(n\log n) 次比较，

但是这个比较次数是不一定能达到的。

目前比较次数的下确界还没有一个通用的公式，据我所知好像只能暴力找。

当然任何一种基于比较的排序算法的时间复杂度都可以提供下确界的一个上界，

一个比较好的上界就是随机快速排序的期望比较次数：(2n+2)\sum_{k=1}^n \frac{1}{k} - 4n，

大概是之前所说的下界的 2 倍，还是有不小差距的。

==========================================================================

再说第 2 种情况：

要保证最后能排好序，一定需要 {n \choose 2} = \frac{n(n-1)}{2}次排序，

这是因为如果在排好序之后 a 和 b 是相邻的，那么它们的大小关系只能通过直接比较确定，

不可能通过和其他数的比较来确定它们的大小关系。

（事实上它们对于其他数的大小关系是完全一样的，如果 a > c，那么也有 b > c，反之亦然。所以不直接比较 a 和 b 是无法区分这两个数的大小关系的。）

第一问其实就是排序算法的最差情况嘛。归并排序和堆排序都是O(nlogn)的。