5.2 算法与工程化练习

5.2 算法与工程化练习

本节摘要：写得出代码，和写得"对、快、好维护"之间，还差算法思维和工程化意识。本节通过几道经典算法题（冒泡排序、二分查找）练编程思维，再讲清楚命名、结构、测试这些工程化基本功。读完本节，你的代码不只是"能跑"，而且"跑得对、改得动、别人看得懂"。

学习目标

阅读完本节，你应当能够：

1. 手写冒泡排序和二分查找，理解它们的时间复杂度
2. 区分暴力解法和高效解法的适用场景
3. 给函数和变量取有意义的名字
4. 用"小函数 + 单一职责"组织稍大的代码
5. 写简单的测试来验证代码正确性

问题与直觉

学到这里，你已经能写出各种"能跑"的程序。但"能跑"和"写得好"之间还有距离。考虑同一个问题——给一组数字排序：你可以调用 Python 内置的 sorted()，一行搞定；但如果你不知道排序背后是怎么工作的，面试时被问"讲讲冒泡排序"就答不上来，遇到受限环境（不能调库）也束手无策。

算法思维的本质是"理解代码背后的运作方式"。你不需要成为算法竞赛选手，但几个经典算法（排序、查找）是编程素养的一部分——它们训练的是"把一个模糊需求拆成精确步骤"的能力，这种能力写任何代码都用得上。

工程化意识解决的是另一个维度的问题：代码不只是写给机器执行的，更是写给人读的。一段"能跑但只有自己看得懂"的代码，过两个月连你自己都读不懂。命名是否清楚、结构是否合理、有没有测试——这些决定了代码能否长期维护。本节把这两方面结合起来，让你从"会写代码"进化到"会写好代码"。

核心原理

2.1 冒泡排序：最直观的排序

冒泡排序的思路极其直观：反复比较相邻两个元素，顺序错了就交换。每一轮把最大的元素"冒泡"到末尾，多轮后整个序列有序。

def bubble_sort(nums):
    n = len(nums)
    for i in range(n - 1):           # 共 n-1 轮
        for j in range(n - 1 - i):   # 每轮比较到已排好的部分之前
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]   # 交换
    return nums

print(bubble_sort([5, 2, 8, 1, 9]))   # [1, 2, 5, 8, 9]
​

它的时间复杂度是 O(n²)——数据量翻倍，耗时变四倍。所以冒泡排序只适合小数据或教学，真实场景用内置 sorted()（背后是更高效的 Timsort）。

💡 关键直觉：学冒泡排序不是为了真的拿它去排大数据，而是理解"通过相邻比较和交换逐步把序列变有序"这个思想。很多算法的核心都是"某种逐步把无序变有序的过程"。

2.2 二分查找：利用有序性

在一个有序列表里找一个数，二分查找比逐个比对快得多：每次和中间元素比，砍掉一半候选。

def binary_search(nums, target):
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target:
            return mid            # 找到，返回索引
        elif nums[mid] < target:
            low = mid + 1         # 目标在右半边
        else:
            high = mid - 1        # 目标在左半边
    return -1                     # 没找到

print(binary_search([1, 3, 5, 7, 9, 11], 7))   # 3
​

二分查找的时间复杂度是 O(log n)——100 万元素最多比较 20 次。但它的前提是列表必须有序，无序列表得先排序或用线性查找。

2.3 暴力 vs 高效的取舍

⚠️ 常见坑：在无序列表上用二分查找，会得到错误结果却不报错。二分查找的前提"有序"是硬性条件，用之前先确认数据有序，或先排序。

2.4 工程化：命名

好命名是代码可读性的基石。原则是"名字要能说明意图"：

# 坏：名字毫无信息
def f(a, b):
    x = a + b
    return x

# 好：名字说明做什么
def total_price(unit_price, quantity):
    amount = unit_price * quantity
    return amount
​

命名规则：变量是名词（user_name）、函数是动词（calculate_total）、布尔加 is/has 前缀（is_valid）、常量全大写（MAX_SIZE）。别用 data、info、temp 这种信息量几乎为零的名字。

2.5 工程化：单一职责与小函数

一个好函数只做一件事。判断标准是"能不能用一句话描述它干什么"——如果描述里出现"并且"，说明它做了两件事，该拆。

# 坏：一个函数既读文件又统计又打印
def do_everything(path):
    with open(path) as f:
        lines = f.readlines()
    stats = Counter(lines)
    for k, v in stats.items():
        print(k, v)

