C++标准库算法：核心排序与查找技巧详解

1. C++标准库算法：从入门到精通

作为C++开发者，我们每天都在与各种数据结构和算法打交道。很多人习惯性地使用for循环和if语句来解决所有问题，却忽略了标准库中那些经过千锤百炼的算法工具。<algorithm>头文件就是这样一个宝藏，它包含了100多个函数模板，掌握其中10-15个核心算法就能覆盖90%的日常开发需求。

我第一次意识到标准库算法的威力是在重构一个老项目时。原本需要几十行嵌套循环的复杂数据处理逻辑，用标准算法配合Lambda表达式后，代码量减少了70%，可读性却大幅提升。从那以后，我就养成了"先查标准库，再考虑手写循环"的习惯。

2. 排序与重排类算法

2.1 std::sort：快速排序的瑞士军刀

std::sort是使用最频繁的排序算法，它基于快速排序实现，平均时间复杂度为O(N log N)。与C语言的qsort相比，它是类型安全的模板函数，不需要手动计算元素大小和交换内存。

cpp复制std::vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6};
std::sort(nums.begin(), nums.end());  // 默认升序

自定义排序规则时，可以传入函数对象或Lambda表达式：

cpp复制// 按绝对值排序
std::sort(nums.begin(), nums.end(), [](int a, int b) {
    return std::abs(a) < std::abs(b);
});

注意：std::sort要求迭代器是随机访问迭代器，所以不能用于std::list（应该使用list自带的sort成员函数）

2.2 std::stable_sort：稳定排序的守护者

当需要保持相等元素的原始顺序时，应该使用std::stable_sort。它通常基于归并排序实现，时间复杂度也是O(N log N)，但需要额外内存空间。

cpp复制struct Student {
    std::string name;
    int score;
};

std::vector<Student> students = {{"Alice", 90}, {"Bob", 85}, {"Cathy", 90}};
// 按分数排序，相同分数的保持原有顺序
std::stable_sort(students.begin(), students.end(), 
    [](const Student& a, const Student& b) { return a.score > b.score; });

2.3 std::partial_sort：部分排序的高手

当只需要前N个有序元素时，std::partial_sort比完全排序更高效：

cpp复制std::vector<int> nums = {5, 3, 1, 4, 9, 2, 6};
// 只排序前3个元素，其余保持原样
std::partial_sort(nums.begin(), nums.begin()+3, nums.end());
// nums现在是 {1, 2, 3, 5, 9, 4, 6}

2.4 std::nth_element：快速选择的利器

std::nth_element用于快速找到第n小的元素，并使该元素位于正确位置，左侧都不大于它，右侧都不小于它：

cpp复制std::vector<int> nums = {5, 3, 1, 4, 9, 2, 6};
// 找到中位数
auto mid = nums.begin() + nums.size()/2;
std::nth_element(nums.begin(), mid, nums.end());
std::cout << "中位数是: " << *mid << std::endl;

2.5 std::unique与擦除-移除惯用法

std::unique去除相邻的重复元素，但不会改变容器大小，通常与erase配合使用：

cpp复制std::vector<int> nums = {1, 1, 2, 2, 2, 3, 4, 4, 5};
auto last = std::unique(nums.begin(), nums.end());
nums.erase(last, nums.end());  // 现在nums是{1, 2, 3, 4, 5}

注意：使用前必须先排序，否则只能去除相邻重复项

3. 查找与统计类算法

3.1 std::find与std::find_if：精准定位器

std::find用于查找特定值，std::find_if则查找满足条件的元素：

cpp复制std::vector<int> nums = {1, 3, 5, 7, 9};
auto it = std::find(nums.begin(), nums.end(), 5);  // 查找值为5的元素

// 查找第一个偶数
auto even = std::find_if(nums.begin(), nums.end(), [](int n) {
    return n % 2 == 0;
});

3.2 std::binary_search与lower_bound：二分查找双雄

在已排序的区间中，二分查找算法效率极高（O(log N)）：

cpp复制std::vector<int> nums = {1, 3, 5, 7, 9};
bool found = std::binary_search(nums.begin(), nums.end(), 5);  // 检查是否存在

// 查找第一个不小于4的元素
auto lb = std::lower_bound(nums.begin()