表插入排序的基本操作仍是将一个记录插 入到已排好序的有序表中。和直接插入排序相 比,是以修改2n次指针值代替移动记录,排序 过程中所需进行的关键字之间的比较次数相同。 其时间复杂度认为O(n2) 内部排序 上面的排序后形成的表只能进行顺序查找, 如果希望对该表进行随机查找,如折半查找, 就需要对该表的记录进行重新排序。 希尔排序 基本思想:先将整个待排记录序列分割成为若 数据结构 干子序列分别进行直接插入排序,待整个序列 中的记录“基本有序”时,再对全体记录进行 一次直接插入排序。 希尔排序的特点:子序列的构成不是简单的 逐段分割”,而是,将(位置)相隔某个“增 量”的记录组成一个子序列。 >增量序列的选择 排希尔取法:dHn/2」ddo/21 di+1}=Ldil/2」…最后一个增量必须等于1 24每一个增量对应一趟希尔排序12 数 据 结 构 之 内 部 排 序 23 表插入排序的基本操作仍是将一个记录插 入到已排好序的有序表中。和直接插入排序相 比，是以修改2n次指针值代替移动记录，排序 过程中所需进行的关键字之间的比较次数相同。 其时间复杂度认为O（n2）。 上面的排序后形成的表只能进行顺序查找， 如果希望对该表进行随机查找，如折半查找， 就需要对该表的记录进行重新排序。 数 据 结 构 之 内 部 排 序 24 ¾ 希尔排序 ¾ 基本思想：先将整个待排记录序列分割成为若 干子序列分别进行直接插入排序，待整个序列 中的记录“基本有序”时，再对全体记录进行 一次直接插入排序。 ¾ 希尔排序的特点：子序列的构成不是简单的 “逐段分割”，而是，将( 位置 ) 相隔某个“增 量”的记录组成一个子序列。 ¾ 增量序列的选择： 希尔取法：d[0]= n / 2 d[1]= d[0] / 2...... d[i+1]= d[i] / 2 ... 最后一个增量必须等于1 每一个增量对应一趟希尔排序