有序顺序表合并有顺序表A和B.其元素均按从小到大的升序排列,编写一个算法将它们合并成一个新的顺序表C,要求C的元素也是从小打到升序排列.算法思路：依次扫描A和B的元素,比较当前元素

Question

有序顺序表合并
有顺序表A和B.其元素均按从小到大的升序排列,编写一个算法将它们合并成一个新的顺序表C,要求C的元素也是从小打到升序排列.
算法思路：依次扫描A和B的元素,比较当前元素的值,将较小值的元素赋给C,如此直到一个线性表扫描完毕,然后将未完的那个顺序表中余下的部分赋给C即可.C的大小要能容纳A、B两个线性表相加的长度.
求解析一下这个算法思路,将未完的那个顺序表中余下的部分赋给C,已经完了的顺序表里面比未完的顺序表大的元素要怎么处理?

Answer 1

在合并的时候,每一次复制到C表中的元素都是A、B表中当前元素中较小的一个,所以,如果A或B中的一个已经全部合并到C,那么另一个表中剩下的元素大于等于已合并完的表中的最大元素.
或者这么说,假设已经完成的表中的最末元素比未完成表中的当前元素大,那么,按照合并规则,这个最末元素应该比另一张表中小于它的元素后合并入新表.因此,假设是不成立的.