百度笔试题请教
问题1：
任何一个基于“比较”的内部排序的算法，若对6个元素进行排序，则在最坏情况下所需的比较次数至少为：_____
A.10 B. 11 C. 21 D.36
我认为最坏情况，肯定就是逆序了，如6,5,4,3,2,1，但此时冒泡法、简单选择法和直接插入法都得用到1+2+3+4+5=15次啊 11次和21次怎么来的啊，答案是什么呢？请各位大侠详解
问题2：
最坏情况下，合并两个大小为n的已排序列数组所需要的比较次数____
A 2n B 2n-1 C 2n+1 D 2n-2
我假设序列1为1,2,3,4,5 序列2为6,7,8,9,10，我用归并方法考虑，却发现有20多次比较，脑子都糊涂了，请各位大侠详解
[解决办法]
问题2：1,3,5,7,9和2,4,6,8,10 才是最坏情况，比较次数为12,23,34,45,56,67,78,89,910，九次即B 2n-1。
[解决办法]
2楼是对的，你这样想，把这两个数组合并后的结果存入另一个数组中，每比较一次至少会插入一个数，最坏情况就是一次比较只能插入一个数。这样只剩最后一个数的时候，不用比较，所以2*n-1;而且最坏情况满足如下条件：
1两个数组的最后一个元素满足比另一个数组的所有非最后元素大，2两个数组中不存在相等元素。
举例 1,5,8,10,13，与2,3,4,7,12，其中13比2,3,4,7大，12比1,5,8,10大，这样就保证了在两个数组的最后元素进行比较前，前面所有的元素都已经比较过，最后比较的必然是12和13.然后最后剩13直接加入。而且必须没有相等元素，这样不会往第三个表中一次插入2个元素。
[解决办法]
然后第一题要用到第二题的结论。是11次，最坏情况下的最少比较次数很明显是用最坏情况下比较次数最少的排序算法。即合并排序。针对此题，6个元素先分两半，每组三个。比如a1,a2,a3,a4,a5,a6分成（a1,a2,a3,），（a4,a5,a6），（a1,a2,a3）再分成（a1，）（a2,a3）然后（a1）不用再分，（a2,a3）分成（a2），（a3），（a4,a5,a6）情况一样，接下来开始合并。（a2）和（a3）比较1次。然后与（a1）合并，最坏比较2次，一共比较3次后，此部分排序成功，另外一个也一样比较3次排序成功。现在一共比较了6次，接下来就是连个长度为3的有序数组合并，最坏为2*3-1即5次，所以一共11次。
