概述

<algorithm> 是 C++ STL 中最庞大的头文件之一，提供了 100+ 个通用算法。掌握这些算法能极大提升编码效率。本文将重点讲解最常用的排序和查找类算法。

所有算法都通过迭代器操作容器，与具体容器类型解耦——这就是 STL 算法的精髓。

sort —— 排序

std::sort 是最常用的排序算法，底层通常是 Introsort（快速排序 + 堆排序 + 插入排序的混合），平均复杂度 **O(n log n)**。

基本用法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    
    // 默认升序
    std::sort(v.begin(), v.end());
    for (int x : v) {
        std::cout << x << " ";  // 1 2 3 4 5 6 7 8 9
    }
    std::cout << std::endl;
    
    return 0;
}

自定义排序规则

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    
    // 降序
    std::sort(v.begin(), v.end(), std::greater<int>());
    for (int x : v) {
        std::cout << x << " ";  // 9 8 7 6 5 4 3 2 1
    }
    std::cout << std::endl;
    
    // 自定义 lambda
    std::vector<int> v2 = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    // 偶数在前，奇数在后；同为偶数/奇数时按升序
    std::sort(v2.begin(), v2.end(), [](int a, int b) {
        if (a % 2 != b % 2) return a % 2 == 0;  // 偶数优先
        return a < b;  // 同类按升序
    });
    for (int x : v2) {
        std::cout << x << " ";  // 2 4 6 8 1 3 5 9
    }
    std::cout << std::endl;
    
    return 0;
}

排序自定义类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

struct Student {
    std::string name;
    int score;
};

int main() {
    std::vector<Student> students = {
        {"Alice", 95}, {"Bob", 87}, {"Charlie", 95}, {"David", 72}
    };
    
    // 按分数降序，同分按名字升序
    std::sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
        if (a.score != b.score) return a.score > b.score;
        return a.name < b.name;
    });
    
    for (const auto& s : students) {
        std::cout << s.name << ": " << s.score << std::endl;
    }
    // Alice: 95
    // Charlie: 95
    // Bob: 87
    // David: 72
    
    return 0;
}

partial_sort —— 部分排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    
    // 只排序前 3 个最小的元素
    std::partial_sort(v.begin(), v.begin() + 3, v.end());
    for (int x : v) {
        std::cout << x << " ";  // 1 2 3 8 9 5 7 4 6（前3个有序，后面无序）
    }
    std::cout << std::endl;
    
    // Top N 问题的高效解法
    std::vector<int> v2 = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    // 求前 3 大
    std::partial_sort(v2.begin(), v2.begin() + 3, v2.end(), std::greater<int>());
    std::cout << "Top 3: " << v2[0] << " " << v2[1] << " " << v2[2] << std::endl;
    // Top 3: 9 8 7
    
    return 0;
}

stable_sort —— 稳定排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

int main() {
    std::vector<std::pair<int, std::string>> v = {
        {3, "Alice"}, {1, "Bob"}, {2, "Charlie"}, {1, "David"}, {3, "Eve"}
    };
    
    // sort 不保证稳定：相同 key 的元素相对顺序可能改变
    // stable_sort 保证稳定：相同 key 的元素保持原始相对顺序
    std::stable_sort(v.begin(), v.end());
    
    for (auto& [num, name] : v) {
        std::cout << num << ": " << name << std::endl;
    }
    // 1: Bob     ← Bob 原来在 David 前面，stable_sort 保持这个顺序
    // 1: David
    // 2: Charlie
    // 3: Alice   ← Alice 原来在 Eve 前面
    // 3: Eve
    
    return 0;
}

binary_search —— 二分查找

std::binary_search 在已排序的区间中查找元素，返回 bool。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v = {1, 3, 5, 7, 9, 11, 13};
    
    // 查找存在的元素
    bool found = std::binary_search(v.begin(), v.end(), 7);
    std::cout << "Found 7: " << found << std::endl;  // true
    
    // 查找不存在的元素
    found = std::binary_search(v.begin(), v.end(), 6);
    std::cout << "Found 6: " << found << std::endl;  // false
    
    // ⚠️ 容器必须已排序！
    std::vector<int> unsorted = {5, 2, 8, 1};
    // std::binary_search(unsorted.begin(), unsorted.end(), 5);  // 未定义行为！
    
    return 0;
}

注意：binary_search 只返回 bool，不能获取元素位置。如果需要位置，用 lower_bound。

lower_bound 和 upper_bound

