排序之Shell排序法
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时，进行插入排序在上面两个集合中是交替进行的。看图：
事实上，我们可以通过更简单的方法来跟踪每次增量排序后的数据，只需在原代码中加入几行。
#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;
}
效果：
评论