有序表归并~当将两个长度均为n的有序表A=（a1,a2,…,an）与B=（b1,b2,…,bn）(ai≠bj,1≤i,j≤n)归并为一个有序表C=（c1,c2,…,c2n）时,所需进行的元素比较次数最少可达n,最多可达2n-1.（1）假设有序

Question

有序表归并~
当将两个长度均为n的有序表A=（a1,a2,…,an）与B=（b1,b2,…,bn）(ai≠bj,
1≤i,j≤n)归并为一个有序表C=（c1,c2,…,c2n）时,所需进行的元素比较次数最少可达n,最多可达2n-1.
（1）假设有序表C=（2,4,5,6,7,9）,试举出两组A与B的例子,使它们在归并过程中进行的元素比较次数分别达到最少和最多；
（2）写出一般情况下,使归并所需进行的元素比较次数分别达到最少和最多时,A与B中的元素应满足的条件.

Answer 1

（1）最少 A=（2,4,5）B=(6,7,9) 最多 A=(2,5,7) B=(4,6,9)
（2）最少时满足一个序列中的最大值小于令一个序列中的最小值；
最多时的情况是两个序列在最终的序列中一个取奇数元素,一个取偶数元素.