合并两个有序序列

• 前言
• 1、方法1——先合并再冒泡排序
• 2、方法2——数组元素一一比较
• 3、方法3——动态内存空间版
• 总结

---

前言

第一行包含两个正整数n, m，用空格分隔； n表示第二行第一个升序序列中数字的个数； m表示第三行第二个升序序列中数字的个数
第二行包含n个整数，用空格分隔
第三行包含m个整数，用空格分隔

输出描述：

• 输出为一行，输出长度为n+m的升序序列
• 即长度为n的升序序列和长度为m的升序序列中的元素重新进行升序序列排列合并

输入：
5 6
1 3 5 7 9 
0 2 4 6 8 10
输出：
0 1 2 3 4 5 6 7 8 9 10

---

1、方法1——先合并再冒泡排序

方法1 显示利用数组开辟空间，再将两个数组合并后，通过冒泡排序算法进行排序：

• 在C语言基础阶段中 【C语言基础5——数组（1）】4、数组作为函数参数 已经详细学过冒泡排序算法了

• 在C语言进阶阶段中【C语言进阶11——字符和字符串函数及其模拟实现（2））7、内存操作函数】 已经详细学过库函数了

方法1的思路见下图：

void bubble_sort(int* arr, int sz)
{
	//排序坐外面的大循环次数
	int i = 0;
	for (i = 0; i < sz - 1; i++)
	{
		int flag = 1;//状态机标志位，代表数组本身元素就是从小到大排序的
		int j = 0;
		for (j = 0; j < sz - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				flag = 0;//只要有一个地方需要排序，就置零
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
		if (1 == flag)
		{//第一轮排序结果都是1，说明没有地方需要排序
			break;//直接跳出后面的循环，不需要再排序了
		}
	}
}
int main()
{
	int m = 0;//数组a的个数
	int n = 0;//数组b的个数
	int i = 0;
	int j = 0;

	scanf("%d%d", &m, &n);
	int a[1000];
	int b[1000];

	//输入第一个数组
	for (i = 0; i < m; i++)
	{
		scanf("%d", &a[i]);
	}

	//输入第二个数组
	for (j = 0; j < n; j++)
	{
		scanf("%d", &b[j]);
	}
	memcpy(a+m, b, n*4);//利用了库函数
	//可以将合并后的数组打印出来看看
	//for (int i = 0; i < m+n; i++)
	//{
	//	printf("%d ", a[i]);
	//}
	bubble_sort(a, m+n);//冒泡排序的函数，
	i = 0;
	for (i = 0; i < m + n; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}

结果见下图所示：

在【初阶数据结构与算法 1】时间复杂度与空间复杂度（1）2.3.5 练习5 中，已经详细学习过冒泡算法的时间复杂度为 O(N^2)。

因此将在方法1 的基础上进行优化。

2、方法2——数组元素一一比较

将两个序列的元素一一比较，按顺序直接打印出来。方法2 的思路见下图：

int main()
{
	int m = 0;//数组a的元素个数
	int n = 0;//数组b的元素个数
	int i = 0;
	int j = 0;
	scanf("%d%d", &m, &n);
	int a[1000];//定义数组a
	int b[1000];//定义数组a

	//输入第一个数组
	for (i = 0; i < m; i++)
	{
		scanf("%d", &a[i]);
	}

	//输入第二个数组
	for (j = 0; j < n; j++)
	{
		scanf("%d", &b[j]);
	}
	i = 0;//再次初始化
	j = 0;
	while (i < m && j < n)
	{
		if (a[i]<b[j])
		{
			printf("%d ", a[i]);
			i++;
		}
		else
		{
			printf("%d ", b[j]);
			j++;
		}
	}
	if (i==m)//此时数组a的值都已经打印出来了
	{
		for(;  j< n; j++)//数组b剩下的元素想直接打印出来就行了
		{
			printf("%d ", b[j]);
		}
	}

	if (j == n)//此时数组b的值都已经打印出来了
	{
		for (; i < m; i++)//数组a剩下的元素想直接打印出来就行了
		{
			printf("%d ", a[i]);
		}
	}
	return 0;

}

结果见下图所示：

方法2的时间复杂度为 O(m+n).

3、方法3——动态内存空间版

在C语言进阶阶段 【C语言进阶13——动态内存管理】 已经学习了动态内存开辟空间相比数组的优势了，方法3 利用动态内存空间和库函数，开辟所需空间大小，不浪费空间：

方法3的思路见下图：

//动态内存版
int main()
{
	int m = 0;//数组a的个数
	int n = 0;//shuzub的个数
	int i = 0;
	int j = 0;
	scanf("%d%d", &m, &n);
	
	int *pa = (int*)malloc((m + 1) * sizeof(int));//开辟有序序列合并的数组空间
	int *pb = (int*)malloc((n + 1) * sizeof(int));//开辟有序序列合并的数组空间
	if (pa == NULL)
	{
		perror("malloc: ");
		return;
	}
	if (pb == NULL)
	{
		perror("malloc: ");
		return;
	}
	//输入第一个数组
	for (i = 0; i < m; i++)
	{
		scanf("%d", pa+i);
	}

	//输入第二个数组
	for (j = 0; j < n; j++)
	{
		scanf("%d", pb+j);
	}
	i = 0;//再次初始化
	j = 0;
	
	while (i<m && j<n)
	{
		if (*(pa + i) < *(pb + j))
		{
			printf("%d ", *(pa + i));
			i++;
		}
		else
		{
			printf("%d ", *(pb + j));
			j++;
		}
	}
	if (i == m)//此时数组a的值都已经打印出来了
	{
		for (; j < n; j++)//数组b剩下的元素想直接打印出来就行了
		{
			printf("%d ", *(pb + j));
		}
	}

	if (j == n)//此时数组b的值都已经打印出来了
	{
		for (; i < m; i++)//数组a剩下的元素想直接打印出来就行了
		{
			printf("%d ", *(pa + i));
		}
	}
	
	free(pa);
	free(pb);
	pa = NULL;
	pb = NULL;
	return 0;
}

结果见下图所示：

---

总结

C语言还需要多练习，不管自己写的代码是罗嗦了，还是太烂了，也必须要写完，大胆实现自己的想法，实现题目要求，这是最重要的一步。

第二步就是多看看别人写的代码，学习别人的思路，记录下来写成博客，方便自己复习。

熟能生巧！