1 排序思想：
第1趟：取一正整数d1（d1<n）作为第一个增量，对所有间隔为d1的记录进行直接插入排序。例如，对{a[k]，a[k+d1]，a[k+2d1]，……}执行直接插入排序，其中，k=0，1，2，……，d1-1
第2趟：取一正整数d2（d2<d1），重复上一步的操作
直到所取的增量为1
例如，原始数据：
第1趟排序，取增量为5，如上图，颜色相同的在同一组，对每组进行直接插入排序：
第2趟排序，取增量为3，如上图，颜色相同的在同一组，对每组进行直接插入排序：
第3趟排序，取增量为1，即对上一步的结果进行直接插入排序：
2 算法实现：
// 根据增量序列dk[]对num[]进行希尔排序
void shell_sort(int num[],int num_len,int dk[],int dk_len){
int k;
for(k=0;k<dk_len;k++)
shell_pass(num,num_len,dk[k]);
}
// 根据增量d对num[]进行一次希尔排序
// 即对所有间隔为d的记录进行直接插入排序
void shell_pass(int num[],int num_len,int d){
int i,j,k,key;
for(i=d;i<num_len;i++){
// 将num[i]插入到指定位置
key=num[i];
j=i-d;
while(j>=0&&num[j]>key){
num[j+d]=num[j];
j-=d;
}
num[j+d]=key;
}
}3 性能分析：
3.1 空间复杂度：如上代码，仅在交换数据时使用一个辅助空间，空间复杂度是O(1)
3.2 时间复杂度：O（nlogn）-O（n^2）
3.3 稳定性：不稳定
