1. 排序到底改变了什么？
排序把记录按照一个或多个键重新排列。记录中的其他字段必须跟着键一起移动；不是把分数排好后，再随意配回姓名。
升序意味着相邻键满足 key(a[i]) <= key(a[i+1])；降序反过来。允许重复值，排序结果不要求严格递增。
2. 记录、键和比较规则
学生记录可以包含姓名、分数、班级。以分数为键排序，不会改变姓名与分数的对应关系。多关键字使用元组：先比较第一项，相同时再比较第二项。
3. 用 Python 排序
students = [
{"name": "小林", "score": 90, "class": 2},
{"name": "小周", "score": 80, "class": 1},
{"name": "小陈", "score": 90, "class": 1},
]
by_score = sorted(students, key=lambda s: s["score"])
by_score_desc = sorted(students, key=lambda s: s["score"], reverse=True)
by_class_score = sorted(students, key=lambda s: (s["class"], -s["score"]))
print([s["name"] for s in by_score]) # 小周、小林、小陈
sorted 返回新列表，原列表不变。list.sort 原地修改列表，返回 None；不要写 a = a.sort()。两者都支持 key、reverse，并保证稳定性。
4. 内部排序与外部排序
数据及算法所需的工作空间能放进内存时，可进行内部排序；超过内存容量时，需要把数据分块处理，并通过外部文件保存有序段。外排重点包括块大小、缓冲区和读写轮数。不要把原书旧硬盘的毫秒数当作现代设备的固定指标。
5. 比较排序与非比较排序
比较排序依靠键的大小比较。对任意互异键排序，比较模型的最坏情况及平均比较次数下界为 Ω(n log n)。这不是“每一个输入都至少要比较 n log n 次”。
计数排序等利用有限整数范围，时间通常写为 O(n + K)，K 为键范围。它没有违反比较模型下界，因为使用了额外条件。本套教材以比较排序为主。计数、桶式方法和基数排序各有键类型、范围或分布方面的条件；不能把“非比较”直接理解为任意输入都线性。
6. 如何分析排序成本？
明确 n 是记录数量，再统计键比较、交换、元素写入和额外空间。字符串键比较还可能依赖字符串长度。一次交换不等于一次写入；不同实现必须统一口径才能比较。大 O 不是实际秒数，小数据上的常数也很重要。Python 列表存放对象引用，交换通常移动引用，不是把记录的所有字段逐字节复制；原书的“指针数组排序”思想可对应到这种间接访问。
7. 稳定性：相等键保留原顺序
5A 和 5B 的键都为 5，标签 A、B 只是区分记录身份。稳定排序应保留它们原来的相对先后。稳定不等于输出有序；不稳定算法某一次也可能碰巧保留顺序。
稳定性适合多次按不同字段排序：先按次要键，再稳定地按主要键排序。也可以把原始位置作为次要键，建立 (key, original_index) 的全序规则。
8. 装饰、排序、还原
records = [(5, "A"), (2, "X"), (5, "B")]
decorated = [(row[0], i, row) for i, row in enumerate(records)]
result = [row for _, _, row in sorted(decorated)]
print(result) # [(2, "X"), (5, "A"), (5, "B")]
原位置参与比较后，即使底层算法没有稳定性保证，也可得到按原始顺序打破平局的结果；额外装饰数据占 O(n) 空间。
9. 选择算法前先问哪些问题？
数据规模、是否近乎有序、稳定性、更新频率、键比较成本、额外内存，以及数据是否需要从文件读取，都影响选择。不要沿用原文“几十、1000”等硬阈值；阈值应由实际环境测量。实际 Python 任务通常先考虑内置排序，而不是因为学过快排就重写它。
| 算法 | 平均时间 | 最坏时间 | 稳定性（常规实现） |
|---|---|---|---|
| 冒泡、插入 | O(n²) | O(n²) | 稳定 |
| 交换式选择 | O(n²) | O(n²) | 不稳定 |
| 希尔 | 取决于增量序列 | 折半序列可为 O(n²) | 不稳定 |
| 快速 | O(n log n) | O(n²) | 不稳定 |
| 归并 | O(n log n) | O(n log n) | 稳定（相等取左） |
| 堆排序 | O(n log n) | O(n log n) | 不稳定 |
堆排序在原书中仅作分类说明，本套不展开实现。优化冒泡和插入的最好情况可达 O(n)，表格中的平均/最坏不能代替最好情况。
10. 本套教材的约定与校正
数组下标从 0 开始，演示标签不参与键比较。原文的 OCR 混淆了 O(n)、O(n²) 等公式；本套统一纠正。常规选择排序、希尔排序和原地快排不稳定；稳定归并排序并不“慢到必须放弃稳定性”。