C++ 排序、查找与复杂度入门｜C++ 第 14 课

Easy explanation

在电话簿里找名字，为什么不必从第一页翻起？

无序纸条只能逐张检查，最坏要看完所有内容；按姓名排好的电话簿可以先翻到中间，根据字母顺序排除一半，再继续折半。这就是排序为查找创造条件。排序本身需要成本，但如果之后会查很多次，这份成本很值得。

复杂度不是精确秒数，而是数据量变大时工作量怎样增长。处理十个元素时差别可能看不出，十万个元素时，平方级算法可能慢得无法接受。初学阶段先学会数“最多检查多少个元素”，就能建立效率意识。

目标 1使用 sort 和比较器定义排序规则

目标 2实现线性查找与二分查找

目标 3理解有序是二分查找的前提

目标 4用大 O 表达算法增长趋势

C++ 排序、查找与复杂度入门通俗学习插图 — 排序建立顺序，二分查找利用顺序一次排除一半候选。

Core concepts

先把四个核心知识点说清楚。

01

默认排序

sort(values.begin(), values.end());

默认从小到大排序。算法接收半开区间，end 指向最后元素之后。

02

自定义比较

sort(v.begin(), v.end(), compare);

比较器回答左元素是否应排在右元素前，必须保持一致规则。

03

二分查找

binary_search(first, last, value)

每次比较中间元素并排除一半。数据必须按同一规则预先排序。

04

复杂度直觉

O(1), O(log n), O(n), O(n²)

表示规模增长时操作次数的趋势，忽略小常数，关注最主要增长部分。

sort(v.rbegin(), v.rend());

使用反向迭代器可得到从大到小的简单排序。

auto it = find(v.begin(), v.end(), target);

线性查找不要求有序，找不到返回 end。

auto pos = lower_bound(v.begin(), v.end(), x);

返回第一个不小于 x 的位置，可用于插入并维持顺序。

stable_sort(...);

相等元素保持原相对顺序时使用稳定排序。

Complete examples

两个例子，把知识变成能运行的程序。

Example 1

例子一：多规则游戏排行榜

分数更高的排前面；分数相同时，用时更短的排前面；仍相同则按姓名排序。比较器要按优先级逐项决定。

返回 true 表示 a 应在 b 前。相等时不能同时认为双方都在前，否则规则不一致。

分数降序、时间升序

struct Player { string name; int score; int seconds; };

sort(players.begin(), players.end(),
    [](const Player& a, const Player& b)
    {
        if (a.score != b.score) return a.score > b.score;
        if (a.seconds != b.seconds) return a.seconds < b.seconds;
        return a.name < b.name;
    });

for (int i = 0; i < players.size(); ++i)
    cout << i + 1 << ". " << players[i].name
         << " " << players[i].score << '\n';

1. Mia 9802. Lina 920（58秒）3. Tom 920（64秒）

Example 2

例子二：手写二分查找

left 和 right 表示答案仍可能出现的闭区间。检查中间值后，根据大小关系舍弃不可能的一半。

使用 left + (right-left)/2 避免两个大下标相加溢出。循环结束仍未返回就表示不存在。

维护可能答案区间

int binarySearch(const vector<int>& v, int target)
{
    int left = 0;
    int right = static_cast<int>(v.size()) - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (v[mid] == target) return mid;
        if (v[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

数据：3 8 12 19 27 31 45查找 27：先看 19，再看 31，再看 27结果下标：4

Algorithm thinking

效率分析从“每轮排除多少候选”开始。

线性查找每轮只排除当前一个元素，所以最坏检查 n 次。二分查找每轮排除大约一半，规模翻倍通常只多一次比较。两层各遍历 n 次的嵌套循环大约执行 n² 次。先掌握这些直觉，不必急着进行复杂数学证明。

选择算法要考虑使用场景。只查一次且数据无序，先排序可能得不偿失；同一批数据会查询几千次，预先排序通常很有价值。数据经常插入删除时，还要考虑维持顺序的成本。

1
确认数据状态
判断是否已排序、是否允许改变原顺序以及查询会执行多少次。
2
定义比较规则
写出第一优先级、相等时第二优先级和最终稳定规则。
3
维护查找范围
二分每轮明确 left、right 和 mid，并保证范围严格缩小。
4
测量和比较
统计比较次数，用小、中、大三种规模观察增长趋势。

Common mistakes

这些错误很常见，学会自己排查。

1

无序数据直接二分

程序可能偶尔返回正确结果，但没有任何保证。必须先按同一规则排序。

2

比较器使用 <=

相等元素互相都“在前”会破坏严格顺序，应使用 < 或 >。

3

区间不缩小

写 left=mid 而不是 mid+1，某些情况下会无限循环。

4

只看小数据速度

十个元素无法体现增长差异，要统计操作次数并扩大规模。

本课通用调试法

先准备一个最小输入，只保留能够重现问题的几行数据；再在关键步骤输出变量值，确认程序究竟在哪一步偏离预期。编译错误从第一条开始处理，运行错误则比较“实际结果”和“期望结果”。修复后别只重跑原来的例子，还要增加空输入、边界值和错误输入，防止问题换一个形式再次出现。

Homework

第 14 课课后作业：从模仿到独立完成。

建议按顺序完成。前四题帮助巩固语法和基本操作，第五到第七题要求把多个知识点组合起来，第八题是小项目。每道题都要先写输入、处理、输出三行计划，再开始敲代码；程序运行后至少测试正常情况、边界情况和错误情况。

1

三种排序

同一组数字分别按升序、降序和绝对值排序，写三个比较器。

2

学生排名

按总分降序、数学分降序、姓名升序排序，处理总分相同情况。

3

选择排序

手写选择排序，每轮输出当前数组，并统计比较和交换次数。

4

线性对二分

对一千个有序数字执行两种查找，输出比较次数并解释差异。

5

插入位置

用 lower_bound 把新分数插入有序 vector，保持从小到大。

6

重复值范围

使用 lower_bound 和 upper_bound 找出目标值出现次数。

7

复杂度标注

阅读十段短代码，判断 O(1)、O(log n)、O(n) 或 O(n²)，说明理由。

8

排行榜项目

支持添加成绩、多规则排序、按姓名线性查找和按分数二分查找，记录比较次数。

本课验收标准：能写出一致的多字段比较器；手写二分不会死循环；知道二分前必须有序；能用自己的话比较 O(n)、O(n²) 和 O(log n)。

提交内容应包括源代码、三组测试输入与输出、一个曾经出现的错误及修复方法。最后请用自己的话解释本课最重要的概念；如果只能照着代码念，还需要再独立重写一次核心例子。

Lesson 14 summary

算法不仅要正确，还要在数据变大时继续可用。

sortcomparatorlinear searchbinary searchBig O

下一课学习栈和队列。它们不强调按下标访问，而是用严格的进出顺序简化撤销、括号匹配和任务调度。

进入第 15 课返回第 13 课查看课程大纲