实验十二排序技术实验报告.docx
《实验十二排序技术实验报告.docx》由会员分享，可在线阅读，更多相关《实验十二排序技术实验报告.docx（16页珍藏版）》请在冰点文库上搜索。
实验十二排序技术实验报告
实验十二排序技术实验
一、实验目的
1掌握各种排序算法的基本思想；
⑵掌握各种排序算法的实现方法；
⑶掌握各种排序算法的时间性能及其花费时间的计算。
⑷掌握各种排序算法所适应的不同场合。
二、实验内容
1、随机函数产生10000个随机数，用直接插入、希尔、冒泡、直接选择等排序方法排序，并统计每一种排序所花费的时间。
2、随机函数产生30000个随机数，用快速、堆、归并等排序方法排序，并统计每一种排序所花费的时间。
三、设计与编码
#include
#include
#include
usingnamespacestd;
voidShuChu（intr[],intn）
{
cout<<"输出：
";
for（inti=0;icout<cout<cout<<"*****************************************"<}
voidInsertSort（intr[],intn）//插入排序
{
inta=r[0];
for（inti=2;i{
r[0]=r[i];
for（intj=i-1;r[0]r[j+1]=r[j];
r[j+1]=r[0];
}
r[0]=a;
}
voidShellSort（intr[],intn）//希尔排序
{
inta=r[0];
for（intd=n/2;d>=1;d=d/2）
{
for（inti=d+1;i<=n-1;i++）
{
r[0]=r[i];
for（intj=i-d;j>0&&r[0]r[j+d]=r[j];
r[j+d]=r[0];
}
}
r[0]=a;
}
voidBubbleSort（intr[],intn）//冒泡排序
{
intexchange=n-1;
while（exchange!
=0）
{
intbound=exchange;exchange=0;
for（intj=1;jif（r[j]>r[j+1]）
{
ints=r[j+1];
r[j+1]=r[j];
r[j]=s;
exchange=j;
}
}
}
voidSelectSort（intr[],intn）//选择排序
{
for（inti=0;i{
intindex=i;
for（intj=i+1;j<=n-1;j++）
if（r[j]index=j;
if（index!
=i）
{
inta=r[index];
r[index]=r[i];
r[i]=a;
}
}
ShuChu（r,n）;
}
intPartition（intr[],intfirst,intend）//快速排序一次划分算法
{
inti=first;
intj=end;
r[0]=r[i];
intp=r[i];
while（i{
while（iif（i{
inta=r[j];
r[j]=r[i];
r[i]=a;
i++;
}
while（iif（i{
intb=r[j];
r[j]=r[i];
r[i]=b;
j--;
}
}
returni;
}
voidQuickSort（intr[],intfirst,intend）//快速排序算法
{
inta=r[0];
if（first{
intpivot=Partition（r,first,end）;
QuickSort（r,first,pivot-1）;
QuickSort（r,pivot+1,end）;
}
r[0]=a;
}
voidSift（intr[],intk,intm）//筛选法调整堆的算法
{
inti=k;
intj=2*i;
while（j<=m）
{
if（jif（r[i]>=r[j]）break;
else
{
inta=r[j];
r[j]=r[i];
r[i]=a;
i=j;
j=2*i;
}
}
}
voidHeapSort（intr[],intn）//堆排序算法
{
for（inti=n/2;i>=1;i--）
Sift（r,i,n-1）;
for（i=2;i{
inta=r[n-i+1];
r[n-i+1]=r[1];
r[1]=a;
Sift（r,1,i-1）;
}
}
voidMerge（intr[],intr1[],ints,intm,intt）//一次归并算法
{
inti=s;
intj=m+1;
intk=s;
while（i<=m&&j<=t）
{
if（r[i]<=r[j]）r1[k++]=r[i++];
elser1[k++]=r[j++];
}
if（i<=m）while（i<=m）
r1[k++]=r[i++];
elsewhile（j<=t）
r1[k++]=r[j++];
}
voidMergePass（intr[],intr1[],intn,inth）
{
inti=1;
inta=n-2*h+1;
while（i<=a）
{
Merge（r,r1,i,i+h-1,i+2*h-1）;
i+=2*h;
}
if（ielsefor（intk=i;k<=n;k++）
r1[k]=r[k];
}
voidMergeSort（intr[],intr1[],intn）//归并排序非递归算法
{
inth=1;
while（h{
MergePass（r,r1,n,h）;
h=2*h;
MergePass（r1,r,n,h）;
h=2*h;
}
}
voidmenu（）
{
cout<<"排序技术实验"<cout<<"*********************"<cout<<"1.直接插入排序"<cout<<"2.希尔排序"<cout<<"3.冒泡排序"<cout<<"4.直接选择排序"<cout<<"5.快速排序"<cout<<"6.堆排序"<cout<<"7.归并排序"<cout<<"8.退出"<}
intmain（）
{
clock_tstart,end;
menu（）;
intflag=1;
while（flag）
{
inti;
cout<<"*****************************************"<cout<<"请输入你所需要的选项：
";
cin>>i;
switch（i）
{
case1:
{
intsrand（30001）;
inta[30001];intn;
cout<<"请输入随机产生的随机数的个数:
";
cin>>n;
a[0]=0;
for（inti=1;ia[i]=rand（）;
ShuChu（a,n）;
cout<<"直接插入排序结果：
"<start=clock（）;
InsertSort（a,n）;
end=clock（）;
ShuChu（a,n）;
doublecount=（double）（end-start）/1000;
cout<<"排序所用时间为:
"<break;
}
case2:
{
intsrand（30001）;
inta[30001];intn;
cout<<"请输入随机产生的随机数的个数:
";
cin>>n;
a[0]=0;
for（inti=1;ia[i]=rand（）;
ShuChu（a,n）;
cout<<"希尔排序结果：
"<start=clock（）;
ShellSort（a,n）;
end=clock（）;
ShuChu（a,n）;
doublecount=（double）（end-start）/1000;
cout<<"排序所用时间为:
"<break;}
case3:
{intsrand（30001）;
inta[30001];intn;
cout<<"请输入随机产生的随机数的个数:
";
cin>>n;
a[0]=0;
for（inti=1;ia[i]=rand（）;
ShuChu（a,n）;
cout<<"冒泡排序结果：
"<start=clock（）;
BubbleSort（a,n）;
end=clock（）;
ShuChu（a,n）;
doublecount=（double）（end-start）/1000;
cout<<"排序所用时间为:
"<break;}
case4:
{intsrand（30001）;
inta[30001];intn;
cout<<"请输入随机产生的随机数的个数:
"<cin>>n;
a[0]=0;
for（inti=1;ia[i]=rand（）;
ShuChu（a,n）;
cout<<"直接选择排序结果：
"<start=clock（）;
SelectSort（a,n）;
end=clock（）;
ShuChu（a,n）;
doublecount=（double）（end-start）/1000;
cout<<"排序所用时间为:
"<break;}
case5:
{intsrand（30001）;
inta[30001];intn;
cout<<"请输入随机产生的随机数的个数:
";
cin>>n;
a[0]=0;
for（inti=1;ia[i]=rand（）;
ShuChu（a,n）;
cout<<"快速排序结果：
"<start=clock（）;
QuickSort（a,1,n-1）;
end=clock（）;
ShuChu（a,n）;
doublecount=（double）（end-start）/1000;
cout<<"排序所用时间为:
"<break;
}
case6:
{intsrand（30001）;
inta[30001];intn;
cout<<"请输入随机产生的随机数的个数:
";
cin>>n;
a[0]=0;
for（inti=1;ia[i]=rand（）;
ShuChu（a,n）;
cout<<"堆排序结果：
"<start=clock（）;
HeapSort（a,n）;
end=clock（）;
ShuChu（a,n）;
doublecount=（double）（end-start）/1000;
cout<<"排序所用时间为:
"<break;}
case7:
{intsrand（30001）;
inta[30001];intn;
inta1[30001];
cout<<"请输入随机产生的随机数的个数:
";
cin>>n;
a[0]=0;
for（inti=1;ia[i]=rand（）;
ShuChu（a,n）;
cout<<"归并排序结果：
"<start=clock（）;
MergeSort（a,a1,n-1）;
end=clock（）;
ShuChu（a,n）;
doublecount=（double）（end-start）/1000;
cout<<"排序所用时间为:
"<break;}
case8:
{flag=0;
break;}
default:
{cout<<"错误!
!
!
"<break;}}}
return0;}
四、运行与调试
a）在调试程序的过程中遇到什么问题，是如何解决的？
答：
数据的下标经常出错，数组的第一个数应是a[0].
b）设计了哪些设计数据？
测试结果是什么？
答：
程序设计了对随机函数产生10000个随机数进行直接插入、希尔、冒泡、直接选择等排序方法排序，并统计每一种排序所花费的时间；对随机函数产生30000个随机数进行快速、堆、归并等排序方法排序，并统计每一种排序所花费的时间。
结果实现各种排序方法的排序，并统计了排序所需时间。
c）程序运行的结果如何？
因排序结果太长，故只设计显示排序时间
五、实验小结
本实验通过不同的算法实现相同的排序，不同的排序算法时间性能亦不同，只要了解算法间的原理，程序就比较简单了，稍微要注意的是数组的下标问题，总的来说，本实验让我对个算法的理解更加深刻，也对数据结构的学习更深入，但还不够熟悉，需多多练习。
升级会员 