8.2.3 希尔排序
原书定位
印刷页P341起,对应PDF第353页。下文为目视整理的知识提要;完整内容见原书对照。
按间隔 将下标同余的记录分组,对各组直接插入排序;逐步缩小间隔,最终 完成全表插入排序。组内记录在物理位置上不一定相邻。
空间 ,不稳定。时间依赖增量序列,不能把某个经验幂次写成所有希尔排序的统一复杂度。教材常用增量折半序列,其最坏为 ;手算按题设增量逐组处理。

希尔排序各增量的分组过程,原书P342。
对应练习
关联知识
原书对照
展开原书对照截图


原书定位
印刷页P341起,对应PDF第353页。下文为目视整理的知识提要;完整内容见原书对照。
按间隔 将下标同余的记录分组,对各组直接插入排序;逐步缩小间隔,最终 完成全表插入排序。组内记录在物理位置上不一定相邻。
空间 ,不稳定。时间依赖增量序列,不能把某个经验幂次写成所有希尔排序的统一复杂度。教材常用增量折半序列,其最坏为 ;手算按题设增量逐组处理。

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

