将R[i]临时保存位tmp，对相隔d个位置一组采用直接插入排序

Question

7、补充BEGIN-END之间的内容，完成希尔排序算法
#include <stdio.h>
typedef int KeyType;    //定义关键字类型为int
typedef char InfoType;
typedef struct
{    KeyType key;        //关键字项
    InfoType data;        //其他数据项，类型为InfoType
} RecType;                //查找元素的类型
void ShellSort(RecType R[],int n) //希尔排序算法
{    int i,j,d;
    RecType tmp;
    d=n/2;                    //增量置初值
    while (d>0)
    {    for (i=d;i<n;i++)     //对所有组采用直接插入排序
        {    
/**********BEGIN**********/
/*
将R[i]临时保存位tmp,对相隔d个位置一组采用直接插入排序
j定位为i后d位，将关键字大于R[j].key的记录后移d位
在第j+d位插入tmp
*/

    
/**********END**********/
        }
        printf("  d=%d: ",d); DispList(R,n);
        d=d/2;                //减小增量
    }
}

Answer 1

tmp = R[i];
j = i - d;
while (j >= 0 && tmp.key < R[j].key) {
R[j + d] = R[j];
j -= d;
}
R[j + d] = tmp;