数据结构：递增排列的数组 union all 算法 2.1

递增排列的数组 union all

假设有2个线性表，递增排列的数组，如

char a[20]="abbcopqtuwz";

char b[20]="bcfgjmtv";

我们需要实现一个union all，将两个字符串中的字符合并到

一个新的线性表c中，其中也是按照递增排列的。

那么按照我们要求输出应该为

abbbccfgjmopqttuvwz

那么算法如下：

点击(此处)折叠或打开

#include<stdio.h>

#include <string.h>

int main(void)

{

        char a[20]="abbcopqtuwz";

        char b[20]="bcfgjmtv";

        char c[30];

        memset(c,0,30);

        int n=0;

        int m=0;

        int h=0;

        int a_len=strlen(a);

        int b_len=strlen(b);

        while(n<a_len && m<b_len)

        {

                if(a[n]< b[m])

                {

                        c[h]=a[n];

                        n++;

                }

                else if(a[n]==b[m])

                else

                        c[h]=b[m];

                        m++;

                h++;

        }

        if(a[n] != 0)

                while(n<a_len)

                        h++;

        if(b[m] != 0 )

                while(m<b_len)

        printf("%s\n",c);

}

运行程序输出为：abbbccfgjmopqttuvwz

可以看到和预期一模一样。

分析这个算法的渐进时间复杂度，实际上我们发现他只是一个单循环，很明显我们原操作只是c[h]=a[n];这样的复制

所以时间复杂度为：

T(n)=O(n)

但是这样的算法明显依赖于两个数组排序好了的情况