oj 合并有序序列

灰太狼 2023-10-05 14:24 20阅读 0赞

#### 合并有序序列 ####

Time Limit: 1000/1000MS (C++/Others) Memory Limit: 65536/65536KB (C++/Others)

Problem Description

有两个已排序好的序列A（长度为n1），B（长度为n2），将它们合并为一个有序的序列C（长度为n=n1+n2)。0 < n1,n2 < 1000。

Input

输入有多组测试数据，每组占两行，第一行为A序列（均为正整数），最后为-1，表示结束。第二行为B序列（均为正整数），最后为-1，表示结束。

Output

输出合并后的序列C，每组占一行。

Sample Input

1 3 8 9 11 -1
    2 5 7 10 13 -1

Sample Output

1 2 3 5 7 8 9 10 11 13

解法：

思路1：使用归并排序的思想，将两个有序数组合并成一个有序数组，时间复杂度o(n),空间复杂度o(n)

思路2：插入排序，将其中一个数组作为基准，然后遍历该基准数组，将另一个数组的每个元素插入到基准数组的正确位置。最后的到一个有序数组；时间复杂度o(n2)，空间复杂度o(1)

我这里采用的思路1，归并排序的思想。

**C语言源码：**

#include<stdio.h>
    #define max 1001
    int c[3002];
    int* merge(int a[],int t,int b[],int v){  //归并排序
      int i=0,j=0,k=0;
      while(i<t&&j<v){
    	  if(a[i]<b[j]){
    		 c[k++]=a[i];
    		 i++;
    	  }
    	  else{
    	     c[k++]=b[j];
    	     j++;
    	  }
      }
      while(i<t){
        c[k++]=a[i];
    	i++;
      }
      while(j<v){
        c[k++]=b[j];
    	j++;
      }
      return c;
    }
    
    int main(){
    	int a[max];
    	int b[max];
    	int *c;
    	int temp,temp1,i=0,j=0,m,n;
    
    	while(scanf("%d",&temp)!=EOF){  //多组输入
    		while(temp!=-1){
    			a[i++]=temp;
    			scanf("%d",&temp);
    			m=i;
    		}
            temp1=temp;  //去掉-1
    		scanf("%d",&temp);	
    		while(temp!=-1){
    		    b[j++]=temp;
    			scanf("%d",&temp);
    			n=j;
    		}
    		temp1=temp;
            c=merge(a,m,b,n);
    		for(int k=0;k<m+n;k++){
    		  printf("%d",c[k]);
    		  if(k<m+n-1)
    		  printf(" ");
    		}
    		printf("\n");
    		i=0;
    		j=0;
    	}
    	return 0;
    
    }