8.8 本章归纳总结
原书定位
印刷页P398起,对应PDF第410页。下文为目视整理的知识提要;完整内容见原书对照。
先从各趟结果的特征识别算法,再核对方向和边界:插入扩大有序前缀,选择与冒泡确定极值,快速确定枢轴,归并扩大有序段,基数逐位建立次序。
性能取决于输入规模、初始次序、关键字结构与实现。具体记录的移动次数、交换次数、比较次数须分别统计;递归空间也应计入辅助空间。
有限整数值域可通过频次统计输出实现线性于 的时间;只有将值域大小视为固定常量时,才可相对输入规模写成 时间和 计数空间。输出记录若含附属信息且要求稳定,还需保留对应记录,不能仅重建关键字。
关联知识
原书对照
展开原书对照截图

