基本思想：將整個無序序列分割成若干小的子序列分別進行插入排序。 

序列分割方法：將相隔某個增量h的元素構成一個子序列。在排序過程中，逐次減小這個增量，最后當h減到1時，進行一次插入排序，排序就完成。增量序列一般采用：ht=2t-1,1≤t≤[log2n]，其中n為待排序序列的長度。 

C函數如下： 

void prshl(p,n) 

int n;double p[]; 

{ 

int k,j,i; 

double t; 

k=n/2; 

while(k>0) 

{ 

for(j=k;j<=n-1;j++) 

{ 

t=p[j];i=j-k; 

while((i>=0)&&(p[i]>t)) 

{ 

p[i+k]=p[i];i=i-k; 

} 

p[i+k]=t; 

} 

k=k/2; 

} 

return; 

}