第 5 周：查找、递推、递归与排序

本周不追求写复杂算法，而是掌握一类题目的共同分析方法：找出初始状态、每轮变化和停止条件，并能把过程逐轮写在纸上。

建议用时：8-10 小时。

本周目标#

学完本周，你应该能够：

手工求一组数据的最小值、最大值、总和与平均值。
完成顺序查找，并找出目标值的全部位置。
使用累加、累乘和递推解决规律问题。
写出带明确终止条件的递归函数。
推演递归调用过程和返回值。
手写冒泡排序、选择排序的每一轮结果。
在有序列表上正确执行二分查找。
知道常见算法大致需要多少次操作。

5.1 算法不是某一段固定代码#

算法是解决一类问题的明确步骤。一个可执行算法应具备：

输入明确。
每一步可以执行。
输出明确。
在有限步骤内结束。

例如“求最大值”的算法：

先把第一个元素当作当前最大值。
依次查看后面的每个元素。
如果当前元素更大，就更新最大值。
查看完全部元素后，当前最大值就是答案。

只有写成步骤，才能检查“空数据”“只有一个元素”“最大值在开头或末尾”等边界。

5.2 最值与平均值#

使用内置函数#

values = [48, 17, 92, 35, 76]

print(min(values))  # 17
print(max(values))  # 92
print(sum(values))  # 268
print(sum(values) / len(values))  # 53.6

这些函数要求数据可以比较和计算。空列表调用 min()、max() 会报 ValueError，求平均时 len(values) 为 0 会触发除零错误。

手工求最小值#

def find_minimum(values):
    if not values:
        return None

    minimum = values[0]
    for value in values[1:]:
        if value < minimum:
            minimum = value
    return minimum

print(find_minimum([48, 17, 92, 35, 76]))  # 17
print(find_minimum([]))                    # None

minimum = values[0] 是初始状态。循环从第二个元素开始，可以减少一次无意义的比较。

同时求最小值和最大值：

def find_min_max(values):
    if not values:
        return None

    minimum = values[0]
    maximum = values[0]

    for value in values:
        if value < minimum:
            minimum = value
        if value > maximum:
            maximum = value

    return minimum, maximum

print(find_min_max([48, 17, 92, 35, 76]))  # (17, 92)

返回值是元组。函数对空列表返回 None，调用者需要检查。

5.3 顺序查找#

顺序查找从第一个元素开始，逐个比较。

找第一个位置#

def find_first(values, target):
    for index, value in enumerate(values):
        if value == target:
            return index
    return -1

print(find_first(["A", "B", "C", "B"], "B"))  # 1
print(find_first(["A", "B"], "Z"))             # -1

enumerate() 让循环同时取得索引和元素。return 一执行，函数立即结束，所以找到第一个后不会再继续查找。

找全部位置#

def search_all(values, target):
    positions = []

    for index, value in enumerate(values):
        if value == target:
            positions.append(index)

    return positions

data = [48, 17, 92, 35, 76, 92, 11]
print(search_all(data, 92))  # [2, 5]
print(search_all(data, 100)) # []

注意两个常见错误：

找到一个就 return，所以没有收集重复值。
函数结束时忘记 return positions，调用结果为 None。

顺序查找的耗时随数据量增长大致线性增加。若数据有 n 个元素，最坏要比较 n 次，常记作 O(n)。

5.4 累加、计数与累乘#

累加#

total = 0
for number in range(1, 101):
    total += number

print(total)  # 5050

累加前先初始化 total = 0，因为 0 加上第一个数不会改变第一个数。

条件累加#

total = 0
count = 0

for score in [88, 59, 92, 70, 100]:
    if score >= 60:
        total += score
        count += 1

print(total)  # 350
print(count)  # 4

累乘#

累乘通常初始化为 1：

product = 1
for number in range(1, 6):
    product *= number

print(product)  # 120

这就是 5 的阶乘：

5! = 1 × 2 × 3 × 4 × 5 = 120

若累乘初始化为 0，无论乘什么都会得到 0。

5.5 递推#

递推指根据前面一项或几项计算下一项。

斐波那契数列#

规则：

F(1) = 0
F(2) = 1
F(n) = F(n-1) + F(n-2)

前几项是：

0, 1, 1, 2, 3, 5, 8, 13, ...

迭代求第 n 项：

def fibonacci(n):
    if n < 1:
        return None
    if n == 1:
        return 0
    if n == 2:
        return 1

    previous = 0
    current = 1

    for _ in range(3, n + 1):
        next_value = previous + current
        previous = current
        current = next_value

    return current

