一、sort 的基本用法

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

void show(const char *t, const vector<int> &v) {
    cout << t << "：";
    for (int x : v) cout << x << " ";
    cout << endl;
}

int main() {
    // ── 实例07：用 sort 排序元素 ────────────
    vector<int> v = {5, 2, 8, 1, 9, 3, 7, 4, 6};

    show("原始    ", v);

    sort(v.begin(), v.end());                       // ★ 默认：从小到大
    show("升序    ", v);

    sort(v.begin(), v.end(), greater<int>());       // ★ 从大到小（用标准库的比较器）
    show("降序    ", v);

    // 只排一部分
    vector<int> p = {9, 3, 7, 1, 8, 2, 6};
    sort(p.begin() + 2, p.begin() + 5);             // 只排第 3～5 个（[2,5) ）
    show("只排中间", p);

    // ── 字符串也能排 ─────────────────────
    vector<string> s = {"banana", "apple", "cherry", "date"};
    sort(s.begin(), s.end());                       // 字典序
    cout << "字符串升序：";
    for (const string &x : s) cout << x << " ";
    cout << endl;

    // ── 裸数组也能排（数组名就是迭代器）──
    int a[] = {5, 2, 8, 1};
    sort(a, a + 4);
    cout << "裸数组排序：";
    for (int i = 0; i < 4; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}

看到什么算成功：

原始    ：5 2 8 1 9 3 7 4 6 
升序    ：1 2 3 4 5 6 7 8 9 
降序    ：9 8 7 6 5 4 3 2 1 
只排中间：9 3 1 7 8 2 6 
字符串升序：apple banana cherry date 
裸数组排序：1 2 5 8 

几个要点：

greater<int>() 那个"两个括号"：greater<int> 是一个模板类（12.2），greater<int>() 是造一个它的对象（就是 13.3 导言说的"函数对象"）。注意"降序"用 greater 而不是 less——"规则"表达的是"哪个排前面"，greater 表示"大的排前面"。 更省事的替代(C++14 起)：sort(v.begin(), v.end(), greater<>());（让编译器自己推类型）。

二、自定义比较规则：三种写法

"怎么算 '前面'"这件事，由你说了算。 三种写法都能用：

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

struct Student {
    string name;
    int    score;
    int    age;
    Student(const string &n, int s, int a) : name(n), score(s), age(a) {}
};

// ① 普通函数：按分数从高到低
bool byScoreDesc(const Student &a, const Student &b) {
    return a.score > b.score;
}

// ② 函数对象：按年龄从小到大
struct ByAge {
    bool operator()(const Student &a, const Student &b) const {
        return a.age < b.age;
    }
};

// 让 Student 能"自己比大小"（11.2 运算符重载；不写它就不能直接 sort(b,e)）
bool operator<(const Student &a, const Student &b) {
    if (a.score != b.score) return a.score > b.score;   // 分数高的在前
    return a.name < b.name;                              // 分数相同按名字
}

void show(const char *t, const vector<Student> &v) {
    cout << t << "：";
    for (const Student &s : v) cout << s.name << "(" << s.score << "," << s.age << ") ";
    cout << endl;
}

int main() {
    vector<Student> cls = {
        Student("小明", 88, 18),
        Student("小红", 95, 17),
        Student("小刚", 71, 19),
        Student("小丽", 88, 16)
    };
    show("原始        ", cls);

    // ① 普通函数
    sort(cls.begin(), cls.end(), byScoreDesc);
    show("① 按分数降序 ", cls);

    // ② 函数对象
    sort(cls.begin(), cls.end(), ByAge());
    show("② 按年龄升序 ", cls);

    // ③ lambda（最常用）
    sort(cls.begin(), cls.end(), [](const Student &a, const Student &b) {
        return a.name < b.name;
    });
    show("③ 按名字升序 ", cls);

    // ④ 不写第三个参数：用 operator<
    sort(cls.begin(), cls.end());
    show("④ 用 operator<", cls);
    return 0;
}

看到什么算成功：

原始        ：小明(88,18) 小红(95,17) 小刚(71,19) 小丽(88,16) 
① 按分数降序 ：小红(95,17) 小明(88,18) 小丽(88,16) 小刚(71,19) 
② 按年龄升序 ：小丽(88,16) 小红(95,17) 小明(88,18) 小刚(71,19) 
③ 按名字升序 ：小刚(71,19) 小丽(88,16) 小明(88,18) 小红(95,17) 
④ 用 operator<：小明(88,18) 小丽(88,16) 小红(95,17) 小刚(71,19) 

几个容易看错的点：

1. ① 里 小明(88) 和 小丽(88) 谁在前？ —— 输出是小明在前。但这两个分数相同，sort 不保证它们的相对顺序（"不稳定"，见下）——你的编译器上可能反过来。
2. ③ 名字升序：小刚 < 小丽 < 小明 < 小红——这是按 UTF-8 字节比的，不是拼音（"刚 g"、"丽 l"、"明 m"、"红 h"，按拼音应该是"刚、红、丽、明"）。中文排序默认按字节，要按拼音得自己写比较器。
3. ④ 那个自定义的 operator< 就是 11.2 学的"运算符重载" —— 重载了 <，sort 不带第三个参数就能用。注意它是个自由函数（不是成员），因为两边都是 Student。
4. 比较函数必须"严格弱序"：不能写 <= 或 >=（要写 < 或 >）。写错会导致越界、崩溃或结果错乱——这是 sort 最著名的坑（和 13.2.1 的 set 比较器同理）。

三、sort 稳不稳？以及它的"兄弟"们

"稳定"的定义：两个"相等"的元素，排完之后相对顺序保持不变。

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

struct Item {
    string name;
    int    score;
    Item(const string &n, int s) : name(n), score(s) {}
};

int main() {
    vector<Item> v = {
        Item("A", 90), Item("B", 80), Item("C", 90), Item("D", 80), Item("E", 90)
    };

    auto show = [](const char *t, const vector<Item> &x) {
        cout << t << "：";
        for (const Item &i : x) cout << i.name << "(" << i.score << ") ";
        cout << endl;
    };
    show("原始        ", v);

    // ── sort（不稳定）：相等元素的顺序可能变 ──
    vector<Item> a = v;
    sort(a.begin(), a.end(), [](const Item &x, const Item &y) { return x.score > y.score; });
    show("sort        ", a);

    // ── stable_sort（稳定）：相等元素顺序不变 ──
    vector<Item> b = v;
    stable_sort(b.begin(), b.end(), [](const Item &x, const Item &y) { return x.score > y.score; });
    show("stable_sort ", b);
    // ★ 注意看 A C E（都是 90）的顺序，以及 B D（都是 80）的顺序
    return 0;
}

看到什么算成功（stable_sort 那行一定保持 A C E、B D 的原顺序）：

原始        ：A(90) B(80) C(90) D(80) E(90) 
sort        ：E(90) A(90) C(90) B(80) D(80)     ← 90 那一组的顺序可能变
stable_sort ：A(90) C(90) E(90) B(80) D(80)     ← 严格保持原顺序

排序家族的完整名单：

其中 partial_sort 和 nth_element 很值得一提：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 7, 4, 6, 0};

    // ── partial_sort：只要前 3 名 ──────────
    vector<int> a = v;
    partial_sort(a.begin(), a.begin() + 3, a.end());
    cout << "partial_sort 前 3 名：";
    for (int i = 0; i < 3; i++) cout << a[i] << " ";
    cout << "（后面几个没排）" << endl;

    // ── nth_element：只要"第 5 小"（中位数）──
    vector<int> b = v;
    nth_element(b.begin(), b.begin() + 5, b.end());
    cout << "第 6 小的元素是：" << b[5] << endl;
    cout << "它左边都比它小，右边都比它大（但两边都没排）" << endl;
    return 0;
}

