希尔排序算法

如果“完全”看不懂，说明你没有看该算法的介绍文本，建议去仔细地看一下！然后对照此程序（如有条件可以对此程序进行单步跟踪运行以观察其运行方式）理解该算法

Gap=8:462 17 512 908 170 897 275 653 503 154 509 612 677 765 703 94

Gap=8:462 17 512 908 170 897 275 653 503 154 509 612 677 765 703 94

Gap=8:462 17 509 908 170 897 275 653 503 154 512 612 677 765 703 94

Gap=8:462 17 509 612 170 897 275 653 503 154 512 908 677 765 703 94

Gap=8:462 17 509 612 170 897 275 653 503 154 512 908 677 765 703 94

Gap=8:462 17 509 612 170 765 275 653 503 154 512 908 677 897 703 94

Gap=8:462 17 509 612 170 765 275 653 503 154 512 908 677 897 703 94

Gap=8:462 17 509 612 170 765 275 94 503 154 512 908 677 897 703 653

Gap=4:170 17 509 612 462 765 275 94 503 154 512 908 677 897 703 653

Gap=4:170 17 509 612 462 765 275 94 503 154 512 908 677 897 703 653

Gap=4:170 17 275 612 462 765 509 94 503 154 512 908 677 897 703 653

Gap=4:170 17 275 94 462 765 509 612 503 154 512 908 677 897 703 653

Gap=4:170 17 275 94 462 765 509 612 503 154 512 908 677 897 703 653

Gap=4:170 17 275 94 462 154 509 612 503 765 512 908 677 897 703 653

Gap=4:170 17 275 94 462 154 509 612 503 765 512 908 677 897 703 653

Gap=4:170 17 275 94 462 154 509 612 503 765 512 908 677 897 703 653

Gap=4:170 17 275 94 462 154 509 612 503 765 512 908 677 897 703 653

Gap=4:170 17 275 94 462 154 509 612 503 765 512 908 677 897 703 653

Gap=4:170 17 275 94 462 154 509 612 503 765 512 908 677 897 703 653

Gap=4:170 17 275 94 462 154 509 612 503 765 512 653 677 897 703 908

Gap=2:170 17 275 94 462 154 509 612 503 765 512 653 677 897 703 908

Gap=2:170 17 275 94 462 154 509 612 503 765 512 653 677 897 703 908

Gap=2:170 17 275 94 462 154 509 612 503 765 512 653 677 897 703 908

Gap=2:170 17 275 94 462 154 509 612 503 765 512 653 677 897 703 908

Gap=2:170 17 275 94 462 154 509 612 503 765 512 653 677 897 703 908

Gap=2:170 17 275 94 462 154 509 612 503 765 512 653 677 897 703 908

Gap=2:170 17 275 94 462 154 503 612 509 765 512 653 677 897 703 908

Gap=2:170 17 275 94 462 154 503 612 509 765 512 653 677 897 703 908

Gap=2:170 17 275 94 462 154 503 612 509 765 512 653 677 897 703 908

Gap=2:170 17 275 94 462 154 503 612 509 653 512 765 677 897 703 908

Gap=2:170 17 275 94 462 154 503 612 509 653 512 765 677 897 703 908

Gap=2:170 17 275 94 462 154 503 612 509 653 512 765 677 897 703 908

Gap=2:170 17 275 94 462 154 503 612 509 653 512 765 677 897 703 908

Gap=2:170 17 275 94 462 154 503 612 509 653 512 765 677 897 703 908

Gap=1:17 170 275 94 462 154 503 612 509 653 512 765 677 897 703 908

Gap=1:17 170 275 94 462 154 503 612 509 653 512 765 677 897 703 908

Gap=1:17 94 170 275 462 154 503 612 509 653 512 765 677 897 703 908

Gap=1:17 94 170 275 462 154 503 612 509 653 512 765 677 897 703 908

Gap=1:17 94 154 170 275 462 503 612 509 653 512 765 677 897 703 908

Gap=1:17 94 154 170 275 462 503 612 509 653 512 765 677 897 703 908

Gap=1:17 94 154 170 275 462 503 612 509 653 512 765 677 897 703 908

Gap=1:17 94 154 170 275 462 503 509 612 653 512 765 677 897 703 908

Gap=1:17 94 154 170 275 462 503 509 612 653 512 765 677 897 703 908

Gap=1:17 94 154 170 275 462 503 509 512 612 653 765 677 897 703 908

Gap=1:17 94 154 170 275 462 503 509 512 612 653 765 677 897 703 908

Gap=1:17 94 154 170 275 462 503 509 512 612 653 677 765 897 703 908

Gap=1:17 94 154 170 275 462 503 509 512 612 653 677 765 897 703 908

Gap=1:17 94 154 170 275 462 503 509 512 612 653 677 703 765 897 908

Gap=1:17 94 154 170 275 462 503 509 512 612 653 677 703 765 897 908

上文是对文中所给数组排序的过程。其中，gap=表示这一趟的取值间隔。

至于算法思想，由于篇幅关系无法在此给出，请参考 希尔排序算法 的介绍文本。

以下是我写的C程序，上面的输出系由该程序创建

//---------------------------------------------------------------------------

#include <stdioh>

#include <stdlibh>

#define M 16

#define FMT "%d "

typedef int data;

void out(data p,int n)

{

int i;

for (i = 0; i<n; i++) {

printf(FMT,p[i]);

}

putchar('\n');

}

void shell(data p,int n)

{

int i,j,gap;

data temp;

gap=n/2;

while (gap>0)

{

for (i=gap; i<n; i++)

{

j=i-gap;

while (j>=0)

if (p[j]>p[j+gap])

{

temp=p[j];

p[j]=p[j+gap];

p[j+gap]=temp;

j-=gap;

}

else break;

printf("Gap=%d:",gap);

out(p,n);

}

putchar('\n');

gap/=2;

}

}

int main(int argc, char argv[])

{

data a[]={503,17,512,908,170,897,275,653,462,154,509,612,677,765,703,94};

int i;

for (i=0; i<M; i++) printf(FMT,a[i]);

putchar('\n');

shell(a,M);

putchar('\n');

system("pause");

return 0;

}

//---------------------------------------------------------------------------

procedure prshl(p,n)

begin

k:=n/2;

while(k>0) do begin

for j:=k to n-1 do begin

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

while((i>=0) and (p[i]>t)) do begin

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

end;

p[i+k]:=t;

end;

k:=k/2;

end;

end;

大体上就是这样

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n^2）的第一批算法之一。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

第一轮排序：设置step步长为4，根据步长将数组分为四组，{1,3}， {4,2}，{6,5}，{0,9} 进行两两比较。

将i=step，开始往后遍历。如果a[i]>a[i-step]交换数据。得到第一轮排序结果：1 2 5 0 3 4 6 9

第二轮排序：设置step步长为2，根据步长继续两两分组，比较数据大小。得到第二轮排序结果：1 0 3 2 5 4 6 9

第三轮排序：设置step步长为1，根据步长继续两两分组，比较数据大小。得到第三轮排序结果：0 1 2 3 4 5 6 9

输出结果：

Shell sort:

0, 1, 2, 3, 4, 5, 6, 9,

希尔排序的关键并不是随便分组后各自排序，而是将相隔某个step 的记录组成一个子序列， 实现跳跃式的移动，使得排序的效率提高。

希尔排序的时间复杂度是O（nlogn），效率上比冒泡排序，直接插入排序，简单选择排序的O（n^2）要高。

以上就是关于希尔排序算法全部的内容，包括:希尔排序算法、用pascal语言实现希尔排序算法、希尔排序等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！