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

用順序表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++;
    }
}