基于"比较"的内部排序的算法，若对5个元素进行排序，则在最坏情况下所需的比较次数至少为____。

Question

●任何一个基于“比较”的内部排序的算法，若对5个元素进行排序，则在最坏情况下所需的比较次数至少为(71)。
　　(71)A．7
　　B．8
　　C．21
　　D．120
　　答案：(71)A
　　解析：对于5个记录的集合任何一个基于“比较”的内部排序的算法的判定树的叶子结点数目为5!，此判定树的树高至少为log25!。由5!=120，27=128，26=64可得6<log25!<7。因此在最坏情况下所需的比较次数至少为7。
对于这道题,上面是附带的答案,看不明白,于是百度了一下,发现还有3种解法,但是答案却不一样.谁可以解释下这4个情况
最坏情况是逆序5 4 3 2 1按升序排列，第一趟比较4次，第二趟3次....1次
总和10n(n-1)/2=10(n-1)(n-2)/2=6 

Answer 1

以二叉树来看，添加第k个节点时，在最坏的情况下需要比较(int)log(2k-1)次（log的底数为2），5个节点就是：
  (int)log(1) + (int)log(3) + (int)log(5) + (int)log(7) + (int)log(9)
= 0 + 1 + 2 + 2 + 3
= 8

Answer 2

题解中所说的判定树，是指用来模拟排序过程的二叉树，树中的每个结点代表了所有可能的排序集合，而边代表了记录之间的比较，也就是一个判断。判定树每个叶结点对应一种排列情况，因此一共有n！个叶结点。此判定树的最小深度为log(n！)＝Ω(nlogn)，也就是说基于比较的排序问题的下限也为Ω(nlogn)。因此题解由下限可得出最小的比较次数为 7 次的结论。楼主……