8.6.2 内部排序算法的应用

教材导航 · 第8章

原书定位

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

规模小或基本有序时,直接插入常合适;需要稳定且保证 O(nlog⁡n)O(n\log n) 可用归并;原地且保证最坏对数线性时间可用堆;一般数组排序可考虑合理选枢轴的快速排序;值域小或位数少时可考虑计数、基数。

选择还需考虑记录大小、存储方式、是否要前 kk 项、辅助空间和稳定性。记录很大时可排序指针或索引,减少搬运;链表则适合通过重接指针归并。

基于二元比较的通用排序,最坏比较次数至少为 ⌈log⁡2(n!)⌉=Ω(nlog⁡n)\lceil\log_2(n!)\rceil=\Omega(n\log n)。该下界不约束利用有限值域或数位结构的非比较排序。

对应练习

8.6 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P381,PDF第393页

原书对照,原书P382,PDF第394页