22、STL算法：排序算法、查找算法、数值算法、修改序列算法、非修改序列算法

STL算法，说白了就是C++标准库给你准备好的一整套"操作数据的工具包"。我个人觉得，这是STL里最值钱的部分。你想想看，不用自己手写冒泡排序、不用自己实现二分查找，直接调函数就完事了。我刚开始学的时候，总觉得这些算法可有可无，直到有一次项目里要处理几十万条数据，自己写的排序跑了一分多钟，换成std::sort后秒出结果……嗯，从那以后我再也不敢小看STL算法了。

22.1 排序算法

排序是日常开发里最常用的操作。STL提供了好几种排序算法，各有各的适用场景。

算法	功能	时间复杂度	我常用的场景
sort	快速排序（平均情况）	O(n log n)	绝大多数排序需求
stable_sort	稳定排序	O(n log n)	需要保持相等元素原始顺序时
partial_sort	部分排序	O(n log k)	只关心前几名时
nth_element	第n大元素	O(n)	找中位数或分位数

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

int main() {
    std::vector<int> data = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    
    // 完整排序
    std::sort(data.begin(), data.end());
    
    // 稳定排序
    std::stable_sort(data.begin(), data.end());
    
    // 只排前3个
    std::partial_sort(data.begin(), data.begin() + 3, data.end());
    
    // 找第5大的元素
    std::nth_element(data.begin(), data.begin() + 4, data.end());
    std::cout << "第5大的元素是: " << data[4] << std::endl;
    
    return 0;
}

22.2 查找算法

查找算法帮你快速定位数据。STL里最常用的就是二分查找和线性查找。

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> sorted = {1, 3, 5, 7, 9, 11, 13};
    
    // 二分查找（要求有序）
    bool found = std::binary_search(sorted.begin(), sorted.end(), 7);
    
    // 返回第一个不小于7的位置
    auto it = std::lower_bound(sorted.begin(), sorted.end(), 7);
    
    // 返回第一个大于7的位置
    auto it2 = std::upper_bound(sorted.begin(), sorted.end(), 7);
    
    // 返回所有等于7的范围
    auto range = std::equal_range(sorted.begin(), sorted.end(), 7);
    
    return 0;
}

22.3 数值算法

数值算法在<numeric>头文件里，专门处理数学计算。说实话，以前我都是自己写循环累加，后来才发现STL早就准备好了。

#include <numeric>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 5};
    
    // 累加
    int sum = std::accumulate(nums.begin(), nums.end(), 0);
    
    // 内积
    std::vector<int> a = {1, 2, 3};
    std::vector<int> b = {4, 5, 6};
    int dot = std::inner_product(a.begin(), a.end(), b.begin(), 0);
    
    // 部分和
    std::vector<int> partial(nums.size());
    std::partial_sum(nums.begin(), nums.end(), partial.begin());
    
    // 相邻差
    std::vector<int> diff(nums.size());
    std::adjacent_difference(nums.begin(), nums.end(), diff.begin());
    
    return 0;
}

22.4 修改序列算法

这类算法会改变容器里的内容。最常用的有copy、transform、replace、fill等。

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

int main() {
    std::vector<int> src = {1, 2, 3, 4, 5};
    std::vector<int> dst(5);
    
    // 复制
    std::copy(src.begin(), src.end(), dst.begin());
    
    // 变换（每个元素乘以2）
    std::transform(src.begin(), src.end(), src.begin(),
                   [](int x) { return x * 2; });
    
    // 替换所有3为99
    std::replace(src.begin(), src.end(), 3, 99);
    
    // 填充
    std::fill(dst.begin(), dst.end(), 0);
    
    return 0;
}

22.5 非修改序列算法

这类算法只读不写，不会改变容器内容。包括find、count、for_each、all_of等。

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

int main() {
    std::vector<int> data = {1, 2, 3, 4, 5, 3, 6, 7};
    
    // 查找第一个3
    auto it = std::find(data.begin(), data.end(), 3);
    
    // 统计3出现的次数
    int cnt = std::count(data.begin(), data.end(), 3);
    
    // 遍历打印
    std::for_each(data.begin(), data.end(),
                  [](int x) { std::cout << x << " "; });
    
    // 检查是否所有元素都大于0
    bool all_positive = std::all_of(data.begin(), data.end(),
                                    [](int x) { return x > 0; });
    
    return 0;
}

22.6 知识体系总览

下面这张图帮你理清STL算法的整体脉络。我建议你把它存下来，写代码时对照着看。

22.7 实战建议

学完这些算法，我建议你记住一个原则：能用STL算法就别自己写循环。原因有三：

• 性能有保障——STL算法的实现经过高度优化，比自己手写的循环快得多
• 代码更简洁——一行算法调用顶得上十几行手写代码
• 可读性更好——std::sort一眼就知道是排序，而手写快排还得看半天