# 好：拆成三个各司其职的函数
def read_lines(path):
    ...

def count_frequency(lines):
    ...

def print_stats(stats):
    ...
​

2.6 工程化：写测试

写完函数后，立刻用几个输入验证它对不对。Python 内置的 assert 是最简单的测试工具：

def add(a, b):
    return a + b

# 简单的断言测试
assert add(2, 3) == 5
assert add(-1, 1) == 0
assert add(0, 0) == 0
print("所有测试通过")
​

assert 后的条件为假就抛 AssertionError。养成"写完一个函数就 assert 几个用例"的习惯，能省下大量调试时间。

工程实践要点

3.1 先想清楚再写代码

面对一个需求，别急着敲键盘。先问自己几个问题：输入是什么、输出是什么、有哪些边界情况（空输入、单个元素、超大数）、能不能用已有的工具。在脑子里或纸上把步骤理清，再落到代码——这比"边写边想"高效得多。

3.2 边界情况必测

def get_max(nums):
    return max(nums)

# 别只测正常情况，要测边界
assert get_max([1, 2, 3]) == 3
assert get_max([-1, -5, -2]) == -1   # 全负数
assert get_max([42]) == 42            # 单个元素
# 空列表怎么办？max([]) 会抛错——要不要处理，取决于需求
​

💡 关键直觉：bug 几乎都出在边界——空数据、单个元素、最大最小值、重复元素。把这几个用例测一遍，能挡住大部分错误。

3.3 用内置工具，别造轮子

Python 内置和标准库提供了大量经过优化的工具：

# 要排序：用 sorted()，别自己写冒泡
sorted_nums = sorted(nums)

# 要找最大最小：用 max/min，别遍历
biggest = max(nums)

# 要统计：用 Counter，别手写循环
from collections import Counter
Counter(words)
​

理解算法原理是重要的，但日常写代码优先用现成工具——它们更快、更不容易出错。自己造的轮子通常比标准库慢得多。

3.4 注释解释"为什么"，不是"是什么"

# 坏：重复代码说的内容
x = x + 1   # x 加 1

# 好：解释为什么这么做
x = x + 1   # 补偿索引从 0 开始的偏移
​

代码本身已经说明了"做了什么"，注释的价值在于补充"为什么这么做"——尤其是那些看起来奇怪、但有充分理由的代码。

分层练习

基础题：实现冒泡排序

题面：自己实现一个冒泡排序函数 bubble_sort(nums)，对传入的列表原地排序（修改原列表）并返回它。测试几组输入。

思路点拨：双重循环，外层 n-1 轮，内层每轮比较相邻元素并交换。可以加个小优化：如果某一轮没有任何交换，说明已经有序，提前结束。

参考骨架：

def bubble_sort(nums):
    n = len(nums)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
                swapped = True
        if not swapped:    # 本轮没交换，已有序
            break
    return nums

assert bubble_sort([5, 2, 8, 1, 9]) == [1, 2, 5, 8, 9]
assert bubble_sort([1]) == [1]
assert bubble_sort([3, 3, 3]) == [3, 3, 3]
​

进阶题：二分查找

题面：实现 binary_search(nums, target)，在一个有序列表里找目标值，找到返回索引，找不到返回 -1。要求列表必须有序，你可以假设输入已排序。

思路点拨：维护 low 和 high 两个指针，每次取中间比较，根据大小关系收缩范围。

参考骨架：

def binary_search(nums, target):
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

assert binary_search([1, 3, 5, 7, 9], 7) == 3
assert binary_search([1, 3, 5, 7, 9], 4) == -1
assert binary_search([], 1) == -1           # 空列表
assert binary_search([5], 5) == 0           # 单元素命中
​

💡 思考延伸：二分查找的循环条件是 low <= high 还是 low < high？用 <= 能覆盖"单元素"的情况。漏掉等号会让单元素查找失败——这就是边界细节的重要性。

挑战题：成绩排名系统

题面：综合运用本章知识，做一个成绩排名系统。要求：①读入一组 (姓名, 分数) 数据（可以硬编码或从文件读）；②按分数从高到低排序；③能按姓名查找某人的分数和名次；④输出前 N 名。把每个功能拆成独立函数，并写 assert 测试。

思路点拨：这是工程化的综合练习。先设计数据结构（列表存元组或字典），再拆函数（load、rank、find、top_n），每个函数写完立刻测。排序用内置 sorted，查找可以先排序后二分，或转字典。

