前言

第一行包含两个正整数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
2
3
4
5
6

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

结果见下图所示：

在【初阶数据结构与算法 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;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

结果见下图所示：

方法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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

结果见下图所示：

总结

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

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

熟能生巧！