直接插入排序_折半插入_2路插入_希尔排序.doc
文本预览下载声明
#include stdio.h
#include stdlib.h
#include iostream.h
void isort(int a[],int len)
{
int i,j,insert;
int index;
for(i=1;ilen;i++)
{
index=i-1;
insert=a[i];
while(index=0inserta[index])
{
a[index+1]=a[index];
index--;
}
a[index+1]=insert;
}
}
void halfinsert(int a[],int len)
{
int i,j;
int low=0,high=0,mid;
int insert;
for(i=1;ilen;i++)
{
low=0;high=i-1;
int insert;
insert=a[i];
while(low=high)
{
mid=(low+high)/2;
if(insert=a[mid])
low=mid+1;
else
high=mid-1;
}
for(j=i-1;j=high+1;j--)
{
a[j+1]=a[j];
}
a[high+1]=insert;
}
}
void twoinsert(int a[],int b[],int len)
{
int i;
int j;
int first,final;
first=final=0;//first、final分别指示d中排好序的记录的第1个和最后1个记录的位置。
b[first]=a[0];
for(i=1;ilen;i++)
{
if(a[i]b[first])//待插入记录小于d中最小值，插入到d[first]之前（不需移动d数组的元素
{
first=(first-1+len)%len;
b[first]=a[i];
}
else if(a[i]=b[final])//待插入记录大于d中最小值，插入到d[final]之后（不需移动d数组的元素）。
{
final=final+1;
b[final]=a[i];
}
else //待插入记录大于d中最小值，小于d中最大值，插入到d的中间（需要移动d数组的元素
{
j=final;
final++;
while(a[i]b[j])
{
b[(j+1+len)%len]=b[j];
j=(j-1+len)%len;
}
b[j+1]=a[i];
}
}
for ( i = 0; i len; ++i )
{
a[i]=b[(i+first)%len];
}
}
void shellsort(int a[],int n)
{
int d;
int i,j,temp;
d=n/2;
int len;
len=n;
while(d=1)
{
for(i=d;ilen;i++)
{
temp=a[i];
j=i-d;
while(j=0a[j]temp)
{
a[j+d]=a[j];
j=j-d;
}
a[j+d]=temp;
}
d=d/2;
}
}
void display(int a[],int len)
{
int i;
for(i=0;ilen;i++)
couta[i] ;
coutendl;
}
int main()
{
int i;
int choice;
int a[8]={3,2,5,4,1,7,9,6};
int len=sizeof(a)/sizeof(int);
int b[10];
printf(please input the choice(0,1,2,3):\n);
scanf(%d,choice);
switch(choice)
{
case 0:
printf(插入排序:\n);
isort(a,len);
display(a,len);
break;
case 1:
printf(折半插入:\n);
halfinsert(a,len);
display(a,len);
break;
case 2:
printf(2_路插入:\n);
twoinsert(a,b,len);
display(a,len);
break;
case
显示全部