R[j+d]=R[0]; //插入R[i]到正确的位置上
} //endif
} //ShellPass
void ShellSort(SeqList R)
{
int increment=n; //增量初值，不妨设n>0
do {
increment=increment/3+1; //求下一增量
ShellPass(R，increment); //一趟增量为increment的Shell插入排序
}while(increment>1)
} //ShellSort
注意：
当增量d=1时，ShellPass和InsertSort基本一致，只是由于没有哨兵而在内循环中增加了一个循环判定条件"j>0"，以防下标越
界。
2.设监视哨的shell排序算法
具体算法【参考书目[12] 】
算法分析
1.增量序列的选择
Shell排序的执行时间依赖于增量序列。
好的增量序列的共同特征：
① 最后一个增量必须为1;
② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
有人通过大量的实验，给出了目前较好的结果：当n较大时，比较和移动的次数约在n l.25 到1.6n 1.25 之间。
2.Shell排序的时间性能优于直接插入排序
希尔排序的时间性能优于直接插入排序的原因：
①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
②当n值较小时，n和n 2 的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n 2 )差别不大。
③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量d i 逐渐缩小，分组数逐渐
减少，而各组的记录数目逐渐增多，但由于已经按d i-1 作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快
因此，希尔排序在效率上较直接插人排序有较大的改进。
3.稳定性
希尔排序是不稳定的。参见上述实例，该例中两个相同关键字49在排序前后的相对次序发生了变化。
