Skip to content

第 11 章:查找与排序初步 ​

本章能学到什么 ​

  • 顺序查找与二分查找的原理和写法
  • 冒泡排序与选择排序的完整过程
  • 用 Python 自带的 sorted 和 sort 一行排好序
  • 「复杂度」这个概念的一句话印象

知识链位置:第 9、10 章讲了字符串和容器(列表、元组)。数据装进容器之后,最常见的两件事就是「找」和「排」。本章解决这两个问题。

从一个成绩单场景开始 ​

期末考试结束,全班 40 人的成绩存进了电脑:

python
names  = ["小明", "小红", "小刚"]  # ……
scores = [72, 85, 60]              # ……

班主任提出两个要求:

  1. 查一下小刚考了多少分——这是查找。
  2. 把全班按分数从高到低排队——这是排序。

这两件事在学校里天天发生。本章看看计算机怎么做,以及怎样做得更快。

顺序查找:一个一个看过去 ​

最朴素的办法:从第一个开始,逐个比较,找到就停。

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

两种查找的差距有多大:

数据个数顺序查找最多看几次二分查找最多看几次
10104
1001007
1 0001 00010
1 000 0001 000 00020

一百万个数据,二分查找最多 20 次就能定位。因为每看一次,范围缩小一半,2 的 20 次方已经超过一百万。

上面的程序找 25 是一次命中。换成找 22,过程看得更清楚:

步数leftrightmidscores[mid]判断
10632522 更小,砍掉右半
20211222 更大,砍掉左半
322222命中

每一次比较,查找范围都缩小一半——这就是「折半」两个字的具体含义。

两种查找各适合什么场合:

场合该用哪种
数据没排序,也不想排序顺序查找
数据已排序,或要反复查很多次先排序,再二分查找
数据量很小(几十个)都行,顺序查找写起来更简单

冒泡排序:相邻的比大小,大的往后挪 ​

排序的数学基础就是「比大小」——数学课上比较两个数谁大,计算机反复做这件事就能把一队数排整齐。

冒泡排序的规则:从头到尾,相邻两个比大小,顺序不对就交换。一轮下来,最大的数像气泡一样「浮」到队尾。再来一轮,第二大的到位。如此反复。

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 6464
第 2 轮后12 22 11 25 6425
第 3 轮后12 11 22 25 6422
第 4 轮后11 12 22 25 64全部

以第 1 轮为例,看「冒泡」是怎样发生的:

比较列表状态(加粗为正在比较的两个)是否交换
64 和 2564 25 12 22 11交换 → 25 64 12 22 11
64 和 1225 64 12 22 11交换 → 25 12 64 22 11
64 和 2225 12 64 22 11交换 → 25 12 22 64 11
64 和 1125 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 6422 到位
第 4 轮后11 12 22 25 6425 到位,结束

两种排序的比较:

对比点冒泡排序选择排序
每轮做什么相邻比较交换,最大数浮到尾部找出最小数,换到最前
交换次数多,逆序对都要交换少,每轮最多一次
好懂程度像气泡上浮像排队挑人

站在巨人肩上: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 一行就能排好,冒泡和选择为什么值得学:

理由说明
练基本功比较、交换、下标控制,是所有算法内容的共同起点
理解代价亲手写过,才知道排序不是「免费的」,数据大时要讲方法
应对变化按特殊规则排序(先按总分、同分再按学号)时,比较逻辑要自己写
考试与竞赛学校信息课、竞赛入门,这两个排序都是常驻题目

日常写程序用库函数,学习阶段写手写版——两件事不矛盾。

【跨语言对照】同一个冒泡,两种写法 ​

本质问题:冒泡排序的逻辑——比较、交换、轮数——在任何语言里都一样。不同的是写出来的样子。

写法差异PythonC++
装数据的容器列表 listvector<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 保证,两个工具就这样配合起来了。