输出（nth_element 那句的"左边小、右边大"是关键）：

partial_sort 前 3 名：0 1 2 （后面几个没排）
第 6 小的元素是：5
它左边都比它小，右边都比它大（但两边都没排）

"只要前 N 名就用 partial_sort，只要中位数就用 nth_element" —— 这是"不用全排"的省钱思路。"排行榜取前 10"用 partial_sort 比"全排完再取前 10"便宜（尤其数据量大时）。 复杂度：partial_sort 是 O(n log N)（N 是你想要的个数）；nth_element 是 O(n) —— 这是"选第 k 大"能达到的最优复杂度。

四、二分查找三兄弟（用之前必须先排序）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    // ★ 必须已排序！
    vector<int> v = {1, 3, 5, 5, 5, 7, 9, 11, 13};
    cout << "已排序数据：";
    for (int x : v) cout << x << " ";
    cout << endl;

    // ── ① binary_search：只回答"在不在"（bool）──
    cout << "找 7：  " << (binary_search(v.begin(), v.end(), 7) ? "有" : "没有") << endl;
    cout << "找 8：  " << (binary_search(v.begin(), v.end(), 8) ? "有" : "没有") << endl;

    // ── ② lower_bound：第一个 >= x 的位置 ──
    vector<int>::iterator lb = lower_bound(v.begin(), v.end(), 5);
    cout << "lower_bound(5) 在下标 " << (lb - v.begin()) << "（第一个 5）" << endl;

    // ── ③ upper_bound：第一个 > x 的位置 ──
    vector<int>::iterator ub = upper_bound(v.begin(), v.end(), 5);
    cout << "upper_bound(5) 在下标 " << (ub - v.begin()) << "（5 后面的那个）" << endl;

    // ── ④ 两相减 = "5 有几个" ──────────────
    cout << "5 出现了 " << (ub - lb) << " 次" << endl;

    // ── ⑤ 有序容器里的 insert 位置：lower_bound 一次给出 ──
    cout << "往有序序列插 6，它应该插在下标 " << (lower_bound(v.begin(), v.end(), 6) - v.begin()) << endl;

    // ── ⑥ 在 set/map 上也有同名成员/算法 ─────
    cout << "（13.2.2 的 equal_range 就是 lower_bound + upper_bound）" << endl;
    return 0;
}

