8.1 排序的基本概念·选择题讲评

评价排序要同时看最好、平均、最坏时间，辅助空间、稳定性、是否适应初始有序。

手工推演与代码

直接插入在近乎有序数据上接近线性；归并始终nlogn但需线性辅助空间。

代码实现必须保持当前有序区、堆区或归并段的不变量，并对空数组、单元素、重复键和逆序输入测试。

正确性与错解反馈

正确性来自每一趟扩大已确定区域且不破坏未处理数据。认为稳定算法一定快；把关键字相等当记录完全相同。

迁移训练

多选：插入稳定、归并稳定、堆排序不稳定、快速排序通常不稳定。答案全选。