C++常用算法

C++标准库（STL）提供了丰富的算法，涵盖排序、查找、数值计算等场景。以下分类介绍常用算法及示例：

---

排序算法

std::sort
基于快速排序的混合算法（Introsort），时间复杂度为 O(n log n)。

#include <algorithm>
#include <vector>
std::vector<int> vec = {4, 2, 5, 1, 3};
std::sort(vec.begin(), vec.end()); // 默认升序

std::stable_sort
稳定排序，保持相等元素的相对顺序，适合复杂对象。

std::stable_sort(vec.begin(), vec.end(), [](int a, int b) {
    return a % 2 < b % 2; // 偶数在前
});

---

查找算法

std::find
线性查找，返回第一个匹配的迭代器。

auto it = std::find(vec.begin(), vec.end(), 3);
if (it != vec.end()) std::cout << "Found: " << *it;

std::binary_search
二分查找（需先排序），返回是否存在。

bool exists = std::binary_search(vec.begin(), vec.end(), 5);

std::lower_bound
返回第一个不小于目标的迭代器。

auto lb = std::lower_bound(vec.begin(), vec.end(), 3);

---

数值算法

std::accumulate
累加或自定义聚合操作。

#include <numeric>
int sum = std::accumulate(vec.begin(), vec.end(), 0);
int product = std::accumulate(vec.begin(), vec.end(), 1, [](int a, int b) {
    return a * b;
});

std::transform
对范围中的元素应用函数。

std::vector<int> squared(vec.size());
std::transform(vec.begin(), vec.end(), squared.begin(), [](int x) {
    return x * x;
});

---

修改序列算法

std::copy
复制范围到目标位置。

std::vector<int> dest(vec.size());
std::copy(vec.begin(), vec.end(), dest.begin());

std::remove_if
移除满足条件的元素（逻辑删除，需配合erase）。

vec.erase(std::remove_if(vec.begin(), vec.end(), [](int x) {
    return x % 2 == 0; // 删除偶数
}), vec.end());

---

堆算法

std::make_heap
将范围转换为最大堆。

std::make_heap(vec.begin(), vec.end());
vec.push_back(6);
std::push_heap(vec.begin(), vec.end()); // 调整堆

---

其他实用算法

std::reverse
反转序列。

std::reverse(vec.begin(), vec.end());

std::unique
去除相邻重复元素（需先排序）。

vec.erase(std::unique(vec.begin(), vec.end()), vec.end());

std::nth_element
部分排序，使第n个元素处于正确位置。

std::nth_element(vec.begin(), vec.begin() + 2, vec.end());

---

注意事项

• 算法多位于<algorithm>和<numeric>头文件。
• 自定义比较函数时，确保满足严格弱序（如a < b而非a <= b）。
• 算法通过迭代器操作，不直接修改容器大小（如remove需配合erase）。

通过灵活组合这些算法，可高效处理大多数数据操作需求。