一、插入排序
插入排序由N-1趟排序组成。对如P=1趟到P=N-1趟，插入排序保证从位置0到位置P上的元素以排序。
void insertionsort(int a[],int N)
{
int j,p,tem;
for(p=1;p<=N-1;p++)
{
tem=a[p];
for(j=p;j>0&&a[j-1]>tem;j--)
{
a[j]=a[j-1];
}
a[j]=tem;
}
}
时间复杂度位（N^2）
二、希尔排序
希尔排序使用一个序列h1,h2,h3,.......h(t),叫做增量序列。只要h1=1，任何增量序列都是可行的，不过，有些增量序列比另外一些更好。使用增量h（k）的一趟排序后，对于每一个i我们有a[i]<=a[i+h(k)].
增量序列一种流行（但是不好）的选着是shell建议的序列：h(t)=[N/2]和h(k)=[h(k+1)/2]。
void shellsort(int a[],int N)
{
int i,j,tmp,Insrement;
for(Insrement=N/2;Insrement>0;Insrement/=2)
{
for(i=Insrement;i
{ tmp=a[i];
for(j=i;j>=Insrement;j-=Insrement)
{
if(a[j-Insrement]>tmp)
a[j]=a[j-Insrement];
else
break;
}
a[j]=tmp;
}
}
}
阅读(215) | 评论(0) | 转发(0) |
