8.2.3 希尔排序

教材导航 · 第8章

原书定位

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

按间隔 dd 将下标同余的记录分组,对各组直接插入排序;逐步缩小间隔,最终 d=1d=1 完成全表插入排序。组内记录在物理位置上不一定相邻。

空间 O(1)O(1),不稳定。时间依赖增量序列,不能把某个经验幂次写成所有希尔排序的统一复杂度。教材常用增量折半序列,其最坏为 O(n2)O(n^2);手算按题设增量逐组处理。

希尔排序各增量的分组过程

希尔排序各增量的分组过程,原书P342。

对应练习

8.2 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P341,PDF第353页

原书对照,原书P342,PDF第354页