print(fibonacci(8))  # 13

这里的更新顺序很重要：

next_value = previous + current
previous = current
current = next_value

如果先把 current 改成下一项，再计算 previous，旧值就丢失了。

5.6 递归#

递归是函数调用自身。每个正确递归都必须有：

终止条件：什么时候不再调用自身。
向终止条件靠近：每次调用的问题必须更小。
返回值组合：把子问题的结果组合成当前结果。

阶乘#

def factorial(n):
    if n < 0:
        return None
    if n == 0:
        return 1
    return n * factorial(n - 1)

print(factorial(5))  # 120

过程展开：

factorial(5)
= 5 * factorial(4)
= 5 * 4 * factorial(3)
= 5 * 4 * 3 * factorial(2)
= 5 * 4 * 3 * 2 * factorial(1)
= 5 * 4 * 3 * 2 * 1 * factorial(0)
= 5 * 4 * 3 * 2 * 1 * 1
= 120

n == 0 是终止条件。每次调用使用 n - 1，问题逐渐变小。

如果没有终止条件，或参数没有靠近终止条件，会发生 RecursionError。

递归求列表和#

def recursive_sum(values):
    if not values:
        return 0
    return values[0] + recursive_sum(values[1:])

print(recursive_sum([1, 2, 3, 4]))  # 10

values[1:] 每次减少一个元素。空列表时返回 0。

这种写法便于理解递归，但会反复创建切片。数据规模很大时，用普通循环更高效。比赛中先保证逻辑正确，再考虑优化。

递归和循环的选择#

问题天然分层，例如“当前结果依赖同类子问题”，递归表达更自然。
需要简单累加、遍历或计数时，循环通常更直接。
递归必须有明确的终止条件。
不要用递归计算很大的斐波那契项，因为简单递归会重复计算大量子问题。

5.7 冒泡排序#

冒泡排序反复比较相邻两项。如果左边大于右边，就交换，使较大的值逐步移动到后面。

核心比较：

if data[j] > data[j + 1]:
    data[j], data[j + 1] = data[j + 1], data[j]

完整实现#

def bubble_sort(values):
    data = values.copy()
    n = len(data)

    for pass_index in range(n - 1):
        swapped = False

        for j in range(n - 1 - pass_index):
            if data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]
                swapped = True

        print(f"第 {pass_index + 1} 轮：", data)

        if not swapped:
            break

    return data

print(bubble_sort([5, 1, 4, 2]))

输出：

第 1 轮： [1, 4, 2, 5]
第 2 轮： [1, 2, 4, 5]
第 3 轮： [1, 2, 4, 5]
[1, 2, 4, 5]

手工推演#

初始：

[5, 1, 4, 2]

第一轮：

比较 5 和 1，交换：[1, 5, 4, 2]
比较 5 和 4，交换：[1, 4, 5, 2]
比较 5 和 2，交换：[1, 4, 2, 5]

第一轮结束，最大值 5 到达末尾。

第二轮：

比较 1 和 4，不交换。
比较 4 和 2，交换：[1, 2, 4, 5]
末尾的 5 已确定，这一轮最后无须再比较 4 和 5。

第二轮后是 [1, 2, 4, 5]。

为什么内层范围越来越短#

第 1 轮后，最大值固定在最后；第 2 轮后，最后两个元素已排好。因此第 i 轮只比较前 n - 1 - i 个相邻位置。

按基础版本不提前停止时，数据有 n 个元素会执行 n - 1 轮：

def bubble_sort_basic(values):
    data = values.copy()
    n = len(data)

    for i in range(n - 1):
        for j in range(n - 1 - i):
            if data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]
        print("第", i + 1, "轮：", data)

    return data

最坏情况下，内部比较次数接近 n²，因此时间复杂度通常写为 O(n²)。前面的 swapped 优化可以在已经有序时提前结束，但第一阶段的轮次题通常仍按题目指定的基础过程推演。

5.8 选择排序#

选择排序每一轮在未排序区间找到最小值，再把它放到该区间开头。

def selection_sort(values):
    data = values.copy()
    n = len(data)

    for i in range(n - 1):
        min_index = i

        for j in range(i + 1, n):
            if data[j] < data[min_index]:
                min_index = j

        data[i], data[min_index] = data[min_index], data[i]
        print(f"第 {i + 1} 轮：", data)

    return data

print(selection_sort([5, 1, 4, 2]))

输出：

第 1 轮： [1, 5, 4, 2]
第 2 轮： [1, 2, 4, 5]
第 3 轮： [1, 2, 4, 5]

