8.8 本章归纳总结

教材导航 · 第8章

原书定位

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

先从各趟结果的特征识别算法,再核对方向和边界:插入扩大有序前缀,选择与冒泡确定极值,快速确定枢轴,归并扩大有序段,基数逐位建立次序。

性能取决于输入规模、初始次序、关键字结构与实现。具体记录的移动次数、交换次数、比较次数须分别统计;递归空间也应计入辅助空间。

有限整数值域可通过频次统计输出实现线性于 n+kn+k 的时间;只有将值域大小视为固定常量时,才可相对输入规模写成 O(n)O(n) 时间和 O(1)O(1) 计数空间。输出记录若含附属信息且要求稳定,还需保留对应记录,不能仅重建关键字。

关联知识

原书对照

展开原书对照截图

原书对照,原书P398,PDF第410页

原书对照,原书P399,PDF第411页