8.6.2 内部排序算法的应用
原书定位
印刷页P381起,对应PDF第393页。下文为目视整理的知识提要;完整内容见原书对照。
规模小或基本有序时,直接插入常合适;需要稳定且保证 可用归并;原地且保证最坏对数线性时间可用堆;一般数组排序可考虑合理选枢轴的快速排序;值域小或位数少时可考虑计数、基数。
选择还需考虑记录大小、存储方式、是否要前 项、辅助空间和稳定性。记录很大时可排序指针或索引,减少搬运;链表则适合通过重接指针归并。
基于二元比较的通用排序,最坏比较次数至少为 。该下界不约束利用有限值域或数位结构的非比较排序。
对应练习
关联知识
原书对照
展开原书对照截图

