c++中如何合并两个已排序数组_c++合并有序数组方法-C++-PHP中文网

c++中如何合并两个已排序数组_c++合并有序数组方法

冰火之心

发布： 2025-09-26 15:08:01

原创

315人浏览过

合并两个已排序数组的常用方法包括：①双指针法，通过比较两数组元素逐个插入新数组；②原地合并，从后往前填充避免覆盖，适用于空间受限场景；③使用std::merge标准库函数，代码简洁高效。三种方法均能实现有序合并，时间复杂度为O(m+n)，可根据需求选择。

c++中如何合并两个已排序数组_c++合并有序数组方法

在C++中合并两个已排序的数组是一个常见问题，通常出现在算法题或实际开发中的数据处理场景。目标是将两个升序（或降序）排列的数组合并成一个同样有序的新数组。以下是几种常用且高效的实现方法。

使用双指针法合并有序数组

这是最经典的方法，适用于两个已按升序排列的数组。通过维护两个指针分别指向两个数组的起始位置，逐个比较元素大小，将较小的元素放入结果数组中。

假设我们要将数组 nums1 和 nums2 合并为一个有序数组，可以这样做：

定义两个指针 i 和 j，初始都指向各自数组的开头
创建一个新数组 result 存放合并后的结果
循环比较 nums1[i] 和 nums2[j]，把较小的加入 result，并移动对应指针
当其中一个数组遍历完后，把另一个数组剩余元素全部追加到 result

示例代码：

立即学习“C++免费学习笔记（深入）”；

#include <vector>
using namespace std;
<p>vector<int> mergeSortedArrays(vector<int>& nums1, vector<int>& nums2) {
vector<int> result;
int i = 0, j = 0;</p><pre class='brush:php;toolbar:false;'>while (i < nums1.size() && j < nums2.size()) {
    if (nums1[i] <= nums2[j]) {
        result.push_back(nums1[i]);
        i++;
    } else {
        result.push_back(nums2[j]);
        j++;
    }
}

while (i < nums1.size()) {
    result.push_back(nums1[i]);
    i++;
}

while (j < nums2.size()) {
    result.push_back(nums2[j]);
    j++;
}

return result;

登录后复制

}

原地合并（适用于LeetCode类型题目）

在某些题目中（如 LeetCode 88），要求将第二个数组合并到第一个数组中，且 nums1 的空间足够大（末尾有足够空位）。此时可以从后往前填充，避免覆盖原始数据。

序列猴子开放平台

具有长序列、多模态、单模型、大数据等特点的超大规模语言模型

查看详情

关键思路：从两个数组的有效末尾开始比较，将较大的数放在 nums1 的最后空位。

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int i = m - 1; // nums1 有效元素末尾
    int j = n - 1; // nums2 末尾
    int k = m + n - 1; // nums1 总长度末尾
<pre class='brush:php;toolbar:false;'>while (i >= 0 && j >= 0) {
    if (nums1[i] > nums2[j]) {
        nums1[k--] = nums1[i--];
    } else {
        nums1[k--] = nums2[j--];
    }
}

while (j >= 0) {
    nums1[k--] = nums2[j--];
}

登录后复制

}

这种方法时间复杂度 O(m+n)，空间复杂度 O(1)，适合对空间有要求的场景。

使用标准库函数合并

C++ 标准库提供了 std::merge 算法，可以直接用于合并两个有序序列。

#include <algorithm>
#include <vector>
<p>vector<int> mergeWithSTL(vector<int>& nums1, vector<int>& nums2) {
vector<int> result(nums1.size() + nums2.size());
merge(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), result.begin());
return result;
}</p>

登录后复制

std::merge 内部也是基于双指针思想实现，代码简洁，推荐在工程中使用以提高可读性和可靠性。

基本上就这些。根据具体需求选择合适的方法：追求效率用双指针，节省空间用从后往前合并，注重代码简洁可用 std::merge。

以上就是c++++中如何合并两个已排序数组_c++合并有序数组方法的详细内容，更多请关注php中文网其它相关文章！