NOIP 2006 提高组初赛 选择题第10题 最少比较次数

题面：

分析一：

一句话：5个数的排序，一共有5!种，看成是完全二叉树的叶子结点，树高是 ⌈log2(5!)⌉

展开讲：将n个数的排序过程看作是在一棵2叉树上寻路（因为每次比较只有2个可能结果），而各种排序结果就是树的叶子，显然有n!个叶子，于是树高至少为h=upper_bound(log2(n!))，于是： n个数排序至少要upper_bound(log2(n!))次比较

对于n=5,log2(5!)=6.9，即至少7次

分析二：

对5个数进行排序，需7次比较的方法_x_i_y_u_e的专栏-CSDN博客