c++中如何在有序数组中插入元素_c++有序数组插入元素方法-C++-PHP中文网

c++中如何在有序数组中插入元素_c++有序数组插入元素方法

尼克

发布： 2025-10-13 21:24:29

原创

750人浏览过

在C++中向有序数组插入元素需先找插入位置再插入，常用std::vector配合循环或std::lower_bound查找，后者效率更高；频繁插入时推荐std::set自动维护有序性。

c++中如何在有序数组中插入元素_c++有序数组插入元素方法

在C++中，向有序数组插入元素需要保证插入后数组仍然保持有序。由于普通数组大小固定，通常使用std::vector来实现动态插入操作。核心思路是：找到合适的插入位置，然后将元素插入到该位置。

使用 std::vector 和手动查找插入位置

可以通过循环遍历找到第一个大于等于目标值的位置，然后使用insert()方法插入元素。

遍历数组，寻找插入点
使用vector::insert(iterator, value)插入元素

示例代码：

有道小P

有道小P，新一代AI全科学习助手，在学习中遇到任何问题都可以问我。

查看详情

#include <iostream>
#include <vector>

void insertSorted(std::vector<int>& arr, int value) {
    auto it = arr.begin();
    while (it != arr.end() && *it < value) {
        ++it;
    }
    arr.insert(it, value);
}

int main() {
    std::vector<int> sorted = {1, 3, 5, 7, 9};
    insertSorted(sorted, 6);

    for (int n : sorted) {
        std::cout << n << " ";
    }
    return 0;
}

登录后复制

输出：1 3 5 6 7 9

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

使用 std::lower_bound 快速定位插入位置

std::lower_bound可以在有序序列中查找第一个不小于给定值的位置，效率更高（基于二分查找）。

时间复杂度为 O(log n)，适合大数组
需包含头文件 <algorithm>

示例代码：

#include <iostream>
#include <vector>
#include <algorithm>

void insertSorted(std::vector<int>& arr, int value) {
    auto pos = std::lower_bound(arr.begin(), arr.end(), value);
    arr.insert(pos, value);
}

int main() {
    std::vector<int> sorted = {1, 3, 5, 7, 9};
    insertSorted(sorted, 4);

    for (int n : sorted) {
        std::cout << n << " ";
    }
    return 0;
}

登录后复制

输出：1 3 4 5 7 9

保持有序数组插入的关键点

确保插入前数组已经排序，否则查找位置会出错。

插入前可调用std::sort(arr.begin(), arr.end())预处理
insert()操作的时间复杂度是 O(n)，因为可能移动大量元素
若频繁插入，考虑使用std::set或std::multiset自动维护有序性

例如，用std::set自动排序：

#include <set>
#include <iostream>

int main() {
    std::set<int> ordered;
    ordered.insert(5);
    ordered.insert(1);
    ordered.insert(3);

    for (int n : ordered) {
        std::cout << n << " "; // 输出：1 3 5
    }
    return 0;
}

登录后复制

基本上就这些。如果数组规模小，手动插入即可；若插入频繁或数据量大，优先考虑lower_bound或直接使用关联容器。

以上就是c++++中如何在有序数组中插入元素_c++有序数组插入元素方法的详细内容，更多请关注php中文网其它相关文章！