我的感觉

来源: 于 2009-08-17 16:11:02 [博客] [旧帖] [给我悄悄话] 本文已被阅读：次

排列8个数，如果用merge sort，最少要17次才能保证排好。而2^16>8!
所以怀疑22次不能保证排好。

直观解释就是总有运气好的时候，可以让最后一次比较不重要，而且这种情况还不少（最少占一半），这样这棵树就无法平衡。不知道对不对？