北理工45. 【字符】合并字符串

45. 【字符】合并字符串

输入两个已经按从小到大顺序排列好的字符串，编写一个合并两个字符串的函数，使合并后的字符串，仍然是从小到 大排列。

输入：
            两个已经排好顺序（升序）的两个字符串

输出：
            一个合并在一起的有序（升序）的字符串

要求：
            设计一个效率尽量高的算法，对每个字符串只扫描一遍就可以了。
            如果采用先进行串连接，然后再进行排序的算法，则效率太低了。

代码如下：

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#define SIZE 20
int main(void)
{
    /*此题的特殊之处在于输入的数据都已经排序过了
    * 之前有一题名为火锅火锅与火锅，涉及到分治法
    * 那么这道题就可以用分治思想来解决了
    * 首先读取长度，len1,len2,令start1 = start2 = 0
    * 比较arr1[start1] 与 arr2[start2],输出较小的一个
    *   如果start1小，那么start1++
    *   while(start1<len1 || start2<len2)
    * 剩下的直接输出
    */
    char arr1[SIZE] = { 0 };
    char arr2[SIZE] = { 0 };
    gets(arr1), gets(arr2);
    int len1 = strlen(arr1), len2 = strlen(arr2);
    int start1 = 0, start2 = 0;
    while (start1 < len1 && start2 < len2) {
        if (arr1[start1] < arr2[start2]) 
            putchar(arr1[start1++]);         
        else if (arr1[start1] == arr2[start2]) {
            putchar(arr1[start1++]);
            putchar(arr2[start2++]);            
        }else
            putchar(arr2[start2++]);
    }
    if (start1 == len1)
        while (start2 < len2)
            putchar(arr2[start2++]);
    else if (start2 == len2)
        while (start1 < len1)
            putchar(arr1[start1++]);
    putchar('\n');
    return 0;
}