ID488257875

somehow:

  Shell排序法又称为缩小增量排序法，也属于插入排序类的算法，是对直接插入排序的一种改进。

  其基本思想就是：将需要排序的序列划分为若干个较小的序列，对这些序列进行直接插入排序，通过这样的操作可使需要排序的数据基本有序，最后再使用一次直接插入排序。这样，首先对数量较小的序列进行直接插入排序可提高效率，最后对基本有序的序列进行直接插入排序，也可提高效率，从而使整个排序过程的效率的到提升。

  Shell排序C语言实现：

#include <stdio.h>

void ShellSort(int a[],int n)

{

int i,j,d,x,k;

for(d=n/2;d>0;d/=2)//d是增量，设置它每次缩小一半

{

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

{

x=a[i];

for(j=i-d;(j>=0&&a[j]>x);j=j-d)

a[j+d]=a[j];

a[j+d]=x;

}

}

}

int main(void)

{

int i,a[]={69,65,90,37,92,6,28,54};

printf("Before Sort:");

for(i=0;i<8;i++)

printf("%d ",a[i]);

printf("\n");

ShellSort(a,8);

printf("After Sort:");

for(i=0;i<8;i++)

printf("%d ",a[i]);

printf("\n");

return 0;

}

  咳咳，循环是有点烦，那么它是如何实现的呢？

  先看一张图。

 

  Shell排序法既然称为缩小增量排序法，所以它进行插入排序是以不同增量进行的，也就是说它每隔d个数据进行插入排序。说起来容易，但是看看代码又晕了。那么它具体是怎么比较的呢？

  当增量为4时，依次对{a[0],a[4]}，{a[1],a[5]}，{a[2],a[6]}，{a[3],a[7]}进行插入排序；

  当增量为2时，依次对{a[0],a[2],a[4],a[6]},{a[1],a[3],a[5],a[7]}进行插入排序；

  当增量为1时，对{a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7]}进行插入排序（每一个大括号代表进行插入排序的对象集合）。

  值得说明的是，进行插入排序时，例如在增量为2时，进行插入排序在上面两个集合中是交替进行的。看图：

   需要说明的是上图第一步是经过了增量为5的排序后的数据。

  事实上，我们可以通过更简单的方法来跟踪每次增量排序后的数据，只需在原代码中加入几行。

#include <stdio.h>

void ShellSort(int a[],int n)

{

int i,j,d,x,k;

for(d=n/2;d>0;d/=2)

{

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

{

x=a[i];

for(j=i-d;(j>=0&&a[j]>x);j=j-d)

a[j+d]=a[j];

a[j+d]=x;

}

//加入的代码，方便查看每一次增量排序后的数据

printf("增量为%d:",d);

for(k=0;k<n;k++)

printf("%d ",a[k]);

printf("\n");

}

}

int main(void)

{

int i,a[]={69,65,90,37,92,6,28,54};

printf("Before Sort:");

for(i=0;i<8;i++)

printf("%d ",a[i]);

printf("\n");

ShellSort(a,8);

printf("After Sort:");

for(i=0;i<8;i++)

printf("%d ",a[i]);

printf("\n");

return 0;

}

  效果：