参考骨架：

def rank_students(records):
    """按分数降序排序，返回带名次的列表"""
    sorted_records = sorted(records, key=lambda x: x[1], reverse=True)
    ranked = []
    for rank, (name, score) in enumerate(sorted_records, 1):
        ranked.append((rank, name, score))
    return ranked

def find_student(ranked, name):
    """按姓名查找，返回 (名次, 分数) 或 None"""
    for rank, n, score in ranked:
        if n == name:
            return (rank, score)
    return None

def top_n(ranked, n):
    """返回前 n 名"""
    return ranked[:n]

# 测试
records = [("小明", 85), ("小红", 92), ("小刚", 78)]
ranked = rank_students(records)
assert ranked[0][1] == "小红"    # 第一名是小红
assert find_student(ranked, "小刚") == (3, 78)
assert len(top_n(ranked, 2)) == 2
for rank, name, score in ranked:
    print(f"第{rank}名 {name} {score}分")
​

⚠️ 常见坑：enumerate(sorted_records, 1) 的第二个参数 1 表示名次从 1 开始（而不是默认的 0）。这种细节不测就容易错——名次显示成"第 0 名"就尴尬了。

追问与答疑

O(n²) 和 O(log n) 到底差多少，有实际感受吗？ 拿真实数字感受一下：一万元素，冒泡要做约五千万次比较，在现代电脑上要跑好几秒；二分最多十四次比较，微秒级完成。差距不是"快一点"，是"能不能用"的区别。但反过来，五十个元素的排序，冒泡和内置排序的耗时都不到毫秒——复杂度只在规模上来之后才产生痛感。所以工程判断是两条：先问"数据会到多大规模"，再选解法；数据永远小的场景，选最好写、最好读的那个。

学排序查找这些经典题，实际工作里用得上吗？ 直接用到手写实现的场合确实少，但训练价值在三个间接层面。一是面试和考试绕不开；二是二分的"收缩区间"思想在调试（二分定位出错提交）、性能分析（定位慢在哪一段）里反复出现；三是写完再测的流程，把"边界意识"变成了肌肉记忆。把经典题当思维健身房，而不是工具箱，期望就摆对了。

assert 和正式的测试框架差别在哪？ assert 是零成本起步的冒烟测试，适合练习和小脚本。它的局限有三：断言失败只报第一处、没有组织结构、运行时加优化选项会被跳过。代码规模上去后，标准库的 unittest 或第三方的 pytest 提供用例分组、批量执行、清晰报告。迁移成本低——assert 的用例几乎能原样搬进 pytest。路径是：assert 起步，等测试数量超过十几个再上框架，别一开始就背框架语法。

函数拆得太细会不会反而难读？ 会有这个甜蜜点问题。过度拆分的症状是：函数名比函数体还长、调用链要跳四五层才能看到干活的地方。判断拆不拆，看两点：两段逻辑是否会独立变化（会，就拆）；拆出来的函数是否有清晰的单句语义（有，名字就取得出来）。名字取不出来的"函数"，往往是不该存在的切分。经验上，一个函数十五到三十行是多数人阅读舒展的区间。

最后补一道综合小题：把你前面写的二分查找改成"泛化版本"，支持传入任意可比较元素（字符串也行）的有序列表。你会发现一行都不用改——这正说明当初的实现没有把"数字"这个细节焊死在逻辑里。顺便用字符串列表测三条边界：空列表、单元素、目标在首尾。

本节要点回顾

• 冒泡排序靠相邻比较和交换：O(n²)，适合教学和小数据，真实场景用 sorted()。
• 二分查找利用有序性每次砍一半：O(log n)，前提是列表必须有序。
• 理解算法原理重要，但日常优先用内置工具：自己造轮子通常更慢更易错。
• 好命名是可读性基石：名词变量、动词函数、布尔加 is/has、常量大写。
• 函数单一职责：能用一句话描述、不出现"并且"的函数才是好函数。
• 写完立刻 assert 测试：重点测边界——空、单元素、最值、重复。
• 注释解释"为什么"不是"是什么"：代码本身已说明做了什么，注释补充动机。
• 先想清楚再写代码：理清输入、输出、边界，比边写边想高效得多。

恭喜，你已经完成了这套 Python 练习题教程的全部内容。附录有一份各章练习题的答案速查，方便你回顾。