这两个是二分查找中最核心的工具：

  • **lower_bound**：第一个 ≥ target 的位置
  • **upper_bound**：第一个 > target 的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v = {1, 2, 4, 4, 4, 6, 7, 9};
    int target = 4;
    
    // lower_bound：第一个 >= 4 的位置
    auto lb = std::lower_bound(v.begin(), v.end(), target);
    std::cout << "lower_bound: index=" << (lb - v.begin()) 
              << ", value=" << *lb << std::endl;
    // lower_bound: index=2, value=4
    
    // upper_bound：第一个 > 4 的位置
    auto ub = std::upper_bound(v.begin(), v.end(), target);
    std::cout << "upper_bound: index=" << (ub - v.begin()) 
              << ", value=" << *ub << std::endl;
    // upper_bound: index=5, value=6
    
    // 计算等于 4 的元素个数
    int count = ub - lb;
    std::cout << "Count of 4: " << count << std::endl;  // 3
    
    // 判断元素是否存在
    bool exists = (lb != v.end() && *lb == target);
    std::cout << "4 exists: " << exists << std::endl;  // true
    
    // 找小于 target 的元素个数
    int lessCount = lb - v.begin();
    std::cout << "Elements < 4: " << lessCount << std::endl;  // 2
    
    // 找大于等于 target 的元素个数
    int geCount = v.end() - lb;
    std::cout << "Elements >= 4: " << geCount << std::endl;  // 6
    
    return 0;
}

降序数组的二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v = {9, 7, 6, 4, 4, 4, 2, 1};  // 降序
    
    int target = 4;
    
    // 降序数组需要传入自定义比较器
    // lower_bound 默认用 <，我们需要用 >
    auto lb = std::lower_bound(v.begin(), v.end(), target, std::greater<int>());
    std::cout << "lower_bound: " << (lb - v.begin()) << std::endl;  // 3
    
    auto ub = std::upper_bound(v.begin(), v.end(), target, std::greater<int>());
    std::cout << "upper_bound: " << (ub - v.begin()) << std::endl;  // 6
    
    return 0;
}

equal_range —— 一步到位

equal_range 同时返回 lower_bound 和 upper_bound：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v = {1, 2, 4, 4, 4, 6, 7, 9};
    
    auto [lb, ub] = std::equal_range(v.begin(), v.end(), 4);
    std::cout << "Range: [" << (lb - v.begin()) << ", " 
              << (ub - v.begin()) << ")" << std::endl;
    // Range: [2, 5)
    
    std::cout << "All 4s: ";
    for (auto it = lb; it != ub; ++it) {
        std::cout << *it << " ";  // 4 4 4
    }
    std::cout << std::endl;
    
    return 0;
}

find —— 线性查找

std::find 是线性查找 O(n)，不需要排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v = {5, 2, 8, 1, 9, 3};
    
    auto it = std::find(v.begin(), v.end(), 8);
    if (it != v.end()) {
        std::cout << "Found 8 at index: " << (it - v.begin()) << std::endl;  // 2
    }
    
    // 查找不存在
    it = std::find(v.begin(), v.end(), 7);
    if (it == v.end()) {
        std::cout << "7 not found" << std::endl;
    }
    
    return 0;
}

find_if —— 条件查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v = {1, 4, 7, 2, 9, 6, 3, 8, 5};
    
    // 找第一个大于 5 的元素
    auto it = std::find_if(v.begin(), v.end(), [](int x) {
        return x > 5;
    });
    if (it != v.end()) {
        std::cout << "First > 5: " << *it << std::endl;  // 7
    }
    
    // 找第一个偶数
    it = std::find_if(v.begin(), v.end(), [](int x) {
        return x % 2 == 0;
    });
    if (it != v.end()) {
        std::cout << "First even: " << *it << std::endl;  // 4
    }
    
    return 0;
}

find_if_not —— 条件不满足的第一个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v = {2, 4, 6, 8, 10, 3, 5};
    
    // 找第一个不是偶数的元素
    auto it = std::find_if_not(v.begin(), v.end(), [](int x) {
        return x % 2 == 0;
    });
    if (it != v.end()) {
        std::cout << "First odd: " << *it << std::endl;  // 3
    }
    
    return 0;
}

count 与 count_if

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v = {1, 2, 3, 2, 4, 2, 5, 2, 6};
    
    // count：统计特定值出现次数
    int cnt = std::count(v.begin(), v.end(), 2);
    std::cout << "Count of 2: " << cnt << std::endl;  // 4
    
    // count_if：统计满足条件的元素个数
    cnt = std::count_if(v.begin(), v.end(), [](int x) {
        return x > 3;
    });
    std::cout << "Count > 3: " << cnt << std::endl;  // 3
    
    // 统计偶数个数
    cnt = std::count_if(v.begin(), v.end(), [](int x) {
        return x % 2 == 0;
    });
    std::cout << "Even count: " << cnt << std::endl;  // 5
    
    return 0;
}

min、max 与 minmax

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

