8.1.1 排序的定义与稳定性

教材导航 · 第8章

原书定位

印刷页P338起,对应PDF第350页。下文为目视整理的知识提要;完整内容见原书对照。

稳定排序要求相同关键字的记录在输出中保持原来的相对次序,而非绝对下标不变。证明不稳定只需找到一组发生逆序的反例;一次具体排序恰好没改变相对次序,不能证明算法稳定。

内部排序常分插入、交换、选择、归并和基数等方法。比较与移动都计入时间;减少关键字比较不一定减少记录移动。稳定性不直接衡量算法优劣,是否需要取决于应用。

对应练习

8.1 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P338,PDF第350页