希尔排序法.doc

希尔排序法
HYPERLINK"http://baike.baidu.com/view/178698.htm"\t"_blank"希尔排序(缩小增量法)
属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序
排序过程：先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止
初始：d＝5
4938659776132749*5504
4913
|-------------------|
3827
|-------------------|
6549*
|-------------------|
9755
|-------------------|
7604
|-------------------|
一趟结果
132749*55044938659776
d=3
132749*55044938659776
13553876
|------------|------------|------------|
270465
|------------|------------|
49*4997
|------------|------------|
二趟结果
130449*38274955659776
d=1
130449*38274955659776
|----|----|----|----|----|----|----|----|----|
三趟结果
0413273849*4955657697
--------------------------------------------------------------------------------------------
例如对503,17,512,908,170,897,275,653,462，154，509，612，677，765，703，94排序的C语言算法
================================================
功能：希尔排序
输入：数组名称（也就是数组首地址）、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述：
在直接插入排序算法中，每次插入一个数，使有序序列只增加1个节点，
并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离（称为
增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除
多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现
了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中
记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量
对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成
一组，排序完成。
下面的函数是一个希尔排序算法的一个实现，初次取序列的一半为增量，
以后每次减半，直到增量为1。
希尔排序是不稳定的。
=====================================================
*/
voidshell_sort(int*x,intn)
{
inth,j,k,t;
for(h=n/2;h>0;h=h/2)/*控制增量*/
{
for(j=h;j<n;j++)/*这个实际上就是上面的直接插入排序*/
{
t=*(x+j);
for(k=j-h;(k>=0&&t<*(x+k));k-=h)
{
*(x+k+h)=*(x+k);
}
*(x+k+h)=t;
}
}
}
voidmain()
{
#defineMAX16
int*p,i,a[MAX];
/*录入测试数据*/
/*
p=a;
printf("Input%dnumberforsorting:\n",MAX);
for(i=0;i<MAX;i++)
{
scanf("%d",p++);
}
*可以自己输入数据
*/
a[]={503,17,512,908,170,897,275,653,462，154，509，612，677，765，703，94};
printf("\n");
//503,17,512,908,170,897,275,653,462，154，509，612，677，765，703，94
/*测试排序*/
p=a;
shell_sort(p,MAX);
/**/
for(p=a,i=0;i<MAX;i++)
{
printf("%d",*p++);
}
printf("\n");
system(