数据结构--内部排序的比较
更新时间:2023-12-31 22:49:01 阅读量: 教育文库 文档下载
存储管理、查找和排序
班级: 姓名: 学号: 完成日期:
题目:内部排序算法比较
问题描述:通过随机数据比较各算法的关键字比较次数与移动次
数。
一、需求分析:
内部排序方法有:插入排序,快速排序,简单选择排序,堆排序,归并排序,基数排序。
二、概要设计
本实验中用到的函数:
1.起泡排序函数
void gensort(int b[],int n) 2.插入排序函数
void insertsort(sqlist b,int n) 3.希尔排序
void shellsort(sqlist b,int n) 4.选择排序
void gentsort(int b[],int n) 5.快速排序
void quicksort(sqlist r,int s,int t) 6.堆排序
void sift(sqlist r,int s,int m)
三、详细设计
#include
#define N 66 //头文件和宏定义 int p,q; //全局变量
//-----------------------起泡排序 void gensort(int b[],int n) {
int i,j;int s=0,t=0; for(i=0;i for(j=i+1;j if(b[i]>b[j]) { int temp=b[i]; b[i]=b[j]; b[j]=temp; s+=3; }}} cout<<\移动次数=\比较次数=\} //-------------------------------插入排序 typedef int KeyType; struct rec { KeyType key; }; typedef rec sqlist[N]; void insertsort(sqlist b,int n) { int i,j;int s=0,t=0; for(i=2;i b[0]=b[i]; s++; j=i-1; t++; while(b[0].key b[j+1]=b[j]; j--; s++; t++; } b[j+1]=b[0]; s++; } cout<<\移动次数=\比较次数=\} //------------------------------------希尔排序 void shellsort(sqlist b,int n) { int i,j,gap; rec x; int s=0,t=0; gap=n/2; while(gap>0) { for(i=gap+1;i j=i-gap; while(j>0) { t++; if(b[j].key>b[j+gap].key) { x=b[j];b[j]=b[j+gap]; b[j+gap]=x;j=j-gap; s+=3; } else j=0; gap=gap/2; }} cout<<\移动次数=\比较次数=\}} //---------------------------------------选择排序 void gentsort(int b[],int n) { int i,j,k; int s=0,t=0; for(i=0;i for(j=i+1;j if(b[k]>b[j]) {k=j;} } if(k!=i) {int temp=b[k]; b[k]=b[i]; b[i]=temp; s+=3; }} cout<<\移动次数=\比较次数=\} //--------------------------------快速排序 void output(sqlist b,int n)//输出元素值 { for(int i=0;i cout< void display(int n,int m)//输出计数 { cout<<\移动次数=\比较次数=\} void BeforeSort()//初始化计数器 { p=0;q=0; } void quicksort(sqlist r,int s,int t) { int i=s,j=t; if(s { r[0]=r[s];p++; while(i while(i while(i r[j]=r[i];q++;p++; } r[i]=r[0];p++; } else return; quicksort(r,s,j-1); quicksort(r,j+1,t); } void sort(sqlist r,int s,int t) { BeforeSort(); quicksort(r,s,t); display(p,q); } //---------------------------------堆排序 void sift(sqlist r,int s,int m) { int j; rec x; x=r[s]; for(j=2*s;j<=m;j*=2) {q++; if(j if(!(x.key void heapsort(sqlist &r,int m) { int i;rec w; for(i=m/2;i>0;--i) sift(r,i,m); for(i=m;i>1;--i) { w=r[i];r[i]=r[1]; r[1]=w; p+=3; sift(r,1,i-1); } } void sorting(sqlist &r,int t) { BeforeSort(); heapsort(r,t); display(p,q); } //-----------------------------------主函数 void main() { int a1[N],i; int e=N; for(i=0;i cout<<\排序前数组:\\n\for(i=0;i cout< for(i=0;i a[i].key=e--; } insertsort(a,N); e=N; for(i=0;i b[i].key=e--;} cout<<\ \\n\cout<<\希尔排序运行结果:\\n\shellsort(b,N); cout<<\ \\n\cout<<\选择排序运行结果:\\n\e=N; int c1[N]; for(i=0;i cout<<\ \\n\cout<<\快速排序运行结果:\\n\e=N; sqlist c; int low=0,high=10; for(i=0;i c[i].key=e--; } sort(c,low,high); cout<<\ \\n\cout<<\堆排序运行结果:\\n\sqlist d; e=N; for(i=0;i cout<<\排序后数组:\\n\for(i=0;i cout< {a1[i]=e++;} cout<<\排序前数组:\\n\for(i=0;i cout< for(i=0;i for(i=0;i b[i].key=e++; } cout<<\ \\n\cout<<\希尔排序运行结果:\\n\shellsort(b,N); cout<<\ \\n\cout<<\选择排序运行结果:\\n\e=1; for(i=0;i cout<<\ \\n\cout<<\快速排序运行结果:\\n\ e=1; for(i=0;i cout<<\ \\n\cout<<\堆排序运行结果:\\n\ e=1; for(i=0;i cout<<\排序后数组:\\n\for(i=0;i cout< a1[i]=rand()0; c1[i]=a1[i]; a[i].key=a1[i]; b[i].key=a1[i]; c[i].key=a1[i]; d[i].key=a1[i]; } cout<<\排序前数组:\\n\for(i=0;i gensort(a1,sizeof(a1)/sizeof(int)); cout< cout<<\插入排序运行结果:\\n\insertsort(a,N); cout< cout<<\希尔排序运行结果:\\n\shellsort(b,N); cout< cout<<\选择排序运行结果:\\n\gentsort(c1,N); cout< cout<<\快速排序运行结果:\\n\sort(c,low,high); cout< cout<<\堆排序运行结果:\\n\sorting(d,N); cout<<\排序后数组:\\n\for(i=0;i 程序运行基本正常。但有少量的语法错误。由于程序中没有给计数器清零。在每个算法程序开始时,将计数器的初值赋为零即可。 五、测试结果: 六、附录 源程序清单: #include void gensort(int b[],int n) { int i,j;int s=0,t=0; for(i=0;i for(j=i+1;j if(b[i]>b[j]) { int temp=b[i]; b[i]=b[j]; b[j]=temp; s+=3; }}} cout<<\移动次数=\比较次数=\} typedef int KeyType; struct rec { KeyType key; }; typedef rec sqlist[N]; void insertsort(sqlist b,int n) { int i,j;int s=0,t=0; for(i=2;i b[0]=b[i]; s++; j=i-1; t++; while(b[0].key b[j+1]=b[j]; j--; s++; t++; } b[j+1]=b[0]; s++; } cout<<\移动次数=\比较次数=\} void shellsort(sqlist b,int n) { int i,j,gap; rec x; int s=0,t=0; gap=n/2; while(gap>0) { for(i=gap+1;i j=i-gap; while(j>0) { t++; if(b[j].key>b[j+gap].key) { x=b[j];b[j]=b[j+gap]; b[j+gap]=x;j=j-gap; s+=3; } else j=0; gap=gap/2; }} cout<<\移动次数=\比较次数=\}} void gentsort(int b[],int n) { int i,j,k; int s=0,t=0; for(i=0;i for(j=i+1;j if(b[k]>b[j]) {k=j;} } if(k!=i) {int temp=b[k]; b[k]=b[i]; b[i]=temp; s+=3; }} cout<<\移动次数=\比较次数=\} void output(sqlist b,int n) { for(int i=0;i cout< void display(int n,int m) { cout<<\移动次数=\比较次数=\} void BeforeSort() { p=0;q=0; } void quicksort(sqlist r,int s,int t) { int i=s,j=t; if(s r[0]=r[s];p++; while(i while(i while(i r[j]=r[i];q++;p++; } r[i]=r[0];p++; } else return; quicksort(r,s,j-1); quicksort(r,j+1,t); } void sort(sqlist r,int s,int t) { BeforeSort(); quicksort(r,s,t); display(p,q); } void sift(sqlist r,int s,int m) { int j; rec x; x=r[s]; for(j=2*s;j<=m;j*=2) {q++; if(j if(!(x.key void heapsort(sqlist &r,int m) { int i;rec w; for(i=m/2;i>0;--i) sift(r,i,m); for(i=m;i>1;--i) { w=r[i];r[i]=r[1]; r[1]=w; p+=3; sift(r,1,i-1); } } void sorting(sqlist &r,int t) { BeforeSort(); heapsort(r,t); display(p,q); } void main() { int a1[N],i; int e=N; for(i=0;i cout<<\排序前数组:\\n\for(i=0;i cout< for(i=0;i a[i].key=e--; } insertsort(a,N); e=N; for(i=0;i b[i].key=e--;} cout<<\ \\n\cout<<\希尔排序运行结果:\\n\shellsort(b,N); cout<<\ \\n\cout<<\选择排序运行结果:\\n\e=N; int c1[N]; for(i=0;i cout<<\ \\n\cout<<\快速排序运行结果:\\n\e=N; sqlist c; int low=0,high=10; for(i=0;i c[i].key=e--; } sort(c,low,high); cout<<\ \\n\cout<<\堆排序运行结果:\\n\sqlist d; e=N; for(i=0;i cout<<\排序后数组:\\n\for(i=0;i cout< cout<<\排序前数组:\\n\for(i=0;i cout< for(i=0;i for(i=0;i b[i].key=e++; } cout<<\ \\n\ cout<<\希尔排序运行结果:\\n\shellsort(b,N); cout<<\ \\n\cout<<\选择排序运行结果:\\n\e=1; for(i=0;i cout<<\ \\n\cout<<\快速排序运行结果:\\n\e=1; for(i=0;i cout<<\ \\n\cout<<\堆排序运行结果:\\n\e=1; for(i=0;i cout<<\排序后数组:\\n\for(i=0;i cout< a1[i]=rand()0; c1[i]=a1[i]; a[i].key=a1[i]; b[i].key=a1[i]; c[i].key=a1[i]; d[i].key=a1[i]; } cout<<\排序前数组:\\n\for(i=0;i cout<<\插入排序运行结果:\\n\insertsort(a,N); cout< cout<<\希尔排序运行结果:\\n\shellsort(b,N); cout< cout<<\选择排序运行结果:\\n\gentsort(c1,N); cout< cout<<\快速排序运行结果:\\n\sort(c,low,high); cout< cout<<\堆排序运行结果:\\n\sorting(d,N); cout<<\排序后数组:\\n\for(i=0;i
正在阅读:
数据结构--内部排序的比较12-31
宝安区旧城、旧村改造管理暂行办法08-20
苏教版三年级语文下册练习三教案06-07
四川大学博物馆社会实践报告 - 图文03-30
C语言第五章循环习题04-28
C语言程序设计实训指导书01-20
典藏 | 永久驿站08-02
建立公司成本核算体系计划(工作计划)10-08
- exercise2
- 铅锌矿详查地质设计 - 图文
- 厨余垃圾、餐厨垃圾堆肥系统设计方案
- 陈明珠开题报告
- 化工原理精选例题
- 政府形象宣传册营销案例
- 小学一至三年级语文阅读专项练习题
- 2014.民诉 期末考试 复习题
- 巅峰智业 - 做好顶层设计对建设城市的重要意义
- (三起)冀教版三年级英语上册Unit4 Lesson24练习题及答案
- 2017年实心轮胎现状及发展趋势分析(目录)
- 基于GIS的农用地定级技术研究定稿
- 2017-2022年中国医疗保健市场调查与市场前景预测报告(目录) - 图文
- 作业
- OFDM技术仿真(MATLAB代码) - 图文
- Android工程师笔试题及答案
- 生命密码联合密码
- 空间地上权若干法律问题探究
- 江苏学业水平测试《机械基础》模拟试题
- 选课走班实施方案
- 数据结构
- 排序
- 内部
- 比较
- 中桃9号桃苗品种介绍 - 图文
- 5.1地图符号(1)
- 三国演义中为什么蜀国文武大臣都死得早
- 2018-2019-烟草员工工作计划-范文模板(6页)
- 《学记》读后感
- 军事理论心得体会作业
- 国际贸易实务试题(判断、单选及多选)-1
- 研讨会 新闻通稿
- 关于干部提拔任用工作情况的报告
- 企业应收账款的风险分析及其防范措施
- 2018-2019版九年级化学下册 9.2 金属的化学性质课后达标训练(含精析)(新版)鲁教版
- 酒桌上有哪些礼仪?
- 《Linux操作系统及应用项目教程》习题
- 六年级奥数-第二讲.比和比例 教师版
- 心的交流 爱的天空
- 无计划停风应急预案
- 修辞部分练习题参考答案
- 新龙县干部职工周转房1期 - 图文
- 《工作与人生》学习导向单
- 自动扶梯日常保养清洁和维修