顺序表合并算法一、二、三

用顺序表A和B表示的两个线性表，元素的个数分别为m和n，若表中数据都是由小到大顺序排列的，且这（m+n）个数据中没有重复的。那么

（1）设计一个算法将此两个线性表合并成一个，仍是数据由小到大排列的线性表，存储到另一个顺序表C中

（2）如果顺序表B的大小为（m+n）个单元，是否可以不利用顺序表C而将合并成的线性表存放于顺序表B中？

（3）设顺序表A有m+n个元素，且前m个有序，后n个有序，设计一个算法，使得整个顺序表有序。

解：（1）用i和j分别扫描顺序表A和B，比较它们的当前元素，将较小者复制到顺序表C中，这一过程循环到其中的一个顺序表扫描完毕为止。将另一个顺序表与小的元素全部复制到顺序表C中:

void merge1(Sqlist *A,Sqlist *B,Sqlist *C)
{
    int i=0,j=0,k=0;
    while(i<A->length && j<B->length)
    {
        if(A->data[i]<B->data[j])
            C->data[C->length++]=A->data[i++];
        else
            C->data[C->length++]=B->data[j++];
    }
    while(i<A->length)
        C->data[C->length++]=A->data[i++];
    while(j<B->length)
        C->data[C->length++]=B->data[j++];
}

（2）可以，将顺序表A中较小的元素插入到B中即可：

void merge2(Sqlist *A,Sqlist *B)
{
    int i=0,j=0;
    int k;
    while(i<A->length)
    {
        if(A->data[i]>B->data[B->length-1])
            B->data[B->length]=A->data[i++];
        else if(A->data[i]<B->data[j])
        {
            for(k=B->length;k>j;--k)
                B->data[k]=B->data[k-1];
            B->data[j]=A->data[i];
            B->length++;
            j++;
            i++;
        }
        else
            j++;
    }
}

（3）后n个元素插入到前m个元素中就行了

void merge3(Sqlist *A,int m,int n)
{
    int j=m;
    int i=0;
    int k;
    int temp;
    while(j<A->length)
    {
        if(A->data[j]>A->data[j-1])//如果直接比前面的大，那么后面的元素就不需要考虑了，肯定比前面的都大
            break;
        else if(A->data[j]<A->data[i])
        {
            temp=A->data[j];
            for(k=j-1;k>=i;--k)
                A->data[k+1]=A->data[k];
            A->data[i]=temp;
            i++;j++;
        }
        else
            j++;
    }
}