11 什么是排序？
排序规则、记录关联、稳定性与成本
第 01 题 问题 1
对记录按分数升序排序后，姓名与分数可以重新任意配对吗？
参考答案
不可以。
解析
排序移动的是完整记录或它的引用；键只负责比较，其他字段必须保持关联。
第 02 题 问题 2
带重复值的升序数组应满足相邻项 < 还是 <=？
参考答案
<=。
解析
排序允许重复值；严格 < 会把合法的相等键误判为未排序。
第 03 题 问题 3
a=[3,1,2]; b=sorted(a)。a、b 分别是什么？
参考答案
a=[3,1,2]；b=[1,2,3]。
解析
sorted 返回新列表，不修改原列表。
第 04 题 问题 4
a=[3,1,2]; b=a.sort()。a、b 分别是什么？
参考答案
a=[1,2,3]；b=None。
解析
list.sort 原地排序，返回 None。不要用 a=a.sort() 接收排序结果。
第 05 题 问题 5
原记录 [(90,"A"),(80,"X"),(90,"B")] 按分数稳定排序，结果是什么？
参考答案
[(80,"X"),(90,"A"),(90,"B")]。
解析
90A 在 90B 之前；标签不作为比较键。
第 06 题 问题 6
“不稳定算法每次一定改变相等键顺序”对吗？
参考答案
不对。
解析
不稳定表示不能保证保留，不代表每个输入都会破坏顺序。
第 07 题 问题 7
先稳定按姓名排，再稳定按班级排，最终哪个字段是主要键？
参考答案
班级是主要键，姓名是同班内的次要键。
解析
后一次稳定排序保留相等班级记录在前一次排序中的姓名顺序。
第 08 题 问题 8
任意互异键的比较排序最坏比较次数下界是 O(n log n) 还是 Ω(n log n)？
参考答案
下界用 Ω(n log n)。
解析
O 表示上界。比较决策树必须区分 n! 种排列，其高度至少为 log₂(n!)。
第 09 题 问题 9
计数排序 O(n+K) 为什么不违反比较排序下界？
参考答案
它利用有限整数范围，超出了仅用键大小比较的模型。
解析
K 也必须计入成本；不能对任意类型键都直接使用。
第 10 题 问题 10
20GB 数据、可用工作内存 1GB，应该只用一次内存快排吗？
参考答案
不应；通常先分块生成有序段，再外部归并。
解析
全部数据及工作空间放不进内存，要控制块与缓冲区，并考虑读写轮数。
第 11 题 问题 11
如何用原始位置给相等键制定明确顺序？
参考答案
比较 (key, original_index)。
解析
记录原始位置作为次要键，消除平局；装饰数据会占额外空间。
第 12 题 问题 12
“算法 A 比较少，因此在所有环境下一定更快”对吗？
参考答案
不对。
解析
还需考虑键比较成本、写入、缓存、空间、解释器和输入规模。大 O 不是实际秒数。