8.1 排序的基本概念

排序把记录按关键字重排。稳定性指相等关键字的相对次序不变；它是算法性质，不等于结果是否有序。内部排序数据可全驻内存，外部排序的主要成本是磁盘I/O。

手工推演与代码

记录(2,a),(1,x),(2,b)稳定升序应为(1,x),(2,a),(2,b)。

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

正确性与错解反馈

正确性来自每一趟扩大已确定区域且不破坏未处理数据。把原地等同稳定；只报平均复杂度；忽略比较次数、移动次数与空间。

迁移训练

判断选择排序是否稳定并构造反例。答案通常不稳定，如(2,a),(2,b),(1)首轮交换会颠倒两个2。