深色模式
第 11 章:查找与排序初步
本章能学到什么
- 顺序查找与二分查找的原理和写法
- 冒泡排序与选择排序的完整过程
- 用 Python 自带的
sorted和sort一行排好序 - 「复杂度」这个概念的一句话印象
知识链位置:第 9、10 章讲了字符串和容器(列表、元组)。数据装进容器之后,最常见的两件事就是「找」和「排」。本章解决这两个问题。
从一个成绩单场景开始
期末考试结束,全班 40 人的成绩存进了电脑:
python
names = ["小明", "小红", "小刚"] # ……
scores = [72, 85, 60] # ……班主任提出两个要求:
- 查一下小刚考了多少分——这是查找。
- 把全班按分数从高到低排队——这是排序。
这两件事在学校里天天发生。本章看看计算机怎么做,以及怎样做得更快。
顺序查找:一个一个看过去
最朴素的办法:从第一个开始,逐个比较,找到就停。
python
names = ["小明", "小红", "小刚", "小丽", "小华"]
scores = [72, 85, 60, 95, 78]
target = "小刚"
found = -1 # -1 表示「还没找到」
for i in range(len(names)):
if names[i] == target: # 逐个比较
found = i
break # 找到就停,不再往后看
if found != -1:
print(target + "的成绩是" + str(scores[found]))
else:
print("没找到" + target)text
小刚的成绩是60这个方法和在作业本堆里翻自己的本子一样:运气好看一本就找到,运气差要翻完整堆。40 人最多看 40 次,4000 人最多看 4000 次。
二分查找:查字典的智慧
查字典时没人从第一页开始翻。查「中」字,先翻到中间附近,发现是「王」部,知道「中」在前面,于是只翻前半本;再对半分,几次就到了。
这个办法叫二分查找。它有一个前提:数据必须已经排好序。乱序的字典没法这样查。
它和数学课上的「折半逼近」是同一招:每次排除一半,范围飞速缩小。
python
scores = [11, 12, 22, 25, 34, 64, 90] # 前提:已从小到大排序
target = 25
left = 0
right = len(scores) - 1 # 查找范围的两端
found = -1
while left <= right:
mid = (left + right) // 2 # 取范围正中间(整数除法)
if scores[mid] == target: # 正好命中
found = mid
break
elif scores[mid] < target:
left = mid + 1 # 目标在右半,砍掉左半
else:
right = mid - 1 # 目标在左半,砍掉右半
if found != -1:
print("找到了,位置是" + str(found))
else:
print("没找到")text
找到了,位置是3两种查找的差距有多大:
| 数据个数 | 顺序查找最多看几次 | 二分查找最多看几次 |
|---|---|---|
| 10 | 10 | 4 |
| 100 | 100 | 7 |
| 1 000 | 1 000 | 10 |
| 1 000 000 | 1 000 000 | 20 |
一百万个数据,二分查找最多 20 次就能定位。因为每看一次,范围缩小一半,2 的 20 次方已经超过一百万。
上面的程序找 25 是一次命中。换成找 22,过程看得更清楚:
| 步数 | left | right | mid | scores[mid] | 判断 |
|---|---|---|---|---|---|
| 1 | 0 | 6 | 3 | 25 | 22 更小,砍掉右半 |
| 2 | 0 | 2 | 1 | 12 | 22 更大,砍掉左半 |
| 3 | 2 | 2 | 2 | 22 | 命中 |
每一次比较,查找范围都缩小一半——这就是「折半」两个字的具体含义。
两种查找各适合什么场合:
| 场合 | 该用哪种 |
|---|---|
| 数据没排序,也不想排序 | 顺序查找 |
| 数据已排序,或要反复查很多次 | 先排序,再二分查找 |
| 数据量很小(几十个) | 都行,顺序查找写起来更简单 |
冒泡排序:相邻的比大小,大的往后挪
排序的数学基础就是「比大小」——数学课上比较两个数谁大,计算机反复做这件事就能把一队数排整齐。
冒泡排序的规则:从头到尾,相邻两个比大小,顺序不对就交换。一轮下来,最大的数像气泡一样「浮」到队尾。再来一轮,第二大的到位。如此反复。
python
a = [64, 25, 12, 22, 11]
n = len(a)
for i in range(n - 1): # 共 n-1 轮
for j in range(n - 1 - i): # 每轮比到「未排好」的末尾
if a[j] > a[j + 1]: # 前面比后面大
a[j], a[j + 1] = a[j + 1], a[j] # 交换两个数
print(" ".join(str(x) for x in a))text
11 12 22 25 64每一轮结束后列表的样子(加粗部分是已经排好的尾部):
| 轮次 | 列表状态 | 本轮归位的数 |
|---|---|---|
| 初始 | 64 25 12 22 11 | — |
| 第 1 轮后 | 25 12 22 11 64 | 64 |
| 第 2 轮后 | 12 22 11 25 64 | 25 |
| 第 3 轮后 | 12 11 22 25 64 | 22 |
| 第 4 轮后 | 11 12 22 25 64 | 全部 |
以第 1 轮为例,看「冒泡」是怎样发生的:
| 比较 | 列表状态(加粗为正在比较的两个) | 是否交换 |
|---|---|---|
| 64 和 25 | 64 25 12 22 11 | 交换 → 25 64 12 22 11 |
| 64 和 12 | 25 64 12 22 11 | 交换 → 25 12 64 22 11 |
| 64 和 22 | 25 12 64 22 11 | 交换 → 25 12 22 64 11 |
| 64 和 11 | 25 12 22 64 11 | 交换 → 25 12 22 11 64 |
最大的 64 一路交换到队尾,像气泡浮上水面——「冒泡」这个名字就是这么来的。
一个常用的小优化:如果某一整轮下来一次交换都没发生,说明已经排好了,可以提前收工:
python
for i in range(n - 1):
swapped = False # 本轮有没有交换过
for j in range(n - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
swapped = True
if not swapped: # 一整轮没交换,提前结束
break对几乎排好的数据,这个优化能省下大半时间。
选择排序:每轮挑出最小的放前面
选择排序换了个思路:第一轮从全部数里找出最小的,和第 1 个位置交换;第二轮从剩下的里找最小的,和第 2 个位置交换。像体育老师排队:先挑出最矮的站排头,再从剩下的人里挑最矮的站第二个。
python
a = [64, 25, 12, 22, 11]
n = len(a)
for i in range(n - 1):
min_pos = i # 先假设第 i 个最小
for j in range(i + 1, n):
if a[j] < a[min_pos]:
min_pos = j # 发现更小的,记下位置
a[i], a[min_pos] = a[min_pos], a[i] # 最小的换到第 i 位
print(" ".join(str(x) for x in a))text
11 12 22 25 64| 轮次 | 列表状态 | 本轮动作 |
|---|---|---|
| 初始 | 64 25 12 22 11 | — |
| 第 1 轮后 | 11 25 12 22 64 | 最小的 11 换到最前 |
| 第 2 轮后 | 11 12 25 22 64 | 剩余中最小的 12 到位 |
| 第 3 轮后 | 11 12 22 25 64 | 22 到位 |
| 第 4 轮后 | 11 12 22 25 64 | 25 到位,结束 |
两种排序的比较:
| 对比点 | 冒泡排序 | 选择排序 |
|---|---|---|
| 每轮做什么 | 相邻比较交换,最大数浮到尾部 | 找出最小数,换到最前 |
| 交换次数 | 多,逆序对都要交换 | 少,每轮最多一次 |
| 好懂程度 | 像气泡上浮 | 像排队挑人 |
站在巨人肩上:sorted 与 sort
实际写程序时很少手写排序。Python 自带两个排序工具:
| 工具 | 用法 | 特点 |
|---|---|---|
sorted(a) | b = sorted(a) | 返回一个排好序的新列表,原列表不动 |
a.sort() | a.sort() | 把原列表就地排好,不返回新列表 |
python
a = [64, 25, 12, 22, 11]
b = sorted(a) # 得到新列表,a 不变
print("sorted 结果:" + " ".join(str(x) for x in b))
print("原列表没变:" + " ".join(str(x) for x in a))
a.sort() # 就地排序,a 自己变
print("sort 之后:" + " ".join(str(x) for x in a))
a.sort(reverse=True) # 从大到小
print("从大到小:" + " ".join(str(x) for x in a))text
sorted 结果:11 12 22 25 64
原列表没变:64 25 12 22 11
sort 之后:11 12 22 25 64
从大到小:64 25 22 12 11手写冒泡和选择排序的意义不在于日常使用,在于理解「比较 + 交换」这套基本功。
给成绩单排序:两个列表一起动
回到本章开头的成绩单。姓名和分数在两个列表里,按分数排序时,交换分数的同时必须交换对应的姓名,否则张冠李戴:
python
names = ["小明", "小红", "小刚", "小丽"]
scores = [72, 85, 60, 95]
# 选择排序:按分数从高到低,姓名跟着一起动
for i in range(len(scores) - 1):
max_pos = i
for j in range(i + 1, len(scores)):
if scores[j] > scores[max_pos]:
max_pos = j
scores[i], scores[max_pos] = scores[max_pos], scores[i]
names[i], names[max_pos] = names[max_pos], names[i]
for i in range(len(names)):
print(names[i] + " " + str(scores[i]))text
小丽 95
小红 85
小明 72
小刚 60这种「两个列表绑在一起动」的写法能工作,但很别扭,漏交换一个就出错。第 12 章会把姓名和分数装进一个包里,从根上消灭这种别扭。
为什么还要学手写排序
既然 sorted 一行就能排好,冒泡和选择为什么值得学:
| 理由 | 说明 |
|---|---|
| 练基本功 | 比较、交换、下标控制,是所有算法内容的共同起点 |
| 理解代价 | 亲手写过,才知道排序不是「免费的」,数据大时要讲方法 |
| 应对变化 | 按特殊规则排序(先按总分、同分再按学号)时,比较逻辑要自己写 |
| 考试与竞赛 | 学校信息课、竞赛入门,这两个排序都是常驻题目 |
日常写程序用库函数,学习阶段写手写版——两件事不矛盾。
【跨语言对照】同一个冒泡,两种写法
本质问题:冒泡排序的逻辑——比较、交换、轮数——在任何语言里都一样。不同的是写出来的样子。
| 写法差异 | Python | C++ |
|---|---|---|
| 装数据的容器 | 列表 list | vector<int> |
| 求长度 | len(a) | a.size() |
| 交换两个元素 | a[j], a[j+1] = a[j+1], a[j] 一行完成 | 借助临时变量三行完成 |
| 输出一行数 | " ".join(...) 拼接 | 循环里逐个 cout |
Python 版:
python
a = [64, 25, 12, 22, 11]
n = len(a)
print("排序前:" + " ".join(str(x) for x in a))
for i in range(n - 1): # 冒泡排序
for j in range(n - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j] # 交换
print("排序后:" + " ".join(str(x) for x in a))C++ 版(详见 《C++ 从入门到精通》第 11 章):
cpp
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> a = {64, 25, 12, 22, 11};
int n = a.size();
cout << "排序前:";
for (int i = 0; i < n; i++) {
cout << a[i];
if (i + 1 < n) cout << " ";
}
cout << endl;
for (int i = 0; i < n - 1; i++) { // 冒泡排序
for (int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
int t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
}
}
}
cout << "排序后:";
for (int i = 0; i < n; i++) {
cout << a[i];
if (i + 1 < n) cout << " ";
}
cout << endl;
return 0;
}两段程序的输出完全一致:
text
排序前:64 25 12 22 11
排序后:11 12 22 25 64为什么设计不一样:Python 把「少打字」当作设计目标,交换这种高频操作直接做成语法。C++ 诞生于对性能和精确控制有要求的年代,交换也要程序员自己写清每一步,编译器才能生成高效的机器指令。两种取向各有适用的场合,本章不做优劣评判。
一句关于「复杂度」的话
计算机科学家用复杂度这个词描述「数据变多时,程序会变慢多少」。冒泡排序的数据量翻 10 倍,时间大约翻 100 倍;二分查找的数据量翻 10 倍,时间只增加一点点。这个概念现在只需有个印象,今后的学习中会反复遇到。
动手实验
实验 1:把顺序查找程序里的 target 改成 "小王",运行程序,观察输出,解释为什么会这样。
💡 查看答案
输出 没找到小王。
循环把 5 个名字全部比较了一遍,没有任何一个等于 "小王",所以 found 始终是初始值 -1,程序走了 else 分支。这正是用 -1 做「没找到」标记的原因。
实验 2:修改冒泡排序程序,让列表从大到小排列,输出 90 64 34 25 22 12 11(先把数据换成 [11, 12, 22, 25, 34, 64, 90] 再改比较方向)。
💡 查看答案
只需把内层循环里的 > 改成 <:前一个数比后一个小就交换,大数就会逐渐浮到前面。
python
a = [11, 12, 22, 25, 34, 64, 90]
n = len(a)
for i in range(n - 1):
for j in range(n - 1 - i):
if a[j] < a[j + 1]: # 只改这一行:小于就交换
a[j], a[j + 1] = a[j + 1], a[j]
print(" ".join(str(x) for x in a))text
90 64 34 25 22 12 11实验 3:数据 [90, 34, 11, 64, 25, 22, 12] 是乱序的。先用 sort 把它排好,再用本章的二分查找代码找 64 的位置,输出 找到了,位置是5。
💡 查看答案
python
a = [90, 34, 11, 64, 25, 22, 12]
a.sort() # 先排序:11 12 22 25 34 64 90
target = 64
left = 0
right = len(a) - 1
found = -1
while left <= right:
mid = (left + right) // 2
if a[mid] == target:
found = mid
break
elif a[mid] < target:
left = mid + 1
else:
right = mid - 1
if found != -1:
print("找到了,位置是" + str(found))
else:
print("没找到")text
找到了,位置是5排序后列表是 [11, 12, 22, 25, 34, 64, 90],64 在第 5 个位置(从 0 开始数)。二分查找的前提「已排序」由 sort 保证,两个工具就这样配合起来了。
