![实验1分治算法_第1页](http://file2.renrendoc.com/fileroot_temp3/2021-6/3/7d3c1103-7bd0-49e8-9601-7b6932934d19/7d3c1103-7bd0-49e8-9601-7b6932934d191.gif)
![实验1分治算法_第2页](http://file2.renrendoc.com/fileroot_temp3/2021-6/3/7d3c1103-7bd0-49e8-9601-7b6932934d19/7d3c1103-7bd0-49e8-9601-7b6932934d192.gif)
![实验1分治算法_第3页](http://file2.renrendoc.com/fileroot_temp3/2021-6/3/7d3c1103-7bd0-49e8-9601-7b6932934d19/7d3c1103-7bd0-49e8-9601-7b6932934d193.gif)
![实验1分治算法_第4页](http://file2.renrendoc.com/fileroot_temp3/2021-6/3/7d3c1103-7bd0-49e8-9601-7b6932934d19/7d3c1103-7bd0-49e8-9601-7b6932934d194.gif)
![实验1分治算法_第5页](http://file2.renrendoc.com/fileroot_temp3/2021-6/3/7d3c1103-7bd0-49e8-9601-7b6932934d19/7d3c1103-7bd0-49e8-9601-7b6932934d195.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、算法设计与分析实验报告实验1分治算法姓名学号班级实验日期2015、1、13实验地点、实验目得1、掌握分治算法得设计思想与分析方法;2、掌握归并排序、快速排序等高效排序算法。二、实验环境1、硬件环境C PU:酷睿i5内存:4 GB硬盘:1TB2、软件环境操作系统:win10编程环境:D ev-C+ +编程语言:C语言 三、实验内容1、编写程序,实现归并排序算法.(1 )归并排序算法归并排序就是建立在归并操作上得一种有效得排序算法,该算法就是采用分治法(Div id e and C o n quer )得一个非常典型得应用。将已有序得子序列合并, 得到完全有序得序列;即先使每个子序列有序,再使子序
2、列段间有序。(2)归并排序算法分析 时间复杂度:O(nl og n )空间复杂度O(nlogn)(3) 编程要求待排序数组长度至少为16,数组中可以有相同元素;按递增排序。4)程序代码 (含注释) / 归并排序算法实现 # inc 1 u d e # in elude #defi ne M A XE 50?/ /线性表中最多元素个数 ty pe d ef i n t K eyType;ty p ede f ch ar I n foTyp e10;t yp edef st r uct? / /记录类型K ey Typ e key; ?/ 关键字项In foTy ped ata;?/ /其她数据项
3、,类型为In f oTy pe Re cTy pe;void Merge ( Rec Type R , i nt low ,i nt mid,in t high) /将两个有序表 R 1 ow、mid与Rmid+1、hig h归并为一个有序表RIo w、high中 ?Re cT ype *R1 ;int i=low, j = mid + 1,k=0; / k就是R1得下标,i、j分别为第1、2段得下标?R1= (ReCType * )ma llo c (h ig h low+ 1 )* sizeof(ReCType);/动态分配空间/在第1段与第2段均未扫whil e (i = mi d &
4、j = high)描完时循环f (Ri、 key=R j、 ke y)?/将第1段中得记录放入R1中?R1k=Ri;?i+ ;k+;?else/将第 2 段中得记录放入R1中? R1k=R Cj ;?j+;k+;whilei=mid)?/将第 1段余下部分复制到 R1?R1C k=Ri;i+;k+;?while (j =high)/将第 2 段余下部分复制到 R1?R 1 C k =Rj;?j+;k+; ?for (k = 0 ,i= low;i =high;k+, i + +)/将 R1 复制回 R中Ri = R1 k;V o id M er geP ass( RecT ype R, i n
5、t 1e ng t h,i nt n )?/ 实现一趟归并? i nt i ;?fo r (i= 0;i +2*le n gth 1 n; i =i+2 * le ng th ) ?/ 归并 len g t h长得两相邻子表?M e r g e (R, i, i +length 1, i+2* 1 ength-1);/余下两个子表,?/ 归并这两个子表i f (i +len gth 1 n )后者长度小于l engt h ?Merg e(R, i,i1 en gth-1, n-1); void M e r ge Sor t (R ec Typ e R: , i n t n) / 二路归并排序算
6、法?int length, k,i = 1 ;?/i用于累计归并得趟数f or (1 en g t h =1 ;1 engthn ;length=2 衣 length)MergeP a ss (R ,length, n);printf(”第趟归并,i+);/ 输出每一趟得排序结?fo r (k = 0;kn; k+)?p r intf(” d, Rk、key);?printf (n);in t m a in()?int i,k,n;RecTy pe R MAXE;?pri n t f(请输入元素个数 n:n);s canf (% d, & n);pr intf(请输入 d个元素:n”,n);f
7、or (i= 0;i n;i+) ?sc anf (”d”,&R i、key);?p rin t f( n ” ; ?M e rgeSort ( R,n) ; /执行排序函数prin tf (归并排序结果:n);”);printf(”for (k= 0;k竄归芹3&788901347143645&54789(簌趟归芽01336477B8947EgU564565第丄趟归彳0归并排序结果:133467Sg1126克47es7GSO0133467s3li3645476cS 7R寸2、编写程序,实现快速排序算法。(1)快速排序算法,其中一部分基本思想就是:通过一趟排序将要排序得数据分割成独立得两部分得
8、所有数据都比另外一部分得所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行 ,以此达到整个数据变成有序序(2)快速排序算法分析时间复杂度:0(niogn) 空间复杂度:0( nl o gn )(3)编程要求待排序数组长度至少为16,数组中可以有相同元素;按递增排序。(4) 程序代码(含注释)/ /快速排序算法实现# i nc 1 ude # de f in eMAXE 50?/ /线性表中最多元素个数typedef in tK ey Type;t ype d e fc ha rInfoType 1 0 ;typed ef st r uct/记录类型?KeyT
9、 ype ey ;/ /关键字项?QuickSo rt (R, i+ l,t) ;/对右区间递归排序 Re cType ;void QuickSort(ReCrype R , int s,1 nt t)/对R s至R t得元素进行快速排序int i = s,j= t ,k;?RecType t emp;?if (s 1&Rj、keyte m p、key)?/从右向左扫描,找第1个关键字小于tem p、key 得 R jif (ij)/表示找到这样得R j,R i、Rj 交换? ?Ri=Rj;?i+;?while (ivj & Ri、ke y t emp、key)i+; ?/从左向右扫描,找第1
10、个关键字大于t emp、ke y得记录 R1if (ij)?/表示找到这样得R 1 , Ri、R j交换? ?Rj= R i;?j-;?Ri=t emp;?Qu ic kSor t(R,s, i 1); /对左区间递归排序? in t main()?i n t i, k ,n;R ecType R MAXE;?prin t f(请输入元素个数n:n ”);s canf ( % d”,&n );?prin tf (请输入 d 个元素:、n, n );f o r (i =0;ivn; i+)sea nf( ” 4&Ri、key);?pr in tf (” n” );Qui C kS ort (R, 0,n 1) ;/?执行排序函数pri n tf (快速排序结果:n”););?pr i nt f (”for (k= 0; kke y);prin tf ( nn );re tu r n 0;(5)程序输出23IS 请输人1亍元素;1 27 9S 3 4 7 G 9 1G 23 1035 14 30快退排序结果:234567791014 IS四、实验总结(心得体会、需要注意得问题等 )
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 八年级英语上册 Module 4 Planes ships and trains Unit 1 He lives the farthest from school教案 (新版)外研版
- 《高强磁悬挂式永磁除铁器》(征求意见稿)
- 小学语文二年级上册《称赞》教学设计二
- 劳动最美丽-奋斗正青春团课课件
- 地基与基础工程质量验收证明单
- 株洲市三三一医院招聘笔试真题2023
- 2023年北京市先农坛体育运动技术学校招聘考试真题
- 第二十四章安全保证体系和安全措施
- 山东铁投集团社会招聘笔试真题2023
- 吉安市阳光学校招聘军事教官笔试真题2023
- 人教版三年级上册数学全册课件(2022年9月新版)
- 2022年生物社团活动总结
- 灭菌验证方案
- 3.7表内乘法(一)整理与复习教案 2022-2023学年二年级数学上册-冀教版
- 污水管道工程的拖拉管定向钻施工方案
- 空调自控系统安装确认(IQ)方案
- TECO-N310系列变频器参数设定说明
- 机械与电气识图教材课件汇总完整版ppt全套课件最全教学教程整本书电子教案全书教案课件合集
- 食堂会计核算与会计科目
- 企业注销登记申请书
- JJG 672-2018 氧弹热量计检定规程-(高清现行)
评论
0/150
提交评论