




已阅读5页,还剩7页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
一、试验内容内部排序算法效率比较平台的设计与实现二、试验目的问题描述:各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。试通过随机的数据比较几种主要的基本算法的关键字比较次数和关键字移动次数,以取得直观感受。开始三、流程图 冒泡排序J=N-1I=0aiai+1 否 是ai与ai+1交换 I+ I=j 否J=J-1结束J=0?否开 始 简单选择排序int i=1;假 iL.length真int j=i;k=i+1 假kL.lenth真L.rj.keyL.rk.key j=k; k+ i!=j 假真 L.ri L.rji+结 束 直接插入排序开始i=2假i=L.length真L.ri.keyL.ri-1.key假真L.r0=L.ri;L.ri=L.ri-1;j=i-2;假L.r0.keyL.rj.key真L.rj+1=L.rj;-j;L.rj+1=L.r0+i结束 希尔排序开始k=0假kt真ShellInsert(&L,dltak,&r);i=dk+1;假i=L.length真假L.ri.key0&L.r0.keyL.rj.key假真L.rj+dk=L.rj;j-=dk;L.rj+dk=L.r0+i+k结束 快速排序开始Lowhigh真-high假+low真Lowhigh&L.rhigh.key=pivotkey77L.rlow=L.rhighLow=pivotkey77真L.r0=L.rlowPivotkey=L.rlow.key假L.rhigh=L.rlow结束L,low,high假开始真LowhighL,low=pivotloc+1,high=highPivotloc=partioion(L,low,high),low=low,high=pivotloc-1;LowhighL,low,high假真假Pivotloc=partioion(L,low,high),low=low,high=pivotloc-1;QSort(L,low,pivotloc-1)结束四、源程序代码#define N 10int compare6=0,0,0,0,0,0,change6=0,0,0,0,0,0;void input(int s)int testN; srand(unsigned)time(NULL); for(int i=0;iN;i+) testi=rand()%100; for(int j=0;ji;j+) while(testj=testi) testi=rand()%N; j=0; for(i=0;i=N-1;i+)si=testi;void swap(int &a,int &b) int tmp; tmp=a; a=b; b=tmp;void insertsort(int s)int i,j;int aN+1;for(i=1;i=N;i+)ai=si-1;for(i=2;i0&a0aj-1&(+compare0);j-)aj=aj-1;change0+;aj=a0;change0+;void bubble_sort(int s,int n)int i,j,temp,aN;for(i=0;in;i+)ai=si;for(i=0;in-1;i+)for(j=0;j aj+1)temp = aj;aj = aj+1;aj+1 = temp;change1+;int partition(int a,int low,int high)int t,key;t=alow;key=alow;while(lowhigh)while(low=key)high-;+compare2;if(lowhigh)alow=ahigh;low+;change2+;while(lowhigh&alow=key)low+;+compare2;if(lowhigh)ahigh=alow;high-;change2+;alow=t;return low;void quicksort(int a,int low,int high)int key;if(lowhigh)key=partition(a,low,high);quicksort(a,low,key-1);quicksort(a,key+1,high);void selectsort(int s,int n)int i,j,k,aN;int t;for(i=0;in;i+)ai=si;for(i=0;in-1;i+)j=i;for(k=i+1;k=n-1;k+)if(akaj&(+compare3)j=k;if(j!=i)t=ai;ai=aj;aj=t;change3+;void shellinsertsort(int s,int n)int i,k,aN;k=int(n/2);for(i=0;i 0; gap /= 2) for(int i = gap; i 0 & tmp aj-gap; j -= gap)aj = aj-gap; compare4+;aj = tmp;change4+; void heap_adjust(int array,int i,int len) int rc = arrayi; for(int j = 2 * i; j len; j *= 2) if(j len & arrayj = arrayj) break; arrayi = arrayj; i = j; arrayi = rc;void heap_sort(int a,int len) int i; for(i = (len-1)/2; i = 0; i-) heap_adjust(a,i,len); for( i = (len-1); i 0; i-) swap(a0,ai);change5+;/弹出最大值,重新对i-1个元素建堆 heap_adjust(a,0,i-1); void CMyDlg:OnButton1() / TODO: Add your control notification handler code hereUpdateData(TRUE);int s10,a10;input(s);for(int i=0;iN;i+)ai=si;CString str100;for(i=0;i100;i+)stri=ai;for(i=0;i N;i+) stri.Format(%i,ai); /把整型数组添加到字符串 m_shuju1+=stri;insertsort(s);m_zhijie1=compare0;m_zhijie2=change0;quicksort(a,0,N-1);m_kuaisu1=compare2;m_kuaisu2=change2;selectsort(s,N);m_jiandan1=compare3;m_jiandan2=change3;shellinsertsort(s,N);m_xier1=compare4;m_xier2=change4;heap_sort(a,N);m_dui1=compare5;m_dui2=change5;bubble_sort(s,N);m_maopao1=compare1;m_maopao2=change1;CString str2100;for(i=0;i100;i+)str2i=si;for(i=0;i N;i+) str2i.Format(%i,ai); /把整型数组添加到字符串 m_shuju2+=str2i;UpdateData(FALSE);五、调试过程对于算法的设计,除了希尔排序和堆排序之外,
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 淡水养鱼课件
- 高考冲刺演讲稿(汇编15篇)
- 2025年乡村医生考试模拟试卷:农村居民健康素养提升关键考点
- 中铁安全质量培训试题及答案解析
- 物理安全培训试题及答案解析
- 2025年护士相关专业题库及答案
- 2025年大学《朝鲜语》专业题库- 朝鲜语专业的实践经验
- 2025年大学《爪哇语》专业题库- 爪哇语专业的实践教学与实习安排
- 2025年大学《大学俄语》专业题库- 俄语专业毕业生职场心得
- 2025年大学《大学俄语》专业题库- 俄语专业的学科融合与学术交流
- 第四章功能性油脂及其加工技术讲课文档
- 慢性乙肝教学课件
- 2025年潍坊市中考英语试卷(含答案解析)
- 【02-新课预习】第10讲 专题提升- 运动图像与追及相遇问题 (教师版) -2025新高一物理暑假衔接讲练 (人教版)
- 建筑垃圾消纳场建设工程经济效益和社会效益分析报告
- 施工企业会计实务课件
- DB53∕T 1090-2022 高速公路交通气象站网建设技术规范
- 中国城市轨道交通全自动运行系统技术指南
- 广东省春季高考数学试卷
- 中国篆刻史课件
- DB2301∕T 178-2024 地下市政基础设施普查及信息化管理平台建设技术规程
评论
0/150
提交评论