数据结构二路归并刷题

Question

题:设有两个长度分别为m 、n 的降序有序序列{a 1，a 2，…，a m )、{b 1，b 2，…，b n )，采用二路归并方法将它们合并成长度为m+12的降序有序序列，则归并过程中元素比较次数最少的条件一定是
答案是:
请问为什么是a1<bn啊？ 如何推导呢?

Answer 1

a1 < bn时 b 中所有元素都大于 a，所以只需要由 a1 和 b中每个元素比较一次，然后将a中元素都追加都后面，得到新的序列 b1, b2, ..., bn, a1, a2, ..., an。比较次数为n次。其实b1 < am也可以，这时比较次数是m，要看m和n哪个点。

因为这样重复比较次数是最少的。看看2个数序列的一般情况：

a1 a2 
b1 b2

• 先比较a1,b1，如果b1较大，b1放到结果序列中，a1保留
• 再a1于b2比较，a1较大，a1放到结果序列中，b2保留
• 然后a2和b2比较。。。。

比较了3次，a和b才向前移动了2位，但是上面是比较多少次就能移动多少位。

Answer 2

其实条件可以是：a1 < bn 或 b1 < an

因为：

• 由于 a 是降序有序序列，所以，a1 是 a 中的最大值，an 是 a 中的最小值
• 同理，由于 b 是降序有序序列，所以，b1 是 b 中的最大值，bn 是 b 中的最小值

如果 a1 < bn，说明，a 中的最大值，都比 b 的最小值小，所以只需将 a 中的元素依次放在 bn 之后即可，总共比较了一次

同理，如果 b1 < an，说明，b 中的最大值，都比 a 的最小值小，所以只需将 b 中的元素依次放在 an 之后即可，总共比较了一次