8.1.1 排序的定义与稳定性
原书定位
印刷页P338起,对应PDF第350页。下文为目视整理的知识提要;完整内容见原书对照。
稳定排序要求相同关键字的记录在输出中保持原来的相对次序,而非绝对下标不变。证明不稳定只需找到一组发生逆序的反例;一次具体排序恰好没改变相对次序,不能证明算法稳定。
内部排序常分插入、交换、选择、归并和基数等方法。比较与移动都计入时间;减少关键字比较不一定减少记录移动。稳定性不直接衡量算法优劣,是否需要取决于应用。
对应练习
关联知识
原书对照
展开原书对照截图

原书定位
印刷页P338起,对应PDF第350页。下文为目视整理的知识提要;完整内容见原书对照。
稳定排序要求相同关键字的记录在输出中保持原来的相对次序,而非绝对下标不变。证明不稳定只需找到一组发生逆序的反例;一次具体排序恰好没改变相对次序,不能证明算法稳定。
内部排序常分插入、交换、选择、归并和基数等方法。比较与移动都计入时间;减少关键字比较不一定减少记录移动。稳定性不直接衡量算法优劣,是否需要取决于应用。
