内部排序

本课对应 408 考纲中的 内部排序。目标不是记一句定义，而是能在选择题中辨析条件，在综合题中写出推导。

核心模型

稳定性描述相等关键字的相对次序；归并稳定且最坏 O(n log n)，快速排序最坏 O(n²)。

做题时先写清对象、状态、下标范围和计量单位。遇到算法要写不变量与复杂度；遇到硬件、系统或网络状态题，要按时间顺序列出每次状态变化。

推导与例题

插入排序在近乎有序序列上移动少；堆排序最坏 O(n log n) 且额外空间 O(1)。

严格作答分四步：确定已知量；选择定义或公式；逐步代入；检查边界和单位。若题目改变缓存容量、页框数、窗口或输入规模，应重新模拟，不能照搬结论。

高频陷阱

不能只背平均复杂度：408 常同时考稳定性、最好/最坏、辅助空间和初始序列敏感性。

判断一个选项时，要找出其中的量词和前提。“一定”“任何”“只要”往往需要反例检查。相似概念必须成对区分，并能各举一个成立与不成立的例子。

本课验收

1. 完成单选，并解释三个错误项具体违反了什么条件。
2. 完成多选；漏选与多选都按错误处理。
3. 独立完成计算或应用题，保留中间过程。
4. 24 小时后不看正文重新作答一次。

只会复述概念不算完成；能算、能画状态、能用反例排错才算掌握。