【C语言指南】合并两个有序数组
【摘要】 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
目录
一、问题描述
（注意认真读题）
二、解题思路
1.合并+排序：思路简单，效率低
这是最容易想到的一种方式，先把数组2中的元素都移动到数组1的空闲位置上
再通过任意一种排序方式对数组1进行排序
2.双指针（双变量）方式：实现简单，效率高
这种方式对逻辑要求严谨一点，但是只要想到了，实现起来一点也不复杂，并且效率很高
- 因为数组的大小不是明确的，所以不能额外创建一个数组，而数组1中留足了可供数组2中元素移动过来的位置，那么将数组2中的元素移动过来是最合适的
- 分别创建两个变量，指向数组1和数组2中有效元素的尾部，这两个变量起到了指针的作用。再创建一个变量指向数组1的尾部，从后往前依次放入较大的元素
- 每次将数组1和数组2的尾部元素进行比较，将较大值放入数组1当前可用的尾部空间
- 当两个变量任意一个走到小于0时，跳出循环（此时说明数组1或数组2中的待排序元素已被放置完毕，而这里只需要处理数组2中还有元素未处理的情况。如果数组2中元素处理完数组1未处理完，此时数组1全部元素是有序的）将数组2中的剩余元素依次放置到数组1中即可
三、源代码
1.合并+排序方式代码
void merge(int* nums1, int m, int* nums2, int n)
{
int i = 0;
int j = 0;
for (i = m ; i < m + n; i++)//将数组2的数据复制到数组1中
{
nums1[i] = nums2[j++];
}
for (i = 0; i <m+n-1 ; i++)//冒泡排序
{
for(j=0;j<m+n-i-1;j++)
if (nums1[j] > nums1[j+1])
{
int temp = nums1[j];
nums1[j] = nums1[j+1];
nums1[j+1] = temp;
}
}
}2.双指针（双变量）方式代码
void merge(int* nums1, int m, int* nums2, int n)
{
int i = m - 1;
int j = n - 1;
int k = m + n - 1;
while (i >= 0 && j >= 0)
{
if (nums1[i] > nums2[j])
{
nums1[k--] = nums1[i--];
}
else {
nums1[k--] = nums2[j--];
}
}
while (j>=0)//出循环时，只需要对数组2中剩余的元素进行处理
{
nums1[k--] = nums2[j--];
}
}
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）