int main() {
    // 基本用法
    std::cout << std::min(3, 7) << std::endl;   // 3
    std::cout << std::max(3, 7) << std::endl;   // 7
    
    // 初始化列表
    std::cout << std::min({5, 2, 8, 1, 9}) << std::endl;  // 1
    std::cout << std::max({5, 2, 8, 1, 9}) << std::endl;  // 9
    
    // 自定义比较
    std::string a = "apple", b = "banana";
    std::cout << std::min(a, b, [](const std::string& x, const std::string& y) {
        return x.size() < y.size();  // 按长度比较
    }) << std::endl;  // apple
    
    // minmax：同时获取最小和最大（C++11）
    auto [lo, hi] = std::minmax({5, 2, 8, 1, 9});
    std::cout << "Min: " << lo << ", Max: " << hi << std::endl;  // Min: 1, Max: 9
    
    // minmax_element：在容器中找最小和最大的元素
    std::vector<int> v = {5, 2, 8, 1, 9, 3};
    auto [minIt, maxIt] = std::minmax_element(v.begin(), v.end());
    std::cout << "Min at " << (minIt - v.begin()) << ": " << *minIt << std::endl;  // 1
    std::cout << "Max at " << (maxIt - v.begin()) << ": " << *maxIt << std::endl;  // 9
    
    // min_element / max_element
    auto minEl = std::min_element(v.begin(), v.end());
    auto maxEl = std::max_element(v.begin(), v.end());
    
    return 0;
}

unique —— 去除相邻重复元素

unique 只去除相邻的重复元素，所以通常要先排序。它也不真正删除元素，而是把不重复的元素移到前面，返回新的逻辑末尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v = {1, 1, 2, 3, 3, 3, 4, 5, 5};
    
    // unique 把不重复元素移到前面，返回新末尾
    auto newEnd = std::unique(v.begin(), v.end());
    
    std::cout << "After unique (before erase): ";
    for (int x : v) {
        std::cout << x << " ";  // 1 2 3 4 5 3 4 5 5
    }
    std::cout << std::endl;
    std::cout << "New size: " << (newEnd - v.begin()) << std::endl;  // 5
    
    // 搭配 erase 真正删除多余元素
    v.erase(newEnd, v.end());
    
    std::cout << "After erase: ";
    for (int x : v) {
        std::cout << x << " ";  // 1 2 3 4 5
    }
    std::cout << std::endl;
    
    // ⚠️ 没排序的情况
    std::vector<int> v2 = {3, 1, 2, 3, 2, 1};
    auto newEnd2 = std::unique(v2.begin(), v2.end());
    // 结果：3 1 2 3 2 1 → 3 1 2 3 2 1（没变化！因为相邻元素都不相同）
    
    // ✅ 正确的去重流程：先排序，再 unique，再 erase
    std::sort(v2.begin(), v2.end());           // 1 1 2 2 3 3
    auto ne = std::unique(v2.begin(), v2.end());  // 1 2 3 ...
    v2.erase(ne, v2.end());                    // 1 2 3
    
    std::cout << "Proper dedup: ";
    for (int x : v2) std::cout << x << " ";  // 1 2 3
    std::cout << std::endl;
    
    return 0;
}

reverse —— 反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    
    // 反转整个容器
    std::reverse(v.begin(), v.end());
    for (int x : v) std::cout << x << " ";  // 5 4 3 2 1
    std::cout << std::endl;
    
    // 反转字符串
    std::string s = "hello";
    std::reverse(s.begin(), s.end());
    std::cout << s << std::endl;  // olleh
    
    // 反转部分区间
    std::vector<int> v2 = {1, 2, 3, 4, 5};
    std::reverse(v2.begin() + 1, v2.begin() + 4);  // 反转 [1,4) → 1 4 3 2 5
    for (int x : v2) std::cout << x << " ";  // 1 4 3 2 5
    std::cout << std::endl;
    
    // reverse_copy：反转到另一个容器
    std::vector<int> v3 = {1, 2, 3, 4, 5};
    std::vector<int> v4(5);
    std::reverse_copy(v3.begin(), v3.end(), v4.begin());
    for (int x : v4) std::cout << x << " ";  // 5 4 3 2 1
    std::cout << std::endl;
    
    return 0;
}

常见陷阱总结

1. binary_search 前必须排序

1
2
3
4
std::vector<int> v = {5, 2, 8, 1, 9};
// ❌ std::binary_search(v.begin(), v.end(), 8);  // UB！
std::sort(v.begin(), v.end());
// ✅ std::binary_search(v.begin(), v.end(), 8);  // OK

2. unique 不会自动删除元素

1
2
3
std::vector<int> v = {1, 1, 2, 2, 3};
// ❌ std::unique(v.begin(), v.end());  // v.size() 仍然是 5！
// ✅ v.erase(std::unique(v.begin(), v.end()), v.end());

3. sort 的比较器必须满足严格弱序

1
2
3
4
5
6
7
8
9
// ❌ 错误的比较器
std::sort(v.begin(), v.end(), [](int a, int b) {
    return a <= b;  // 必须用 <，不能用 <=
});

// ✅ 正确的比较器
std::sort(v.begin(), v.end(), [](int a, int b) {
    return a < b;  // 严格弱序
});

用 <= 会导致元素相等时返回 true，违反严格弱序要求，结果是未定义行为。

本文覆盖了最基础的排序和查找算法。下一篇将介绍更多数值计算和变换类算法。