冒泡与选择的区别#

比较项	冒泡排序	选择排序
每轮做什么	相邻元素比较并交换	扫描未排序区，找最小值
交换次数	可能很多	每轮最多一次
每轮结束	最大元素到末尾	最小元素到开头
常见复杂度	`O(n²)`	`O(n²)`

考试要求推演哪种算法，就按哪种规则写出每轮结果，不要混用。

5.9 二分查找#

二分查找只适用于有序数据。它每次检查中间元素，然后排除一半区间。

def binary_search(values, target):
    low = 0
    high = len(values) - 1
    compared = []

    while low <= high:
        mid = (low + high) // 2
        middle_value = values[mid]
        compared.append(middle_value)

        if middle_value == target:
            return mid, compared
        elif middle_value < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1, compared

data = [1, 3, 5, 7, 9, 11]
position, compared = binary_search(data, 7)

print(position)  # 3
print(compared)  # [5, 9, 7]

手工推演#

在 [1, 3, 5, 7, 9, 11] 中查找 7：

轮次	`low`	`high`	`mid`	中间值	下一步
1	0	5	2	5	7 更大，`low = 3`
2	3	5	4	9	7 更小，`high = 3`
3	3	3	3	7	找到，返回 3

依次比较的中间值是 5、9、7。

循环条件为什么是 `low <= high`#

当 low == high 时，还有一个元素没有检查，因此仍要进入循环。如果写成 low < high，可能在没有检查最后候选值时就退出。

二分一定比顺序查找快吗#

二分查找每次大约排除一半，适合数据较多且已经有序。若数据无序，先排序的成本可能超过直接顺序查找；小数据也未必需要二分。复杂度 O(log n) 描述的是增长趋势，不是每次运行的实际毫秒数。

5.10 怎样写算法过程题#

纸面题通常不是只问最终答案，而是问每轮状态。建议使用四列表：

轮次	比较位置	是否交换	当前序列
初始	-	-	`[5, 1, 4, 2]`
1	`5,1`	是	`[1, 5, 4, 2]`

每完成一个关键操作就更新表，不把多步变化挤在一行。最后再检查：

轮次是否从 1 开始。
是否遗漏最后一次比较。
序列长度是否一直不变。
冒泡是否把最大值移到末尾。
选择是否把最小值移到开头。
二分的 low/high 是否正确更新。

5.11 本周作品一：查找与统计工具包#

def find_min_max(values):
    if not values:
        return None
    minimum = values[0]
    maximum = values[0]

    for value in values:
        if value < minimum:
            minimum = value
        if value > maximum:
            maximum = value

    return minimum, maximum


def search_all(values, target):
    positions = []
    for index, value in enumerate(values):
        if value == target:
            positions.append(index)
    return positions


def average(values):
    if not values:
        return None
    return sum(values) / len(values)


data = [48, 17, 92, 35, 76, 92, 11]
print(find_min_max(data))       # (11, 92)
print(search_all(data, 92))     # [2, 5]
print(f"{average(data):.2f}")   # 53.00

每个函数只完成一个明确任务，便于分别测试。

5.12 本周作品二：排序推演表#

def trace_bubble_sort(values):
    data = values.copy()
    n = len(data)

    for pass_index in range(n - 1):
        for j in range(n - 1 - pass_index):
            if data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]
        print(pass_index + 1, data)

    return data


data = [48, 17, 92, 35, 76, 92, 11]
result = trace_bubble_sort(data)
print("最终：", result)
print("原列表：", data)

因为函数内部使用 data = values.copy()，原列表不会被修改。如果把 values.copy() 改成 values，两个名称会指向同一个列表，输出“原列表”时也会看到已排序结果。

5.13 独立练习#

A. 快速判断题#

顺序查找列表 [3, 7, 7, 9] 中第一个 7，返回的索引是多少？
查找全部 7，返回什么？
5 的阶乘是多少？
递归函数必须有什么条件？
对 [5, 1, 4, 2] 做冒泡第一轮，结果是什么？
对 [5, 1, 4, 2] 做选择第一轮，结果是什么？
二分查找能否直接用于无序列表？
在 [1, 3, 5, 7, 9, 11] 中查找 7，中间值依次是什么？
冒泡排序和选择排序哪一个每轮最多交换一次？
O(log n) 为什么会比 O(n) 增长慢？

B. 编程题#

