C++标准模板库（STL）algorithm算法库

陈一男学习网站[ ChenYinan.com ] - CCF - NOI - 菜鸟教程 - 编程题库 - C++语言 - API

在C++中，<algorithm>头文件提供了一系列非常有用的算法，以下是一些主要方面的介绍：

一、排序算法

1. std::sort

功能：对给定范围内的元素进行快速排序（通常是 introsort，一种混合排序算法，结合了快速排序、堆排序和插入排序的优点）。

#include <algorithm>
#include <vector>
#include <iostream>
int main() {
    std::vector<int> v = {5, 2, 8, 1, 9};
    std::sort(v.begin(), v.end());
    for (int num : v) {
        std::cout << num << " ";
    }
    return 0;
}

时间复杂度：平均为 $O(nlogn)$，最坏情况为 $O(n^2)$，不过在实际应用中表现良好。

2. std::stable_sort

功能：对给定范围内的元素进行稳定排序。稳定排序意味着相等元素的相对顺序在排序前后保持不变。

std::vector<int> v = {5, 2, 8, 1, 9};
std::stable_sort(v.begin(), v.end());

时间复杂度：通常为 $O(nlog^2n)$，但对于一些特殊情况（如接近有序的数据）可能有更好的性能。

二、搜索算法

1. std::find

功能：在给定范围内查找指定元素。

std::vector<int> v = {5, 2, 8, 1, 9};
auto it = std::find(v.begin(), v.end(), 8);
if (it!= v.end()) {
    std::cout << "Element found";
} else {
    std::cout << "Element not found";
}

时间复杂度：平均为 $O(n)$，其中n是范围的大小。

2. std::binary_find

功能：在有序范围内使用二分查找算法查找指定元素。不过要注意，标准库中没有名为std::binary_find的函数，但可以通过自定义或者使用std::lower_bound和std::upper_bound来实现类似功能。

std::lower_bound用于在有序的序列（如数组、vector等）中查找第一个不小于（大于等于）给定值的元素的位置。

std::vector<int> v = {1, 2, 3, 4, 5};
auto it = std::lower_bound(v.begin(), v.end(), 3);
if (it!= v.end() && *it == 3) {
    std::cout << "Element found";
} else {
    std::cout << "Element not found";
}

std::upper_bound用于在有序序列（如数组、vector等）中查找第一个大于给定值的元素的位置。

#include <iostream>
#include <algorithm>
int main() {
    int arr[] = {1, 3, 5, 5, 7, 9};
    int* it = std::upper_bound(arr, arr + 6, 5);
    std::cout << "The position of the first element greater than 5 is: " << (it - arr) << std::endl;
    return 0;
}

时间复杂度：$O(logn)$，其中n是范围的大小。

三、变换算法

1. std::transform

功能：对给定范围内的元素应用一个函数，并将结果存储在另一个范围（可以是相同的范围）中。

std::vector<int> v = {1, 2, 3, 4, 5};
std::vector<int> result(v.size());
std::transform(v.begin(), v.end(), result.begin(), [](int x) { return x * 2; });

时间复杂度：$O(n)$，其中n是范围的大小。

四、数值算法（<numeric>头文件中的部分相关算法）

1. std::accumulate

功能：计算给定范围内元素的总和（或者自定义的二元操作的累积结果）。

std::vector<int> v = {1, 2, 3, 4, 5};
int sum = std::accumulate(v.begin(), v.end(), 0);

时间复杂度：$O(n)$，其中n是范围的大小。

C++编程语言基础