合并两个有序序列

问题描述

合并两个有序线性表，合并后仍有序。

分析与思考

结构：线性结构

存储结构：顺序存储结构和链式存储结构都可

方法实现

法一：

1.将两组数据存入一个数组中，直接sort

2.将两组数据存入一个链表中，对链表进行排序

法二：

1.分别存储在两个数组La,Lb中

2.逐个进行比较，小的那者存入新数组Lc中

3.某一个数组遍历完后，另一组数组没有与之进行对比的数据

4.将多余部分直接存入新数组Lc中

核心部分代码实现

int i,j;
int len_a=sizeof(La)/sizeof(La[0]);
int len_b=sizeof(Lb)/sizeof(Lb[0]);
for(i=0,j=0;i<len_a&&j<len_b;)
{
  if(La[i]<=Lb[j])
  {Lc[index++]=La[i];++i;}
  else
  {Lc[index++]=Lb[j];++j;}
}
while(i<len_a) {Lc[index++]=La[i];++i;}
while(j<len_b) {Lc[index++]=Lb[j];++j;}

法三

1.使用链表实现

2.创建链表，把数据存入链表中

3.使用递归，实现链表合并

（1）如果某一个链表为空，直接返回另一个链表

（2）如果list1 -> val <= list2 -> val

保留 list1 -> val

将list1 -> next和 list2 进行合并，返回值赋值给list1->next

核心部分代码实现

Node* merge1(Node *list1,Node* list2)
{
	if(!list1->next) return list2;
    if(!list2->next) return list1;
    if(list1->val<=list2->val) 
    {
        list1->next=merge1(list1->next,list2);
        return list1;
    }
    else
    {
        list2->next=merge1(list1,list2->next);
        return list2;
    }	
}

法四

1.使用链表实现

2.把数据存入两个链表中

3.使用迭代实现

判断list1 和list2的头结点大小，将较小者存入结果中，对应链表的结点往后移一位

核心部分代码实现

Node* merge2(Node* list1,Node* list2)
{
	Node* List=(Node*)malloc(sizeof(Node));
	Node* cur=List;
	while(list1&&list2)
	{
		if(list1->val<=list2->val)
		{
			cur->next=list1;
			list1=list1->next;
		}
		else
		{
			cur->next=list2;
			list2=list2->next;
		}
		cur=cur->next;
	}
	if(!list1) cur->next=list2;
	if(!list2) cur->next=list1;
	return List->next;
}

法五

1.把两个链表连接起来

2.排序

核心部分代码实现

Node* merge3(Node* list1,Node* list2)
{
	Node* p=list1;
	while(p->next)
	{
		p=p->next;
	}
	p->next=list2->next;
	return list1;
}

void my_sort(Node* list)
{
	for(Node* i=list;i;i=i->next)//冒泡排序
	{
		for(Node* j=list;j->next;j=j->next)
		{
			if(j->val>(j->next->val))
			{
				int temp=j->val;
				j->val=j->next->val;
				j->next->val=temp;
			}
		}
	}
}

分析

法二的时间复杂度为 O(max(n,m))

法三、法四的时间复杂度 O(n+m) ,

其中 n,m分别为list1和list2的长度