编写函数返回一个列表的最小值和最大值。
编写函数 searchAll(values, target)，返回所有目标索引。
计算 1 到 20 的乘积。
用递推输出斐波那契数列前 10 项。
用递归计算 1 + 2 + ... + n。
写出冒泡排序，并在每轮后输出当前列表。
写出选择排序，并说明每轮选择的最小值。
写出二分查找，返回目标索引；不存在时返回 -1。

5.14 练习答案与解释#

A. 快速判断题答案#

索引 1。
[1, 2]。
120。
终止条件，并且每次递归都要向终止条件靠近。
[1, 4, 2, 5]。
[1, 5, 4, 2]。第一个位置原本已有最小值 1，交换后序列可能看起来相同。
不能。二分依赖有序性判断目标在中间值左边还是右边。
5、9、7。
选择排序。
数据规模增大时，log n 每次只按约一半增长，而 n 按原规模增长；但实际速度还受实现和数据影响。

B. 编程题参考答案#

最小值和最大值：

def find_min_max(values):
    if not values:
        return None

    minimum = values[0]
    maximum = values[0]

    for value in values:
        if value < minimum:
            minimum = value
        if value > maximum:
            maximum = value

    return minimum, maximum

查找全部位置：

def searchAll(values, target):
    result = []
    for index, value in enumerate(values):
        if value == target:
            result.append(index)
    return result

1 到 20 的乘积：

product = 1
for number in range(1, 21):
    product *= number
print(product)

前 10 项斐波那契：
```
previous = 0
current = 1

for _ in range(10):
    print(previous)
    previous, current = current, previous + current
```
输出从 0 开始的前 10 项。并行赋值会先计算右边，再分别更新左边，因此不需要临时变量。

递归求和：

def sum_to(n):
    if n <= 0:
        return 0
    return n + sum_to(n - 1)

print(sum_to(5))  # 15

冒泡排序：

def bubble_sort(values):
    data = values.copy()
    n = len(data)

    for i in range(n - 1):
        for j in range(n - 1 - i):
            if data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]
        print("第", i + 1, "轮：", data)

    return data

选择排序：

def selection_sort(values):
    data = values.copy()
    n = len(data)

    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if data[j] < data[min_index]:
                min_index = j

        data[i], data[min_index] = data[min_index], data[i]
        print("第", i + 1, "轮最小值：", data[i], data)

    return data

二分查找：

def binary_search(values, target):
    low = 0
    high = len(values) - 1

    while low <= high:
        mid = (low + high) // 2
        if values[mid] == target:
            return mid
        if values[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

5.15 常见错误清单#

求最小值时初始值设为 0，导致全为正数时得到错误答案。
顺序查找第一次命中就返回，没有收集全部重复位置。
累乘初始值为 0。
递归缺少终止条件，或参数没有变小。
冒泡和选择的每轮目标混记。
冒泡内层范围没有随轮次缩短。
交换两个变量时丢失其中一个旧值。
二分查找循环条件写成 low < high。
二分查找没有先确保数据有序。
直接在原列表上排序，却继续把原列表当作未排序数据使用。

5.16 过关检查#

能不调用 min()、max() 手工求最值。
能写出查找第一个位置和查找全部位置的函数。
能完成 5! 的循环推演。
能展开一个递归函数的调用和返回过程。
能手工写出冒泡排序每轮结果。
能手工写出选择排序每轮结果。
能正确更新二分查找的 low/high，并写出中间值序列。
能解释排序和查找问题中的空列表、单元素、重复值和不存在目标。
完成第 5 周作品后，原列表与返回的排序列表关系清楚。
第一阶段算法过程题能够脱离电脑独立完成。

第 5 周：查找、递推、递归与排序

本周目标#

5.1 算法不是某一段固定代码#

5.2 最值与平均值#

使用内置函数#

手工求最小值#

5.3 顺序查找#

找第一个位置#

找全部位置#

5.4 累加、计数与累乘#

累加#

条件累加#

累乘#

5.5 递推#

斐波那契数列#

5.6 递归#

阶乘#

递归求列表和#

递归和循环的选择#

5.7 冒泡排序#

完整实现#

手工推演#

为什么内层范围越来越短#

5.8 选择排序#

冒泡与选择的区别#

5.9 二分查找#

手工推演#

循环条件为什么是 low <= high#

二分一定比顺序查找快吗#

5.10 怎样写算法过程题#

5.11 本周作品一：查找与统计工具包#

5.12 本周作品二：排序推演表#

5.13 独立练习#

A. 快速判断题#

B. 编程题#

5.14 练习答案与解释#

A. 快速判断题答案#

B. 编程题参考答案#

5.15 常见错误清单#

5.16 过关检查#

循环条件为什么是 `low <= high`#