排序报告.docx
- 文档编号:13699747
- 上传时间:2023-06-16
- 格式:DOCX
- 页数:15
- 大小:110.73KB
排序报告.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;i flag=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;i m=i; for(j=i+1;j if(R[j] if(m! =i){ t=R[i]; R[i]=R[m]; R[m]=t;}}} voidinsert(ElemTypeR[],intn){//直接插入 for(inti=1;i ElemTypetemp=R[i];//i是插入次数,共进行n-1次插入,这里把待排序元素赋给temp intj=i-1; while((j>=0)&&(temp R[j+1]=R[j];//顺序比较和移动 j--;} R[j+1]=temp;}} voidbinary(ElemTypeR[],intn){//二分 for(inti=1;i intleft=0,right=i-1; ElemTypetemp=R[i]; while(left<=right){ intmiddle=(left+right)/2;//取中点的值 if(temp right=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;i ElemTypetemp=R[i];//待插入对象先放入temp for(intj=i-d;j>=0;j-=d){//在组内向前顺序进行比较和移动 if(temp R[j+d]=R[j]; else break;}//查找到合适位置就退出j循环 R[j+d]=temp;}}} voidquick(ElemTypeR[],intleft,intright){//快速 inti=left,j=right; ElemTypetemp=R[i]; while(i while((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(i R[j]=R[i]; j=j-1;}}//一次划分得到基准值的正确位置 R[i]=temp; if(left if(i+1 voidcreatheap(ElemTypeR[],inti,intn){//建立大根堆 intj;ElemTypet; t=R[i];j=2*i; while(j if((j j++;} if(t R[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;i R[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;i R[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;i R[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;i R[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;i R[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;i R[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;i R[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++程序设计语言,主编揣锦华,西安电子科技大学出版社 评语 评阅人: 日期:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 排序 报告
![提示](https://static.bingdoc.com/images/bang_tan.gif)