4.3 非数值计算
知识点
1.什么是"非数值计算"
非数值计算：处理对象不是数值（或主要不是数值运算），而是查找、排序、比对、匹配、路径搜索、逻辑推理等问题。
| 数值计算 | 非数值计算 | |
|---|---|---|
| 处理对象 | 数 | 数据元素（记录、字符串、结点） |
| 核心操作 | 算术运算 | 比较与移动 |
| 典型问题 | 求根、求和、求 π | 查找、排序、字符串处理、汉诺塔 |
| 结果 | 一个数值 | 位置、顺序、新序列、步骤 |
为什么重要：现实中大部分数据处理都是非数值的——在 10 万条记录里找一个人、把成绩从高到低排、判断两个文本是否相同。
本小节的四类问题：
- 查找——东西在哪？
- 排序——怎么排队？
- 字符串处理——文字怎么比对与变换？
- 递归类——汉诺塔怎么搬？
2.查找：顺序查找
思路：从第一个元素开始，逐个比较，找到就返回位置，找完没有就报告"不存在"。
# 4-10 顺序查找
def seq_search(a, key):
for i in range(len(a)):
if a[i] == key:
return i # 返回下标
return -1 # 未找到
效率：
- 最好情况：第 1 个就是 → 1 次比较；
- 最坏情况：最后 1 个或不存在 → n 次；
- 平均：约 n/2 次；
- 时间复杂度：O(n)。
优点：对数据没有要求（无序也能查），实现简单； 缺点：数据量大时慢。
Python 里的等价写法：key in a（判断存在）、a.index(key)（取下标）。
3.查找：二分查找（折半查找）
（1）前提与思路
前提（必须满足）：数据已经按顺序排好（有序）。
思路：每次取中间元素与目标比较：
- 相等 → 找到；
- 目标小于中间值 → 只在左半部分继续找；
- 目标大于中间值 → 只在右半部分继续找。
每比较一次，查找范围减半——这是它快的根本原因。
（2）代码实现
# 4-11 二分查找（a 必须已升序排列）
def binary_search(a, key):
low, high = 0, len(a) - 1
while low <= high:
mid = (low + high) // 2
if a[mid] == key:
return mid # 找到
elif a[mid] < key:
low = mid + 1 # 目标在右半区
else:
high = mid - 1 # 目标在左半区
return -1 # 未找到
三个易错点：
- 循环条件是
low <= high（不是<），否则会漏掉最后一个元素； mid用整除//，否则得到小数下标；low = mid + 1、high = mid - 1，不能写成mid（会死循环）。
（3）效率分析（必考）
查找过程示例：在 11 个有序数中找某个值，最多比较 4 次（11 → 5 → 2 → 1）。
| 数据规模 n | 顺序查找最多比较 | 二分查找最多比较 |
|---|---|---|
| 10 | 10 | 4 |
| 100 | 100 | 7 |
| 1 000 | 1 000 | 10 |
| 1 000 000 | 1 000 000 | 20 |
规律：二分查找的比较次数 ≈ log₂n，时间复杂度 O(log n)。
结论（答题落点）：数据量大且有序时，二分查找远优于顺序查找；但二分查找要求先排序，如果只查一次，排序的成本可能超过查找节省的时间。
生活类比：查字典——不会从第一页翻，而是先翻中间，看拼音在哪一半，再继续折半。
4.排序（三种基本排序，必会）
排序：把一组数据按关键字的升序或降序重新排列。
比较维度：比较次数、交换次数、是否稳定、时间复杂度。
（1）冒泡排序（Bubble Sort）
思想：相邻两个比较，逆序就交换。每一轮走完，最大的元素"冒"到末尾。
# 4-12 冒泡排序（升序）
def bubble_sort(a):
n = len(a)
for i in range(n - 1): # 共 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
return a
要点：
- 外层控制轮数（n-1 轮），内层控制比较（
n-1-i次，每轮少一个）； swapped优化：某一轮没发生交换说明已经有序，可提前结束；- 时间复杂度 O(n²)，最好情况（已有序）O(n)；
- 空间 O(1)（原地排序）。
手算示例：[5, 3, 8, 1]
第 1 轮：3 5 1 8 （8 冒到最后）
第 2 轮：3 1 5 8 （5 到位）
第 3 轮：1 3 5 8 （3 到位，完成）
（2）选择排序（Selection Sort）
思想：每一轮在未排序部分找出最小（或最大） 的元素，与未排序部分的第一个位置交换。
# 4-13 选择排序（升序）
def selection_sort(a):
n = len(a)
for i in range(n - 1):
min_idx = i # 假设当前位置最小
for j in range(i + 1, n):
if a[j] < a[min_idx]:
min_idx = j # 记录更小的位置
if min_idx != i: # 交换到前面
a[i], a[min_idx] = a[min_idx], a[i]
return a
特点：
- 每轮只交换一次（最多 n-1 次交换），交换次数最少；
- 比较次数固定为 n(n-1)/2，与初始顺序无关（不能提前结束）；
- 时间复杂度 O(n²)。
与冒泡的核心差别：冒泡"边比边换"，选择"先找最小再换一次"。
（3）插入排序（Insertion Sort）
思想：像整理扑克牌——把每个新元素插入到前面已排好序的部分中的正确位置。
# 4-14 插入排序（升序）
def insertion_sort(a):
for i in range(1, len(a)):
key = a[i] # 待插入的元素
j = i - 1
while j >= 0 and a[j] > key: # 比 key 大的往后挪
a[j + 1] = a[j]
j -= 1
a[j + 1] = key # 插入正确位置
return a
特点：
- 对基本有序的数据效率很高（接近 O(n)）；
- 稳定排序；
- 时间复杂度 O(n²)，最好 O(n)。
（4）三种排序对比表（必背）
| 对比项 | 冒泡排序 | 选择排序 | 插入排序 |
|---|---|---|---|
| 核心动作 | 相邻比较，逆序交换 | 每轮选最小，放到前面 | 取一个，插入已排好的部分 |
| 比较次数 | 约 n²/2（可提前结束） | 固定 n(n-1)/2 | 约 n²/4（有序时 n-1） |
| 交换次数 | 多 | 最少 | 中等（移动多） |
| 能否提前结束 | 能（无交换即有序） | 不能 | 部分能（已就位即停） |
| 时间复杂度 | O(n²)，最好 O(n) | O(n²)，始终 | O(n²)，最好 O(n) |
| 稳定性 | 稳定 | 不稳定（长距离交换） | 稳定 |
| 适用场景 | 教学演示、小数据 | 交换成本高的场合 | 数据基本有序 |
记忆口诀：冒泡"换相邻"、选择"选最小"、插入"打扑克"。
重要提醒：这三种排序都是 O(n²)；实际工程中用快速排序／归并排序（O(n log n)） 或直接用 sorted()。
5.字符串处理（非数值计算的另一大类）
（1）回文判断
回文：正着读和倒着读相同的字符串（如 "level"、"上海自来水来自海上"）。
# 4-15 判断回文（两种写法）
def is_palindrome1(s):
return s == s[::-1] # 切片反转后比较，最简洁
def is_palindrome2(s):
i, j = 0, len(s) - 1
while i < j: # 首尾向中间夹逼
if s[i] != s[j]:
return False
i += 1
j -= 1
return True
两种思路对比：
- 切片法：代码最短，但额外占 O(n) 空间（生成了新字符串）；
- 双指针法：不用额外空间（O(1)），比较次数最多 n/2。
若要忽略大小写与空格：先 s = s.lower().replace(" ", "") 再判断。
（2）字符统计
# 4-16 统计字符串中各类字符的个数
s = input("请输入一行字符：")
letters = digits = spaces = others = 0
for ch in s:
if ch.isalpha():
letters += 1
elif ch.isdigit():
digits += 1
elif ch.isspace():
spaces += 1
else:
others += 1
print(f"字母{letters} 数字{digits} 空格{spaces} 其他{others}")
要点：初始化四个计数器 → 遍历一次 → 用 if-elif 分类累加。这是"计数模式"的典型应用。
（3）大小写转换与反转
s = "Hello World"
print(s.upper()) # HELLO WORLD
print(s.lower()) # hello world
print(s.swapcase()) # hELLO wORLD
print(s[::-1]) # dlroW olleH（反转）
注意：字符串不可变，这些方法都返回新字符串，必须赋值接收。
（4）子串统计与替换
text = "abcabcabc"
print(text.count("abc")) # 3（出现次数）
print(text.find("b")) # 1（首次出现的下标）
print(text.replace("a", "X")) # XbcXbcXbc
print("abc" in text) # True（成员判断）
易错：find 找不到返回 -1（不是 0，也不是报错）；而 index 找不到会报错。
（5）编码转换类问题（与 3.4 呼应）
# 统计字母出现频率（可用于破解替换密码）
freq = {}
for ch in "hello":
freq[ch] = freq.get(ch, 0) + 1
print(freq) # {'h': 1, 'e': 1, 'l': 2, 'o': 1}
要点：freq.get(ch, 0) + 1 是"字典计数"的标准写法——键不存在时取 0，避免 KeyError。
6.递归经典：汉诺塔
（1）问题描述
有 A、B、C 三根柱子，A 上有 n 个大小不同的圆盘（小在上）。要求把全部圆盘移到 C，规则：
- 每次只能移动一个圆盘；
- 大盘不能压在小盘上。
（2）递归思路（三步分解）
要把 n 个盘从 A 移到 C（借助 B）：
- 先把上面 n-1 个盘从 A 移到 B（借助 C）；
- 把最大的第 n 个盘从 A 移到 C（一步）；
- 再把 n-1 个盘从 B 移到 C（借助 A）。
终止条件：n == 1 时，直接从 A 移到 C。
（3）代码
# 4-17 汉诺塔
def hanoi(n, a, b, c): # n 个盘从 a 借助 b 移到 c
if n == 1:
print(f"{a} -> {c}") # 只剩一个，直接搬
else:
hanoi(n - 1, a, c, b) # ① n-1 个从 a 借助 c 移到 b
print(f"{a} -> {c}") # ② 最大的从 a 移到 c
hanoi(n - 1, b, a, c) # ③ n-1 个从 b 借助 a 移到 c
hanoi(3, "A", "B", "C")
3 个盘的输出（7 步）：
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C
（4）复杂度：为什么 n=64 搬不完
移动次数递推式：T(n) = 2T(n-1) + 1，解得 T(n) = 2ⁿ - 1。
| n | 移动次数 |
|---|---|
| 3 | 7 |
| 10 | 1023 |
| 20 | 1 048 575 |
| 64 | 约 1.8 × 10¹⁹ |
传说：僧侣搬 64 个盘，每秒一步不停，需要约 5845 亿年——远超宇宙年龄。这是"指数级增长"最著名的例子。
教学价值：汉诺塔完美体现"分解"（把 n 化成 n-1）与"递归"（自己调用自己），用循环极难写清，用递归只需 6 行。
7.综合效率对比表（必背）
| 算法 | 时间复杂度 | 空间复杂度 | 前提／特点 |
|---|---|---|---|
| 顺序查找 | O(n) | O(1) | 无需有序 |
| 二分查找 | O(log n) | O(1) | 必须有序 |
| 冒泡排序 | O(n²) | O(1) | 稳定，可提前结束 |
| 选择排序 | O(n²) | O(1) | 交换次数最少，不稳定 |
| 插入排序 | O(n²)，最好 O(n) | O(1) | 稳定，适合基本有序 |
| 汉诺塔 | O(2ⁿ) | O(n)（递归深度） | 指数级，规模稍大即不可行 |
一句话总结："查找看有没有序，排序看数据乱不乱，递归看规模涨得多快"。
8.易错点清单
| 序号 | 易错点 | 说明 | 正确做法 |
|---|---|---|---|
| 1 | 对无序数据用二分查找 | 结果可能错误 | 先排序，或改用顺序查找 |
| 2 | 二分查找 while low < high | 漏掉最后一个元素 | low <= high |
| 3 | low = mid（不加 1） | 死循环 | low = mid + 1 |
| 4 | 冒泡内层 range(n-1) 每轮不变 | 多做了无效比较 | range(n - 1 - i) |
| 5 | 选择排序以为能提前结束 | 比较次数固定 | 它不能提前结束 |
| 6 | 认为三种排序都是 O(n log n) | 都是 O(n²) | 快排/归并才是 O(n log n) |
| 7 | 字符串 replace 不赋值 | 原串不可变，没变化 | s = s.replace(...) |
| 8 | find 找不到以为返回 0 | 返回 -1 | 用 if idx != -1 判断 |
| 9 | 字典计数直接 d[ch] += 1 | 首次会 KeyError | 用 d.get(ch, 0) + 1 |
| 10 | 汉诺塔递归参数顺序写错 | 结果错 | 记住"借助谁、移到谁"三个参数的含义 |
| 11 | 回文判断忘记统一大小写 | 大小写不同判成 False | 先 lower() |
| 12 | 交换写成 a = b; b = a | 两个变量变成同值 | a, b = b, a 或借助临时变量 |
9.速查表
| 序号 | 考点 | 结论 |
|---|---|---|
| 1 | 非数值计算的核心操作 | 比较与移动 |
| 2 | 顺序查找复杂度 | O(n) |
| 3 | 顺序查找前提 | 无（无序也可以） |
| 4 | 二分查找前提 | 数据有序 |
| 5 | 二分查找复杂度 | O(log n) |
| 6 | 二分循环条件 | low <= high |
| 7 | 二分 mid 计算 | (low + high) // 2 |
| 8 | 二分更新 | low = mid + 1／high = mid - 1 |
| 9 | 冒泡排序思想 | 相邻比较，逆序交换 |
| 10 | 冒泡每轮效果 | 最大（小）值到位 |
| 11 | 冒泡优化 | swapped 标志提前结束 |
| 12 | 选择排序思想 | 每轮选最小，交换一次 |
| 13 | 选择排序比较次数 | 固定 n(n-1)/2 |
| 14 | 插入排序思想 | 打扑克，插入已排好的部分 |
| 15 | 插入排序优势 | 基本有序时接近 O(n) |
| 16 | 三种排序复杂度 | 都是 O(n²) |
| 17 | 交换两个变量 | a, b = b, a |
| 18 | 回文最简写法 | s == s[::-1] |
| 19 | 双指针法空间 | O(1) |
| 20 | find 找不到 | 返回 -1 |
| 21 | 字典计数写法 | d.get(ch, 0) + 1 |
| 22 | 汉诺塔递推式 | T(n) = 2ⁿ − 1 |
| 23 | 汉诺塔复杂度 | O(2ⁿ)（指数级） |
| 24 | 汉诺塔递归三步骤 | 移 n−1 到辅助柱 → 移最大盘 → 移 n−1 到目标柱 |
10.课堂提示（讲课参考）
- 二分查找用"猜数字"复现：1~100 猜数字，让学生体会"每次砍一半"的威力，再引出
O(log n)。 - 三种排序用同一组数据手算：
[5, 3, 8, 1, 9, 2]，让学生用三种方法各排一遍，比较次数写在黑板上对比，比看代码直观。 - 冒泡用"气泡上浮"动画、选择用"选班长"、插入用"整理扑克"——三个生活比喻分别对应三种排序，学生不易混。
- 汉诺塔先让学生用手搬 3 个盘，记录步数 7 步，再问"4 个盘要几步"（15 步），最后推出 2ⁿ−1，指数增长的震撼比公式更有说服力。
- 二分查找的边界 bug 让学生踩一次（写
low < high或low = mid），在 10 个元素的数组上找最后一个元素会失败——错误记忆最牢。