看到什么算成功：

已排序数据：1 3 5 5 5 7 9 11 13 
找 7：  有
找 8：  没有
lower_bound(5) 在下标 2（第一个 5）
upper_bound(5) 在下标 5（5 后面的那个）
5 出现了 3 次
往有序序列插 6，它应该插在下标 5

这三个函数的逻辑关系（和 13.2.2 的完全一致）：

⚠️ 铁律：必须先排序。 在无序数据上用 binary_search，结果是"未定义的"（可能查不到明明存在的值）。 这是它和 find 的本质区别——find 不要求有序（O(n)），binary_search 要求有序（O(log n)）。 "排序一次 + 多次查找"和"每次查找都扫一遍"，选哪个取决于你查多少次。 "有序"这一点又要回溯到容器选择：如果数据本来就放在 set / map 里，就用它们的成员 find（自动有序、O(log n)）；如果是 vector，那就"先 sort 一次，之后反复 binary_search"。

五、动手 Demo：成绩排行榜

任务：把一批成绩做成排行榜：总分榜、前 3 名、中位数、按分数查人。

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

struct Rec {
    string name;
    int    score;
    Rec(const string &n, int s) : name(n), score(s) {}
};

void show(const char *t, const vector<Rec> &v) {
    cout << t << "：";
    for (const Rec &r : v) cout << r.name << "(" << r.score << ") ";
    cout << endl;
}

int main() {
    vector<Rec> v = {
        Rec("小明", 88), Rec("小红", 95), Rec("小刚", 71),
        Rec("小丽", 88), Rec("小强", 100), Rec("小敏", 63)
    };
    show("原始        ", v);

    // ① 完整排行榜：分数降序，同分按名字
    sort(v.begin(), v.end(), [](const Rec &a, const Rec &b) {
        if (a.score != b.score) return a.score > b.score;
        return a.name < b.name;
    });
    show("完整排行榜  ", v);

    // ② 只取前 3 名（partial_sort 更省：不用全排）
    vector<Rec> p = { Rec("小明",88), Rec("小红",95), Rec("小刚",71),
                      Rec("小丽",88), Rec("小强",100), Rec("小敏",63) };
    partial_sort(p.begin(), p.begin() + 3, p.end(),
                 [](const Rec &a, const Rec &b) { return a.score > b.score; });
    cout << "前三名      ：";
    for (int i = 0; i < 3; i++) cout << p[i].name << "(" << p[i].score << ") ";
    cout << endl;

    // ③ 中位数（nth_element 是 O(n)）
    vector<int> scores;
    for (const Rec &r : v) scores.push_back(r.score);
    size_t mid = scores.size() / 2;
    nth_element(scores.begin(), scores.begin() + mid, scores.end());
    cout << "分数中位数  ：" << scores[mid] << endl;

    // ④ 按分数查人：先按分数排一次，之后可以反复二分
    vector<pair<int, string>> idx;
    for (const Rec &r : v) idx.push_back(make_pair(r.score, r.name));
    sort(idx.begin(), idx.end(), [](const pair<int,string> &a, const pair<int,string> &b) {
        return a.first < b.first;                       // ★ 二分查找前必须按"被查的键"排序
    });

    auto r = equal_range(idx.begin(), idx.end(), make_pair(88, string("")),
                         [](const pair<int,string> &a, const pair<int,string> &b) {
                             return a.first < b.first;   // ★ 只比分数
                         });
    cout << "88 分的人有 " << (r.second - r.first) << " 个：";
    for (auto it = r.first; it != r.second; ++it) cout << it->second << " ";
    cout << endl;
    return 0;
}

