




已阅读5页,还剩3页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
南京邮电大学通达学院实验报告实验名称: 快速排序算法 课程名称:微型计算机原理与接口技术姓名 班级学号: 钱煜中 142501 14250120 实验时间: 2016.12.2 快速排序原理一、 实验原理:快速排序算法quick sort主要是利用分治递归的思想进行排序的方法。它的原理是首先从待排序的原始序列ap,r中选取一个元素aq作为分界点(pivot),然后将序列分为两个子序列,左边子序列ap,q-1元素的值都小于分界点m,右边子序列aq+1,r元素值都大于分界点的值,此时得到的序列命名为a,而aq应该处于其排好序后的正确位置。然后利用递归的思想,对左右两个子序列ap,q-1和aq+1,r再分别进行排序,直到子序列的长度为1结束,序列有序。其中,选取a中的基准分界点的方式有多种,或者选择序列的首元素ap,或者选择序列的尾元素ar,或者选择序列中间位置的元素a(p+r)/2,或者取这三个元素按照大小排序后的中间值。例子:a = 38, 81, 22, 48, 13, 69, 93, 14, 45, 58, 79, 72,取(left+right)/2处的元素作为分界点(pivot)的值。具体第一次分区过程如下:因此,第一次分区,以69为分界点,结果为:a= 14, 58, 22, 48, 13, 38, 45, 69, 93, 81, 79, 72。二、 实验代码#include int fast_sort(int *a,int i,int j,int *p,int *b)int k,temp,f,g;g=*p;g=(12*g)-12;/intf(成功进入快速排序 g=%dn,g);k=i;i+;for(;iak&ij;)j-;for(;aiak&ij;)i+;/intf(i=%dn,i);if(i=j)break;if(iaj)temp=ak;ak=aj;aj=temp;/r(f=0;f12;f+)/intf(%3d,af);/printf(排序成功 n);for(f=0;f12;f+)*(b+g+f)=af;return j;void digui(int *a,int i,int j,int *p,int *b,int *z)int k;if(i*z)*z=*p;/printf(z=%dnp=%d,*z,*p);*p=*p-1;void main()int a=38, 81, 22, 48, 13, 69, 93, 14, 45, 58, 79, 72;int b1012;int y=0,k,x=0,z=0;printf( 初始序列为 );for(k=0;k12;k+)printf(%3d,ak );printf(n);digui(a,0,11,&x,b,&z);for(y=1;yz+1;y+)printf(第%2d次后的数组为,y);for(k=0;k12;k+)printf(%3d,by-1k);printf(n);三、 实验数据(给出实验结果) 对序列a = 38, 81, 22, 48, 13, 69, 93, 14, 45, 58, 79, 7238 81 22 48 13 69 93 14 45 58 79 7238 14 22 48 13 69 93 81 45 58 79 7238 14 22 13 48 69 93 81 45 58 79 72进行快速排序,其中,以序列的首元素作为排序的分界点。输出结果要求:输出每一次分区后的结果以及最终排序结果。四、 实验总结(问题、解决方法、心得体会等)这次实验我做了很久,重新编写了算法很多次。最开始我对算法的理解不够深,在递归自调用的时候没有想通上下界其实在递归下一层的时候下一层是知道上一层的上下界的,只要排序算法里返还一个最好作为比较值的位置就可以了。一开始排序算法写完就把每次数输出出来,知道后来和同学讨论正确答案是排序了多少次,才想想到我是把每个区排完后的情况,而其实我想输出的是每次排序后数组情况。可是一开始进入的就是左半区的左半区的左半区。反正一次是无法输出全部的,因为右半区还没有算。思考了很久,我决定建立一个二维数组,第一行是第一次后的数组,第二行是第二次后的数组。可是如何确定现在是第几次?我建立了一个指针,每次进入递归一层就会+1,
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025至2030年中国工艺纸辫市场分析及竞争策略研究报告001
- 高数药学期末试卷及答案
- 教育培训机构融资担保企业制定与实施新质生产力战略研究报告
- 期货AI应用企业制定与实施新质生产力战略研究报告
- 阅读障碍辅助软件企业制定与实施新质生产力战略研究报告
- 企业食品安全管理人员考试习题及解析2(餐饮服务篇)
- 舞蹈表演在线平台行业跨境出海战略研究报告
- 阅读积分制度行业跨境出海战略研究报告
- 农村道路畅通工程路面加宽改造施工方案与实施
- 建筑工程施工现场管控策略与重要性研究
- 《浅谈A企业消防安全管理中存在的问题及完善对策研究》6300字(论文)
- 秦汉考古Uooc课程答案
- 《电力建设工程施工安全管理导则》(NB∕T 10096-2018)
- 医疗器械考试题及答案
- 画饼充饥儿童故事绘本 课件
- 心理护理的沟通与技巧
- 开关、插座及其它电气设备技术规格书
- 早期阻断性矫治-乳前牙反颌的矫治(口腔正畸科)
- 手术室护士子宫切除手术护理配合常规
- DB61T 5097-2024 强夯法处理湿陷性黄土地基技术规程
- 药物临床试验统计分析计划书
评论
0/150
提交评论