排序报告.docx
《排序报告.docx》由会员分享，可在线阅读，更多相关《排序报告.docx（15页珍藏版）》请在冰点文库上搜索。
排序报告
长安大学
算法与数据结构课程设计
内部排序以及应用
专业
班级
姓名
指导教师
日期
目录
摘要.........................................................................................................................1
关键字.....................................................................................................................1
内容要求................................................................................................................1
流程图.....................................................................................................................1
程序源代码............................................................................................................2
编译及调试...........................................................................................................7
收获与心得..........................................................................................................8
参考文献.................................................................................................................8
评语...........................................................................................................................9
摘要
排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素或者记录的任意序列，重新排列成一个按关键字有序的序列。
这里采用的是内部排序，将散乱的数组排列在内存中进行排列。
关键字：
冒泡，二分，希尔，堆，内部排序
内容要求：
1.从键盘上输入10个随机整形数字，然后利用各种排序方法对其进行排序
2.让计算机自动产生50000个随机整形数字，再利用所定义的各种排序方法对其进行排序，然后计算出各种排序所用的时间长度，以供临时参考。
流程图：
源程序：
#include
#include
#include
#include
constintN=50000;
#defineElemTypeint
voidBubble（ElemTypeR[],intn）{//冒泡
intflag=1;//当其为0时，停止排序
for（inti=1;iflag=0;//开始元素未进行交换
for（intj=n-1;j>=i;j--）
if（R[j]ElemTypet=R[j];
R[j]=R[j-1];
R[j-1]=t;flag=1;}//交换,标记发生了交换
if（flag==0）return;}}
voidselect（ElemTypeR[],intn）{//直接选择
inti,j,m;
ElemTypet;
for（i=0;im=i;
for（j=i+1;jif（R[j]if（m!
=i）{
t=R[i];
R[i]=R[m];
R[m]=t;}}}
voidinsert（ElemTypeR[],intn）{//直接插入
for（inti=1;iElemTypetemp=R[i];//i是插入次数,共进行n-1次插入,这里把待排序元素赋给temp
intj=i-1;
while（（j>=0）&&（tempR[j+1]=R[j];//顺序比较和移动
j--;}
R[j+1]=temp;}}
voidbinary（ElemTypeR[],intn）{//二分
for（inti=1;iintleft=0,right=i-1;
ElemTypetemp=R[i];
while（left<=right）{
intmiddle=（left+right）/2;//取中点的值
if（tempright=middle-1;//左区间
else
left=middle+1;//右区间
}
for（intj=i-1;j>=left;j--）{
R[j+1]=R[j];}//后面的元素向前移动
R[left]=temp;}}
voidshell（ElemTypeR[],intn）{//希尔
for（intd=n/2;d>=1;d/=2）{//d是增量的大小,增量每次整除2,第一次是n/2
for（inti=d;iElemTypetemp=R[i];//待插入对象先放入temp
for（intj=i-d;j>=0;j-=d）{//在组内向前顺序进行比较和移动
if（tempR[j+d]=R[j];
else
break;}//查找到合适位置就退出j循环
R[j+d]=temp;}}}
voidquick（ElemTypeR[],intleft,intright）{//快速
inti=left,j=right;
ElemTypetemp=R[i];
while（iwhile（（R[j]>temp）&&（j>1））
j=j-1;
if（j>i）{
R[i]=R[j];
i=i+1;}
while（（R[i]<=temp）&&（j>i））
i=i+1;
if（iR[j]=R[i];
j=j-1;}}//一次划分得到基准值的正确位置
R[i]=temp;
if（leftif（i+1voidcreatheap（ElemTypeR[],inti,intn）{//建立大根堆
intj;ElemTypet;
t=R[i];j=2*i;
while（jif（（jj++;}
if（tR[i]=R[j];
i=j;
j=2*i;
}else{
j=n;}
R[i]=t;}}
voidheap（ElemTypeR[],intn）{//堆排序
ElemTypet;
for（inti=n/2;i>=0;i--）{
creatheap（R,i,n）;}
for（i=n-1;i>=0;i--）{
t=R[0];
R[0]=R[i];
R[i]=t;
creatheap（R,0,i-1）;}}
voidout（ElemTypeR[],intn,charprint）{//输出函数
if（print=='y'）{
for（inti=0;i<=n-1;i++）{
if（i%10==0）
{cout<cout<cout<voidRsort（）{//随机数排序用时输出
charch,print;
cout<<"产生"<cin>>print;
ElemTypeR[N],T[N];
time_tt1,t2;
doublett1,tt2,tt3,tt4,tt5,tt6,tt7;
srand（0）;
for（inti=0;i<=N-1;i++）{
T[i]=rand（）;}//产生随机数
out（T,N,print）;
cout<<"直接插入排序（y/n）?
";
cin>>ch;
if（ch=='y'）{
for（i=0;iR[i]=T[i];}
t1=time（NULL）;//记录开始排序的时间
insert（R,N）;
t2=time（NULL）;//排序完成的时间
tt1=difftime（t2,t1）;//时间差值
out（R,N,print）;}
srand（0）;
for（i=0;i<=N-1;i++）{
T[i]=rand（）;}//产生随机数
out（T,N,print）;
cout<<"二分插入排序（y/n）?
";
cin>>ch;
if（ch=='y'）{
for（i=0;iR[i]=T[i];}
t1=time（NULL）;
binary（R,N）;
t2=time（NULL）;
tt2=difftime（t2,t1）;
out（R,N,print）;}
srand（0）;
for（i=0;i<=N-1;i++）{
T[i]=rand（）;}
out（T,N,print）;
cout<<"希尔插入排序（y/n）?
";
cin>>ch;
if（ch=='y'）{
for（i=0;iR[i]=T[i];}
t1=time（NULL）;
shell（R,N）;
t2=time（NULL）;
tt3=difftime（t2,t1）;
out（R,N,print）;}
srand（0）;
for（i=0;i<=N-1;i++）{
T[i]=rand（）;}
out（T,N,print）;
cout<<"冒泡插入排序（y/n）?
";
cin>>ch;
if（ch=='y'）{
for（i=0;iR[i]=T[i];}
t1=time（NULL）;
Bubble（R,N）;
t2=time（NULL）;
tt4=difftime（t2,t1）;
out（R,N,print）;}
srand（0）;
for（i=0;i<=N-1;i++）{
T[i]=rand（）;}
out（T,N,print）;
cout<<"选择插入排序（y/n）?
";
cin>>ch;
if（ch=='y'）{
for（i=0;iR[i]=T[i];}
t1=time（NULL）;
select（R,N）;
t2=time（NULL）;
tt5=difftime（t2,t1）;
out（R,N,print）;}
srand（0）;
for（i=0;i<=N-1;i++）{
T[i]=rand（）;}
out（T,N,print）;
cout<<"快速排序（y/n）?
";
cin>>ch;
if（ch=='y'）{
for（i=0;iR[i]=T[i];}
t1=time（NULL）;
quick（R,0,N-1）;
t2=time（NULL）;
tt6=difftime（t2,t1）;
out（R,N,print）;}
srand（0）;
for（i=0;i<=N-1;i++）{
T[i]=rand（）;}
out（T,N,print）;
cout<<"堆排序（y/n）?
";
cin>>ch;
if（ch=='y'）{
for（i=0;iR[i]=T[i];}
t1=time（NULL）;
heap（R,N）;
t2=time（NULL）;
tt7=difftime（t2,t1）;
out（R,N,print）;}//用时输出：
cout<<"直接插入排序的时间：
"<cout<<"二分插入排序的时间：
"<cout<<"希尔排序的时间：
"<cout<<"冒泡插入排序的时间：
"<cout<<"选择插入排序的时间：
"<cout<<"快速排序的时间：
"<cout<<"堆排序的时间：
"<voidmain（）{
intch;charprint='y';intch2;
ElemTypeT[10];
cout<<"请选择队列种类：
\n1.用户自定义输入2.随机产生序列并且计算排序用时\n";
cin>>ch;
if（ch==1）{
restart:
cout<<"请先输入10组数据：
\n";
for（inti=0;i<=9;i++）{
cin>>T[i];}
goon:
cout<<"你所输入的序列是\n";out（T,10,print）;
cout<<"请选择所用的排序方法\n1.直接插入排序\n2.二分发插入排序\n3.希尔排序\n4.冒泡插入排序\n5.选择插入排序\n6.快速排序\n7.堆排序\n选择?
:
";
cin>>ch2;
switch（ch2）{
case1:
select（T,10）;out（T,10,print）;break;
case2:
binary（T,10）;out（T,10,print）;break;
case3:
shell（T,10）;out（T,10,print）;break;
case4:
Bubble（T,10）;out（T,10,print）;break;
case5:
insert（T,10）;out（T,10,print）;break;
case6:
quick（T,0,9）;out（T,10,print）;break;
case7:
heap（T,10）;out（T,10,print）;break;
default:
cout<<"输入无效";}
cout<<"\n排序完成,1.继续排序2.重新输入数组其他.退出\n选择?
:
";
cin>>ch;
switch（ch）{
case1:
gotogoon;
case2:
gotorestart;
default:
cout<cout<<"以上是各种排序所用时间\n排序完成,1.输入排序其他.退出\n选择?
:
";
cin>>ch;
switch（ch）{
case1:
gotorestart;
default:
cout<编译及其调试：
1.输入数组，选择方法进行排序：
*排序将按照从小到大依次排列，不显示排序的过程
2.让计算机自动生成50000个随机数字进行排序，然后输出结果
这里为了显示方便，加入了一个输出的参数控制是否显示
下面的是不显示。
*随机函数使用rand（）函数进行数据预设
*这里利用time（）函数计时和difftime（）函数进行秒级别的时差计算
收获与心得：
从本次设计来说，让我更加了解了各种内部排序的方法与程序的写法，排序的思想以及时间和储存上的优势与劣势，锻炼了我编写程序的能力以及查阅各种有用资料的能力。
参考文献：
1.数据结构c++版习题解答与实习指导，李根强主编，中国水利水电出版社
2.数据结构c语言版，严蔚敏主编，清华大学出版社
3.c++程序设计语言，主编揣锦华，西安电子科技大学出版社
评语
评阅人：
日期：
升级会员 