实验九排序算法实现程序.docx
《实验九排序算法实现程序.docx》由会员分享，可在线阅读，更多相关《实验九排序算法实现程序.docx（15页珍藏版）》请在冰点文库上搜索。
实验九排序算法实现程序
实验九数据结构中各种排序的操作
实验目的：
实现各种排序的操作
实验要求：
1、编写函数实现希尔排序操作；
2、编写函数实现非递归的快速排序操作；
3、编写函数实现递归的快速排序操作；
4、编写函数实现堆排序操作；
5、编写函数实现归并排序操作；
6、编写函数实现基数排序操作；
#include
#include
structnode
{
intkey;
}r[20];
structrnode
{
intkey;
intpoint;
};
main（）
{
voidprint（structnodea[20],intn）;
intcreat（）;
voidshell（structnodea[20],intn）;
inthoare（structnodea[20],intl,inth）;
voidquick1（structnodea[20],intn）;
voidquick2（structnodea[20],intl,inth）;
voidheap（structnodea[20],inti,intm）;
voidheapsort（structnodea[20],intn）;
voidmerges（structnodea[20],structnodea2[20],inth1,intmid,inth2）;
voidmergepass（structnodea[20],structnodea2[20],intl,intn）;
voidmergesort（structnodea[20],intn）;
intyx（intm,inti）;
intradixsort（structrnodea[20],intn）;
intnum,l,h,c;
structrnodes[20];
c=1;
while（c!
=0）
{
printf（"主菜单\n"）;
printf（"1输入关键字，以-9999表示结束。
\n"）;
printf（"2希尔排序\n"）;
printf（"3非递归的快速排序\n"）;
printf（"4递归的快速排序\n"）;
printf（"5堆排序\n"）;
printf（"6归并排序\n"）;
printf（"7基数排序\n"）;
printf（"输入选择（1--7,0表示结束）:
"）;
scanf（"%d",&c）;
switch（c）
{
case1:
num=creat（）;print（r,num）;break;
case2:
shell（r,num）;print（r,num）;break;
case3:
quick1（r,num）;print（r,num）;break;
case4:
l=0;h=num-1;quick2（r,l,h）;
printf（"outputquick2sortresult:
\n"）;
print（r,num）;break;
case5:
heapsort（r,num）;break;
case6:
mergesort（r,num）;print（r,num）;break;
case7:
radixsort（s,num）;
}
}
}//mainend
voidprint（structnodea[20],intn）
{
inti;
for（i=0;iprintf（"%5d",a[i].key）;
printf（"\n"）;
}//printend
intcreat（）
{
inti,n;
n=0;
printf（"inputkeys"）;
scanf（"%d",&i）;
while（i!
=-9999）
{
r[n].key=i;
n++;
scanf（"%d",&i）;
}
return（n）;
}//creatend
voidshell（structnodea[20],intn）//希尔排序
{
inti,j,k;
for（i=n;i>=1;i--）
a[i].key=a[i-1].key;
k=n/2;
while（k>=1）
{
for（i=k+1;i<=n;i++）
{
a[0].key=a[i].key;
j=i-k;
while（（a[j].key>a[0].key）&&（j>=0））
{
a[j+k].key=a[j].key;
j=j-k;
}
a[j+k]=a[0];
}
k=k/2;
}
for（i=0;ia[i].key=a[i+1].key;
printf（"输出希尔排序的结果:
\n"）;
}//shellend
////////////////////快速排序///////////////////////////
inthoare（structnodea[20],intl,inth）//分区处理函数
{
inti,j;
structnodex;
i=l;
j=h;
x.key=a[i].key;
do
{
while（（i=x.key））
j--;
if（i{
a[i].key=a[j].key;
i++;
}
while（（ii++;
if（i{
a[j].key=a[i].key;
j--;
}
}while（ia[i].key=x.key;
return（i）;
}//hoareend
voidquick1（structnodea[20],intn）
{
inti,l,h,tag,top;
ints[20][2];
l=0;h=n-1;tag=1;top=0;
do
{
while（l{
i=hoare（a,l,h）;
top++;
s[top][0]=i+1;
s[top][1]=h;
h=h-1;
}
if（top==0）
tag=0;
else
{
l=s[top][0];
h=s[top][1];
top--;
}
}while（tag==1）;
printf（"输出非递归快速排序结果:
\n"）;
}//quickend
voidquick2（structnodea[20],intl,inth）//递归的快速排序
{
inti;
if（l{
i=hoare（a,l,h）;
quick2（a,l,i-1）;
quick2（a,i+1,h）;
}
}//quick2end
////////////////////快速排序结束////////////////////////
////////////////////堆排序函数//////////////////////////
voidheap（structnodea[20],inti,intm）//调整堆的函数
{
structnodex;
intj;
x.key=a[i].key;
j=2*i;
while（j<=m）
{
if（jif（a[j].key>a[j+1].key）
j++;
if（a[j].key{
a[i].key=a[j].key;
i=j;
j=2*i;
}
else
j=m+1;
}
a[i].key=x.key;
}//heapend
voidheapsort（structnodea[20],intn）//堆排序的主体函数
{
inti,v;
structnodex;
for（i=n;i>0;i--）
a[i].key=a[i-1].key;
for（i=n/2;i>=1;i--）
heap（a,i,n）;
printf（"输出堆排序结果:
\n"）;
for（v=n;v>=2;v--）
{
printf（"%5d",a[1].key）;
x.key=a[1].key;
a[1].key=a[v].key;
a[v].key=x.key;
heap（a,1,v-1）;
}
printf（"%5d",a[1].key）;
for（i=0;ia[i].key=a[i+1].key;
}//heapsortend
/////////////////堆排序函数结束///////////////////
//////////////////归并函数////////////////////////
voidmerges（structnodea[20],structnodea2[20],inth1,intmid,inth2）
//归并排序的核心算法
{
inti,j,k;
i=h1;j=mid+1;k=h1-1;
while（（i<=mid）&&（j<=h2））
{
k=k+1;
if（a[i].key<=a[j].key）
{
a2[k].key=a[i].key;
i++;
}
else
{
a2[k].key=a[j].key;
j++;
}
}
while（i<=mid）
{
k++;
a2[k].key=a[i].key;
i++;
}
while（j<=h2）
{
k++;
a2[k].key=a[j].key;
i++;
}
}//mergesend
voidmergepass（structnodea[20],structnodea2[20],intl,intn）
//一趟归并
{
intj,i,h1,mid,h2;
i=0;
while（（n-i）>=2*l）
{
h1=i;
mid=h1+l-1;
h2=i+2*l-1;
merges（a,a2,h1,mid,h2）;
i=i+2*l;
}
if（（n-i）<=l）
for（j=i;j<=n;j++）
a2[j].key=a[j].key;
else
{
h1=i;
mid=h1+l-1;
h2=n-1;
merges（a,a2,h1,mid,h2）;
}
}//mergepassend
voidmergesort（structnodea[20],intn）
{
intl;
structnodea2[20];
l=1;
while（l{
mergepass（a,a2,l,n）;
l=2*l;
mergepass（a2,a,l,n）;
l=2*l;
}
printf（"输出归并排序的结果:
\n"）;
}//mergesortend
///////////////归并函数结束///////////////
///////////////基数排序///////////////////
intyx（intm,inti）//分离关键字倒数第i位有效数字的算法
{
intx;
switch（i）
{
case1:
x=m%10;break;
case2:
x=（m%100）/10;break;
case3:
x=（m%1000）/100;break;
case4:
x=（m%10000）/1000;break;
}
return（x）;
}//yxend
intradixsort（structrnodea[20],intn）
{
intf[11],e[11],i,j,k,l,p,d,t;
for（i=1;i<=n;i++）
{
a[i].key=r[i-1].key;
a[i].point=i+1;
}
a[n].point=0;
p=1;
printf（"输出关键字有效位数d\n"）;
scanf（"%d",&d）;
printf（"输出基数排序的结果:
\n"）;
for（i=1;i<=d;i++）
{
for（j=0;j<=10;j++）
{
f[j]=0;
e[j]=0;
}
while（p!
=0）
{
k=yx（a[p].key,i）;
if（f[k]==0）
{
f[k]=p;
e[k]=p;
}
else
{
l=e[k];
a[l].point=p;
e[k]=p;
}
p=a[p].point;
}
j=0;
while（f[j]==0）
j++;
p=f[j];t=e[j];
while（j<10）
{
j++;
while（（j<10）&&（f[j]==0））
j++;
if（f[j]!
=0）
{
a[t].point=f[j];
t=e[j];
}
}
a[t].point=0;
t=p;
while（t!
=0）
{
printf（"%5d",a[t].key）;
t=a[t].point;
}
printf（"\n"）;
}
return（p）;
}
程序运行：
升级会员 