为什么 合并两个长度分别为m和n的有序表，最坏情况下需要比较m＋n－1次？数据结构的一道题。

Question

如题所述

Answer 1

我补充一下过程示例：
设上链指针p，下链q，每次比较后较小节点依次作为“合并后链表的节点”，同时较小链指针后移。某链指空后不再比较。则楼上所给的第一个例子：第一步：1和2比，1小作为新节点，p移至3。第二步，3和2比，2小作为新节点，q移至4。第三步，3和4比，3小，p移至5。第四步，5和4比，4小，q移至6。第五步，5和6比，p指空。结束。
最坏的情况实质上是让两指针都走完各自的链表，同时某链肯定先走完，因为一次只移动一个指针，另一个链表无论怎样都会至少少走一步，这就是m+n-1的含义。

Answer 2

问：长度分别为m和n的有序表A，B，合并过程中最坏的比较次数为什么是m+n-1。

答：

无论你的有序表使用数组还是链表存储，合并有序表的方法通常使用双指针法。合并的结果要产生新表C，它包含表A、B的所有元素，并且顺序和表A、B一致。因此讨论比较次数乃至最坏比较次数要建立在理解双指针法的基础上，最高赞的答案已经给出了流程，这里不再赘述。

这里给出更一般的结论——最差的情况是所有元素都比较过。每比较一次就往表C里放一个元素，也就是说排完m+n-1个元素比较了m+n-1次。那还剩最后一个元素怎么办？很简单，最后一个元素直接放到表C的表尾就可以了。所以总共是m+n-1次。

举一个例子，假设有序表为升序。长度为m的有序表的前m-1个元素都小于长度为n的有序表的第1个元素，第m个元素大于长度为n的有序表的n个元素（即所有元素），这样比较次数就是m-1+n。

Answer 3

最坏的情况就是交叉如：
1 3 5
2 4 6
与
1 3 5 7 9
2 4 8本回答被提问者和网友采纳