Question

用C语言编写算法实现将两个递增顺序表合并为一个递增顺序表

Answer 1

1.最容易的办法就是把两个表保存在一个新的表里，然后冒泡排序（就是这么暴力。）
2.不过这个问题用指针实现最方便了。
两个指针分别指着两个递增表：比较指针所指的值大小，将小的那个保存在新的表里，然后将小的那个指针往前走一步。再比较，再保存，再走....直到其中一个表走完，把另一个表剩下的数接在后面。
这样做的好处是原有的两个表的内容不会被修改。因为结果是保存在新的表里的，但是消耗内存。
3.插入排序，同样使用指针比较，把一个表里的数据插到另一个表里。这样省内存，但是被插入的这个表原有的数据就没咯。

Answer 2

bool Merge(SeqList A, SeqList B, SeqList &C)
{    //合并有序顺序表A与B成为一个新的有序顺序表C    
    if(A.length+B.length>C.maxSize)  //大于顺序表的最大长度
            return false;
    int i=0,j=0,k=0;
    while(i<A.length && j<B.length)
    {        //循环，两两比较，小者存入结果表
            if(A.data[i] < B.data[j])
                C.data[k++] = A.data[i++];
            else            C.data[k++]=B.data[j++];
    }
    while(i<A.length)  //还剩一个没有比较完的顺序表
            C.data[k++] =A.data[i++];
    while(j<B.length)
           C.data[k++] = B.data[j++];
    C.length=k；
    return true;
}

Answer 3

bool Merge(SeqList A, SeqList B, SeqList &C)
{ //合并有序顺序表A与B成为一个新的有序顺序表C
if(A.length+B.length>C.maxSize) //大于顺序表的最大长度
return false;
int i=0,j=0,k=0;
while(i<A.length && j<B.length)
{ //循环，两两比较，小者存入结果表
if(A.data[i] < B.data[j])
C.data[k++] = A.data[i++];
else C.data[k++]=B.data[j++];
}
while(i<A.length) //还剩一个没有比较完的顺序表
C.data[k++] =A.data[i++];
while(j<B.length)
C.data[k++] = B.data[j++];
C.length=k；
return true;
}

Answer 4

可参考归并排序算法，它的主要思想就是将长度为1，2，4.。。。2^n的有序表进行合并。或者直接调用stl库的Merge模板

//a,b是初始数组，c是目标数组，n1，n2分别为ab长度
for (int i=0, j=0; i<n1 || j<n2; )
    if ( i<n1 && (j>=n2 || a[i] < b[j])  ) c[i+j] = a[i++];
        else c[i+j] = b[j++];