希尔排序
希尔排序是对插入排序的改进，对中等规模的数据排序效率较高！交换的次数变得少了，效率就高了。
希尔排序的算法:(1)相距为k的数据进行比较，若不符合排序的条件，就进行交换。
（2）第一次比较时k为数组长度的一半，以后依次减半，直至k为零，比较结束。
下面是希尔排序实现的c代码和c++代码。
c代码：
#include<stdio.h>
void shell(int a[],int n)
{
int k,x,i,j;
k=n/2;
while(k>=1)
{
for(i=k;i<n;i++)
{
x=a[i];
j=i-k;
while(j>=0&&x<a[j])
{
a[j+k]=a[j];
j=j-k;
}
a[j+k]=x;
}
k=k/2;
}
}
int main()
{
int a[10],i;
printf("请输入10个数\n");
for(i=0;i<10;i++)
scanf("%d",&a[i]);
printf("未排好的数为：\n");
for(i=0;i<10;i++)
printf("%d\t",a[i]);
shell(a,10);
printf("已排好的数为：\n");
for(i=0;i<10;i++)
printf("%d\t",a[i]);
getch();
return 0;
}
C++代码：
#include<iostream>
void shell(int a[],int n)
{
int k,x,i,j;
k=n/2;
while(k>=1)
{
for(i=k;i<n;i++)
{
x=a[i];
j=i-k;
while(j>=0&&x<a[j])
{
a[j+k]=a[j];
j=j-k;
}
a[j+k]=x;
}
k=k/2;
}
}
int main()
{
int a[10],i;
cout<<"请输入10个数\n";
for(i=0;i<10;i++)
cin>>a[i];
cout<<"未排好的数为：\n";
for(i=0;i<10;i++)
cout<<a[i]<<" ";
cout<<endl;
shell(a,10);
cout<<"已排好的数为：\n";
for(i=0;i<10;i++)
cout<<a[i]<<" ";
;
return 0;
}
希尔排序非常容易实现，算法代码短而简单。希尔排序时插入排序的一种改进，减少了其复制的次数，速度要快很多。原因是，当N值很大时数据项每一趟排序需要的个数很少，但数据项的距离很长。当N值减小时每一趟需要和动的数据增多，此时已经接近于它们排序后的最终位置。正是这两种情况的结合才使希尔排序效率比插入排序高很多。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