看到什么算成功：

原始        ：小明(88) 小红(95) 小刚(71) 小丽(88) 小强(100) 小敏(63) 
完整排行榜  ：小强(100) 小红(95) 小明(88) 小丽(88) 小刚(71) 小敏(63) 
前三名      ：小强(100) 小红(95) 小明(88) 
分数中位数  ：88
88 分的人有 2 个：小丽 小明 

这个 Demo 把四种手法都用上了：

注意 ④ 那个"只比分数"的比较器：pair 的默认比较是"先比 first、再比 second"。这里我们只想按分数查，所以显式给了"只比 first"的比较器——sort 用的和 equal_range 用的必须是同一个规则，否则二分查找就会出错。这是 equal_range 最容易犯错的地方。

30 秒实验

1. 比较器写 <= 会怎样：把 byScoreDesc 的 > 改成 >=，在大数据上跑 → 可能崩溃或结果错乱（严格弱序被破坏）。这是 sort 的经典雷区。
2. binary_search 用在乱序数据上：vector<int> v={9,1,5,3}; binary_search(v.begin(),v.end(),3); → 多半返回"没有"（虽然 3 确实在）。记住：它要求有序。
3. sort vs stable_sort：把本节第三部分的对比跑一遍，盯住 A C E 和 B D 的顺序。
4. list 不能 sort：写 list<int> l; sort(l.begin(), l.end()); → 编译报一大串（核心是 "no match for 'operator-'"）。改用 l.sort();。

常见误区

1. "sort 是稳定的"——不稳定（用的是快排/堆排/插排的混合）。要保序用 stable_sort。
2. "比较函数可以写 <="——必须写 < / >（严格弱序）。写成 <= 会导致越界访问、崩溃或结果错乱——而且报错位置往往在标准库内部，很难看。
3. "sort 能给任何容器排序"——只能给"随机访问迭代器"的容器：vector、deque、数组。list / set / map 都不行（list 用成员 l.sort()；set / map 本身就排好了）。
4. "只要前 10 名，那就全排完再取前 10"——用 partial_sort 更省（O(n log 10) 而不是 O(n log n)）。只要中位数就用 nth_element（O(n)）。
5. "在 map 上也能用 sort 按值排"——不能（map 的迭代器是双向的，而且它只按键有序）。要按值排，搬到 vector 再 sort（13.2.3）。
6. "binary_search 不要求有序"——错了，必须有序，否则结果未定义。这是它和 find（O(n)、不要求有序）的根本区别。
7. "给自定义类排序，只要写个 sort 调用就行"——sort 需要"能比较"：要么重载 operator<（11.2），要么传比较器。报错会是一大串模板展开，看最后一条 note 最快。
8. "中文排序是按拼音的"——默认按 UTF-8 字节序，不是拼音。要按拼音，得先转拼音再比（自己写比较器）。
9. "sort 的比较器里可以用 a == b"——sort 只需要 <。用 == 判断相等是另一个坑：两个"不相等也不小于"的元素，在严格弱序里就意味着"相等"，所以不要另外写 ==。

• ☐ 下一节（13.3.4 数值算法）

相关笔记

• 修正序列算法（含实例05、06） —— 上一节：reverse / unique / partition
• 数值算法（含实例08） —— 下一节：accumulate 与累加
• 非修正序列算法（含实例03、04） —— adjacent_find 也要靠排序
• map类模板 —— "按值排序"要搬到 vector 再 sort
• multiset 类模板 —— 成员版 equal_range
• 重载运算符 —— 给自定义类排序要重载 <
• 链表类模板 —— list 为什么必须用成员 sort
• 🔷 C++基础 · 索引 —— 全课路线图