日期：2005-5-25 10:45:55 来源: 编辑： 175
它的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排 序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
在希尔排序中，子序列的构成不是简单地“逐段分割”，而是将相隔某个“增量”的记录组成一个子序列。如在第一趟排序时的增量为7，即将相隔为7的元素编成一组进行直接插入排序。第二趟排序时的增量为3，增量进一步缩小。由于在这两趟的插入排序中在子序列中逆序的关键字是跳跃式地移动，从而使得在进行最后一趟增量为1的插入排序时，序列已基本有序，只要作少量比较和移动即可完成排序，因此希尔排序的时间复杂度较直接插入排序低。
下面用算法语言描述的希尔排序:
希尔排序中增量序列的选取是一个复杂的问题，涉及到一些数学上尚未解决的难题。我们不想加以详细讨论。到目前仅得出部分结论：如当增量序列为d[k]=2t-k+l -1时，希尔排序的运行时间为O(n3/2)，其中1≤k≤t≤└log2(n＋1)┘。增量序列还可以有各种取法, 如d[k]=2t-k，（d=…,9,5,3,2,1）。但请注意：应使增量序列中的值没有除1之外的公因子，并且最后一个增量值必须等于1。
基本思想：将整个无序序列分割成若干小的子序列分别进行插入排序。
序列分割方法：将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，排序就完成。增量序列一般采用：ht=2t-1,1≤t≤[log2n]，其中n为待排序序列的长度。
void prshl(p,n)
int ndouble p[]
{
int k,j,i
double t
k=n/2
while(k>0)
{
for(j=kj<=n-1j++)
{
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
}
希尔排序(缩小增量法)
属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序
排序过程：先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止
初始：d＝5
49 38 65 97 76 13 27 49* 55 04
|---------------|
38 27
|--------------|
65 49*
|--------------|
97 55
|---------------|
|76-------------04|
一趟结果
d=3 13 27 49*55 04 49 38 65 97 76
|--------|--------|----------|
27 04 65
|--------|-------|
49* 49 97
|--------|---------|
二趟结果
13 04 49*38 27 49 66 65 97 76
d=1
三趟结果
04 13 27 38 49*49 55 65 76 97
下标 0 1 2 3 4 5 6 7 8 9数组 49 38 65 97 26 13 27 50 55 4 (原数组)
增量=5, [0]=49与[5]=13为一组,互换为 13 49 (排序是从小到大)
[1]=38与[6]=27为一组,互换为 27 38
[2]=65与[7]=50为一组,互换为 50 65
[3]=97与[8]=55为一组,互换为 55 97
[4]=26与[9]=4 为一组,互换为 4 26
增量=5的排序结果是: 13 27 50 55 4 49 38 65 97 26
下标 0 1 2 3 4 5 6 7 8 9
数组 13 27 50 55 4 49 38 65 97 26 (第一趟之后)
增量=2, [0]=13,[2]=50,[4]=4,[6]=38,[8]=97为一组,
互换之后,[0]=4,[2]=13,[4]=38,[6]=50,[8]=97
[1]=27,[3]=55,[5]=49,[7]=65,[9]=26为一组,
互换之后,[1]=26,[3]=27,[5]=49,[7]=55,[9]=65
增量=2的排序结果是: 4 26 13 27 38 49 50 55 97 65
下标 0 1 2 3 4 5 6 7 8 9
数组 4 26 13 27 38 49 50 55 97 65 (第二趟之后)
增量=1, 数组里的10个数据作为一组,其中,
[1]=26有[2]=13互换为 13 26
[8]=97与[9]=65互换为 65 97
增量=1的排序结果是: 4 13 26 27 38 49 50 55 65 97
// C语言测试代码
// 希尔排序法 (自定增量)
#include <stdio.h>
#include <stdlib.h>
void printData(int data[],int n) //打印数组
{
int i
for(i=0i<ni++)
{
printf("%d ",data[i])
}
printf("\n")
}
//希尔排序(从小到大)
void shell(int data[],int count)
{
int offset_a[3]={5,2,1} //每一趟的增量
int len
int pos
int offset
int i,j
int temp
len=sizeof(offset_a)/sizeof(int)
for(i=0i<leni++)
{
offset=offset_a[i]
for(j=offsetj<countj++)
{
temp=data[j]
pos=j-offset
while(temp<data[pos] && pos>=0 && j<=count)
{
data[pos+offset]=data[pos]
pos=pos-offset
}
data[pos+offset]=temp
}
printf("增量=%d,排序结果: ",offset)
printData(data,count)
}
}
int main(void)
{
int data[]={49,38,65,97,26,13,27,50,55,4}
int count
count=sizeof(data)/sizeof(int)
printf("原数组: ")
printData(data,count)
shell(data,count)
printf("\n最后的排序结果: ")
printData(data,count)
return 0
}
