若不设置监视哨,根据上例的分析不难写出希尔排序算 法,请读者自行完成之。下面我们先分析如何设置监 视哨,然后给出具体算法。设某一趟希尔排序的增量 为h,则整个文件被分成h组:(R1,RH1,R2h+1,…), (R2,R1+2,R2h+2, (Rh, RL, R 因为各组中记录之间的距离均为是h,故第1组至第h组 的哨兵位置依次为1-h,2-h,…,0。如果象直接插入 排序算法那样,将待插入记录R:(h1≤iN)在查找插 入位置之前保存到监视哨中,那么必须先计Ri属于哪 组,才能决定使用哪个监视哨来保存Ri。为了避免 这种计算,我们可以将Ri保存到另一个辅肋记录X中, 而将所有监视哨R1,R2h,…,R0的关键字,设置为 小于文件中的任何关键字即可。因为增量是变化的, 所以,各趟排序中所需的监视哨数目也不相同,但是 我们可以按最大增量d1来设置监视哨。若不设置监视哨，根据上例的分析不难写出希尔排序算 法，请读者自行完成之。下面我们先分析如何设置监 视哨，然后给出具体算法。设某一趟希尔排序的增量 为h，则整个文件被分成h组：（R1，Rh+1，R2h+1，…）， （R2，Rh+2，R2h+2，…），…（Rh，R2h，R3h，…）， 因为各组中记录之间的距离均为是h，故第1组至第h组 的哨兵位置依次为1-h，2-h，…，0。如果象直接插入 排序算法那样，将待插入记录Ri（h+1≤i≤N） 在查找插 入位置之前保存到监视哨中，那么必须先计Ri属于哪 一组，才能决定使用哪个监视哨来保存Ri。为了避免 这种计算，我们可以将Ri保存到另一个辅肋记录X中， 而将所有监视哨R1-h，R2-h，…，R0的关键字，设置为 小于文件中的任何关键字即可。因为增量是变化的， 所以，各趟排序中所需的监视哨数目也不相同，但是 我们可以按最大增量d1来设置监视哨