8.6 教材 8.6·选择题讲评

横向选择：小且近有序用插入；要求稳定且可用额外空间选归并；最坏保证且原地可用堆；平均实践快常用快排。

手工推演与代码

稳定性：插入、冒泡、归并、计数（正确实现）稳定；希尔、选择、堆、快排通常不稳定。

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

正确性与错解反馈

正确性来自每一趟扩大已确定区域且不破坏未处理数据。只背时间不看空间稳定性；认为原地必不稳定。

迁移训练

要求最坏nlogn且O(1)辅助空间，典型选择堆排序。