数据结构实验四题目一排序实验报告
14页1、数据结构实验报告 实验名称: 实验四排序学生姓名:XX班 级:班内序号:学 号:日 期:1实验要求实验目的: 通过选择实验内容中的两个题目之一,学习、实现、对比、各种排序的算法,掌握 各种排序算法的优劣,以及各种算法使用的情况。题目 1: 使用简单数组实现下面各种排序算法,并进行比较。排序算法如下:1、插入排序;2、希尔排序;3、冒泡排序;4、快速排序;5、简单选择排序;6、堆排序;7、归并排序;8、基数排序(选作)9、其他。具体要求如下:1、测试数据分成三类:正序、逆序、随机数据。2、对于这三类数据,比较上述排序算法中关键字的比较次数和移动次数(其中关 键字交换记为 3 次移动)。3、对于这三类数据,比较上述排序算法中不同算法的执行时间,精确到微妙。4、对2和 3的结果进行分析,验证上述各种算法的时间复杂度。5、编写main ()函数测试各种排序算法的正确性。2. 程序分析2.1 存储结构存储结构:数组0A11A22A33A44A55A6NAn-12.2 关键算法分析一、关键算法:1、插入排序a、取排序的第二个数据与前一个比较b、若比前一个小,则赋值给哨兵c、从后向前比较,将其插入在
2、比其小的元素后d、循环排序2、希尔排序a、将数组分成两份b、将第一份数组的元素与哨兵比较c、若其大与哨兵,其值赋给哨兵d、哨兵与第二份数组元素比较,将较大的值赋给第二份数组e、循环进行数组拆分3、对数据进行编码a、取数组元素与下一个元素比较b、若比下一个元素大,则与其交换c、后移,重复d、改变总元素值,并重复上述代码4、快速排序a、选取标准值b、比较高低指针指向元素,若指针保持前后顺序,且后指针元素大于标准值,后 指针前移,重新比较c、否则后面元素赋给前面元素d、若后指针元素小于标准值,前指针后移,重新比较e、否则前面元素赋给后面元素5、简单选择排序a、从数组中选择出最小元素b、若不为当前元素,则交换c、后移将当前元素设为下一个元素堆排序a、生成小顶堆b、将堆的根节点移至数组的最后c、去掉已做过根节点的元素继续生成小顶堆d、数组倒置7、归并排序a、将数组每次以1/2拆分,直到为最小单位b、小相邻单位数组比较重排合成新的单位c、循环直至完成排序二、代码详细分析:1、插入排序关键代码: 取排序的第二个数据与前一个比较:if(rivri-l) 若比前一个小,则赋值给哨兵: r0=ri; 从后
3、向前比较,将其插入在比其小的元素后: for(j=i-l;r0rj;j-)rj+l=rj;a+; rj+l=r0; 循环排序2、希尔排序关键代码: 将数组分成两份: d=n/2 将第一份数组的元素与哨兵比较: for(int i=d+l;i=n;i+) 若其大与哨兵,其值赋给哨兵: if(r00&r0=l;d=d/2)3、冒泡排序关键代码: 取数组元素与下一个元素比较: for(int i=l;iri+l) 若比下一个元素大,则与其交换: r0=ri; ri=ri+l; ri+l=r0; 后移,重复: for(int i=l;ibound;i+) 改变总元素值,并重复上述代码: int bound=pos;4、快速排序关键代码: 选取标准值: r0=ri 比较高低指针指向元素,若指针保持前后顺序,且后指针元素大于标准值,后指针前移,重新比较: while(i=flag) j-; 否则后面元素赋给前面元素: ri=rj; 若后指针元素小于标准值,前指针后移,重新比较: while(ij&ri=flag) i+; 否则前面元素赋给后面元素: rj=ri;5、简单选择排序关键代码: 从数组中
《数据结构实验四题目一排序实验报告》由会员壹****1分享,可在线阅读,更多相关《数据结构实验四题目一排序实验报告》请在金锄头文库上搜索。
巩固发展创建文明城市工作情况汇报
留守儿童帮扶计划书
药品补充申请办事指南优秀范文五篇
初级银行从业《风险管理》考前(难点+易错点剖析)押密卷答案参考90
新教材八年级数学上册 1.1.1 探索勾股定理教学案北师大版
2023年农村房屋转让合同(份范本)
驾驶员年终工作总结范本(5篇).doc
2022年11月广东外语外贸大学门诊部公开招聘1名非事业编制工作人员笔试参考题库(答案解析)
购买土地合同样本(九篇).doc
小学一年级下学期少先队工作总结
小学六年级数学列方程解稍复杂的分数应用题教案
县领导城市管理会议讲话模板(2篇)
云南省迪庆州香格里拉中学2019-2020学年高一物理上学期期末考试试题
环保的工作总结范文5篇
黑龙江医保服务项目可研报告【参考模板】
临水临电专项施工方案
二手车买卖合同协议书范文(六篇)
MOA-30KV避雷器检测仪使用说明书
开幕式表演解说词
×××农电局供电所制度
2023-02-28 3页
2023-09-30 5页
2022-11-16 10页
2023-06-08 16页
2022-09-21 17页
2023-12-31 9页
2023-04-23 44页
2023-08-06 8页
2023-06-04 18页
2024-02-21 11页