这几道题好难啊，完全不会！求大神解答

1 冒泡排序要进行C(N,2)次比较，每次比较有1/2的概率交换，所以交换操作的期望次数是C(N,2) / 2。

2 下表列出每个元素可能移动的距离：

1      0     1     2     3。。。     n - 1
2      1      0    1     2.。。。    n - 2
。。。

n     n - 1  n - 2                           0

矩阵里面所有元素加起来再除以n。 

3 数学归纳法。假设结论对小于n都成立，则n个数时，前n - 1个数找最大数至少需要n - 2次比较，第n个数要和前n - 1个数的最大数比较1次，所以至少需要n - 1次。

4 首先基于比较的查找算法的下限是lgn。因为二分查找的上限是lgn，所以二分查找是最优的。

5 7个元素排序的决策树模型有7！个叶子结点，所以树高为lg(7!) = 13，也就是说至少要比较13次。
   先任取3个排序，用到2次比较。再任取3个排序，用到2次比较。合并排序它们的结果，至多6次比较。最后一个元素用二分插入，至多3次比较。

引用 1 楼 li_x1979 的回复:

5 7个元素排序的决策树模型有7！个叶子结点，所以树高为lg(7!) = 13，也就是说至少要比较13次。
   先任取3个排序，用到2次比较。再任取3个排序，用到2次比较。合并排序它们的结果，至多6次比较。最后一个元素用二分插入，至多3次比较。

2次比较怎么能排序3个数？