下载文档原格式
数据结构排序算法综合实验报告姓名：xx x x班级：10电信1学号：xxx指导老师：胡圣荣日期：2012.12.15～2013.1.5华南农业大学工程学院算法基本思想：1、插入排序：每次将一个待排序的记录，按其关键字大小插入到前面已经排序好的序列中的适当位置，直到全部记录插入完毕为止。
（1）直接插入排序：在排序过程中，每次都讲无序区中第一条记录插入到有序区中适当位置，使其仍保持有序。
初始时，取第一条记录为有序区，其他记录为无序区。
显然，随着排序过程的进行，有序区不断扩大，无序区不断缩小。
最终无序区变为空，有序区中包含了所有的记录，排序结束。
（2）希尔排序：将排序表分成若干组，所有相隔为某个“增量”的记录为一组，在各组内进行直接插入排序；初始时增量d1较大，分组较多（每组的记录数少），以后增量逐渐减少，分组减少（每组的记录数增多），直到最后增量为1（d1>d2>...>dt=1）,所有记录放为一组，再整体进行一次直接插入排序。
2、交换排序：每次比较两个待排序的记录，如果发现他们关键字的次序与排序要求相反时就交换两者的位置，直到没有反序的记录为止。
（1）冒泡排序：设想排序表R[1]到R[n]垂直放置，将每个记录R[i]看作是重量为R[i].key 的气泡；根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡违反本原则的轻气泡，就使其向上“漂浮”，如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。
（2）快速排序：在待排序的n个记录中任取一个作为“基准”，将其与记录分为两组，第一组中个记录的键值均小于或等于基准的键值，第二组中个记录的键值均大于或等于基准的键值，而基准就排在这两组中间（这也是该记录的最终位置），这称为一趟快速排序（或一次划分）。
对所分成的两组重复上述方法，直到所有记录都排在适当位置为止。
3、选择排序：每次从待排序的记录中选出关键字最小（或最大）的记录，顺序放在已排好序的子序列的后面（或最前），直到全部记录排序完毕。
c语言排序综合课程设计一、教学目标本课程的教学目标是使学生掌握C语言排序算法的原理和实现方法，能够运用排序算法解决实际问题。
具体目标如下：1.理解排序算法的基本概念和分类。
2.掌握常用的排序算法（冒泡排序、选择排序、插入排序、快速排序等）的原理和实现。
3.了解排序算法的性能分析（时间复杂度、空间复杂度等）。
4.能够使用C语言实现各种排序算法。
5.能够对给定的数据集进行排序，并分析排序结果。
6.能够根据实际问题选择合适的排序算法。
情感态度价值观目标：1.培养学生的逻辑思维能力和解决问题的能力。
2.培养学生对计算机科学的兴趣和热情。
3.培养学生团队合作精神和自主学习能力。
二、教学内容根据教学目标，本课程的教学内容主要包括以下几个部分：1.排序算法的基本概念和分类。
2.冒泡排序、选择排序、插入排序、快速排序等常用排序算法的原理和实现。
3.排序算法的性能分析（时间复杂度、空间复杂度等）。
4.排序算法在实际问题中的应用。
第1周：排序算法的基本概念和分类。
第2周：冒泡排序和选择排序的原理和实现。
第3周：插入排序和快速排序的原理和实现。
第4周：排序算法的性能分析。
第5周：排序算法在实际问题中的应用。
三、教学方法为了达到本课程的教学目标，将采用以下教学方法：1.讲授法：通过讲解排序算法的基本概念、原理和实现方法，使学生掌握排序算法的基础知识。
2.案例分析法：通过分析实际问题，让学生了解排序算法在实际中的应用。
3.实验法：让学生通过动手实践，加深对排序算法的理解和掌握。
4.小组讨论法：鼓励学生之间进行讨论和交流，培养团队合作精神和自主学习能力。
四、教学资源为了支持本课程的教学内容和教学方法的实施，将准备以下教学资源：1.教材：《C语言程序设计》。
2.参考书：《算法导论》、《数据结构与算法分析》。
3.多媒体资料：PPT课件、教学视频等。
4.实验设备：计算机、网络等。
五、教学评估为了全面、客观、公正地评估学生的学习成果，本课程将采用以下评估方式：1.平时表现：通过课堂参与、提问、讨论等环节，评估学生的学习态度和积极性。
.大连科技学院数据结构课程设计题目排序综合学生专业班级指导教师职称副教授所在单位信息科学系软件教研室教学部主任完成日期2013 年1月11 日.课程设计报告单学号专业班级网络工程11-1考核项目评分备注平时工作态度及遵守纪律情况1（10 分）掌握基本理论、关键知识、基本技能的程度和2阅读参考资料的水平（10 分）独立工作能力、综合运用所学知识分析和解决3问题能力及实际工作能力提高的程度（20 分）完成课程设计说明书及软件的情况与水平（小组分工情况、规性、整洁清楚、叙述完整性、4思路清晰程度、工作量及实际运行情况和创新性）（60 分）总评成绩综合评定：（优、良、中、及格、不及格）指导教师签字：2013年1月11日数据结构课程设计任务书一、任务及要求：1.设计（研究）任务和要求研究容：排序综合任务和要求：（1）学习数据结构基础知识，掌握数据结构典型的算法的使用。
（2）对指导教师下达的题目进行系统分析。
（3）根据分析结果完成系统设计。
（4）编程：在计算机上实现题目的代码实现。
（5）完成对该系统的测试和调试。
（6）提交课程设计报告。
要求完成课程设计报告3000 字以上 (约二十页 )。
完成若干综合性程序设计题目，综合设计题目的语句行数的和在100 行语句以上。
2.原始依据结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。
提高程序设计和调试能力。
学生通过上机实习，验证自己设计的算法的正确性。
学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。
3.参考题目：二、工作量2 周（ 10 个工作日）时间三、计划安排第 1 个工作日：查找相关资料、书籍，阅读示例文档，选择题目。
第 2 个工作日－第 3 个工作日：设计程序结构、模块图。
第 4 个工作日－第 9 个工作日：完成程序的编码，并且自己调试、测试。
穿插进行课程设计报告的撰写。
第 10 个工作日：上交课程设计报告，由教师检查软件测试效果、检查课程设计报告，给出学生成绩。
课程设计排序实验报告一、教学目标本课程的教学目标是使学生掌握XX学科的基本知识，提高学生的XX技能，培养学生的科学素养和探究精神。
具体来说，知识目标包括：1.掌握XX学科的基本概念、原理和规律。
2.了解XX学科的发展历程和现状。
3.学会运用XX学科的知识解决实际问题。
技能目标包括：1.能够运用实验方法进行科学探究。
2.能够运用数学方法对实验数据进行分析和处理。
3.能够撰写实验报告，表达自己的观点和结论。
情感态度价值观目标包括：1.培养学生对科学的热爱和好奇心，激发学生探索未知的欲望。
2.培养学生尊重事实、严谨治学的科学态度。
3.培养学生团队合作、沟通交流的能力。
二、教学内容根据课程目标，教学内容主要包括XX学科的基本概念、原理和规律，以及实验方法和技能。
具体安排如下：1.第一部分：XX学科的基本概念、原理和规律。
包括章节1-5，主要介绍XX学科的基础知识，如XX现象的产生、XX规律的应用等。
2.第二部分：实验方法和学习技能。
包括章节6-8，主要介绍实验设计、实验操作、实验数据分析等方法，以及如何撰写实验报告。
3.第三部分：综合应用。
包括章节9-10，主要结合实际问题，让学生运用所学知识和技能进行分析和解决。
三、教学方法为了实现课程目标，我们将采用多种教学方法，如讲授法、讨论法、案例分析法、实验法等。
具体安排如下：1.讲授法：用于传授基本概念、原理和规律，引导学生理解并掌握知识点。
2.讨论法：用于探讨实验现象、分析实验数据，培养学生的思考和表达能力。
3.案例分析法：通过分析实际案例，让学生学会运用所学知识解决实际问题。
4.实验法：让学生亲自动手进行实验，培养学生的实验操作能力和科学探究精神。
四、教学资源为了支持教学内容和教学方法的实施，我们将准备以下教学资源：1.教材：选用权威、实用的教材，为学生提供系统、全面的学习材料。
2.参考书：提供相关领域的参考书籍，拓展学生的知识视野。
3.多媒体资料：制作课件、视频等多媒体资料，提高课堂教学的趣味性和效果。
课程设计课程设计名称：专业班级：学生姓名：学号：指导教师：排序综合0000000000000 0000000000000 00000000000000 00000000000000课程设计时间:2010621 -2010625计算机科学与技术专业课程设计任务书说明：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页信息科学与工程学院课程设计成绩评价表信息科学与工程学院课程设计成绩评价表课程名称：数据结构课程设计设计题目：排序1、需求分析1.1、直接插入排序思路:设有一组关键字{K1,K2,…….,Kn},排序开始变认为K1是一个有序的序列, 让K2插入到表长为1的有序序列，使之成为一个表长为2的有序序列,让K3插入到表长为2的有序序列,使之成为一个表长为3的有序序列，依次类推,最后让Kn插入上述表长为n-1的有序序列,得到一个表长为n的有序序列.1.2、希尔排序思路：先取一个正整数d1（d1<n）把全部记录分成di个组，所有距离为di的倍数的记录看成是一组，然后在各组内进行插入排序；然后取d2（d2<d1）,重复上述分组和排序操作，直到取di=1（>=1）,即所有记录成为一个组为此.一般选di约为n/2,d2 为d1/2,…….,di=11・3、快速排序：（递归和非递归）思路:以第一个关键字K1为控制字，将[Ki、K2、….K n]分成两个子区，使左区的有关键字小于等于K1 ,右区所有关键字大于等于K1,最后控制居两个子区中间的适当位置。
在子区内数据尚处于无序状态。
将右区首、尾指针保存入栈，对左区进行与第（1）步相类似的处理，又得到它的左子区和右子区，控制字区中。
重复第（1）、（2）步，直到左区处理完毕。
然后退栈对一个个子区进行相类似的处理，直到栈空分区处理函数hoare思路：首先用两个指针i、j分别指向首、尾两个关键字，i=1，j=8。
如对（46、56、14、43、95、10、19、72）。
c语言课程设计排序综合一、教学目标本章节的教学目标是让学生掌握C语言中的排序算法，包括冒泡排序、选择排序和插入排序。
学生需要了解排序算法的原理和实现方式，能够运用排序算法解决实际问题。
此外，学生还需要掌握排序算法的性能分析，能够根据实际需求选择合适的排序算法。
通过本章节的学习，学生应该能够达到以下具体的学习成果：1.知识目标：–了解排序算法的概念和作用；–掌握冒泡排序、选择排序和插入排序的原理和实现方式；–理解排序算法的性能分析方法。
2.技能目标：–能够编写C语言程序实现排序算法；–能够对给定的数据集进行排序并分析性能。
3.情感态度价值观目标：–培养学生的逻辑思维能力和问题解决能力；–培养学生对计算机科学和编程的兴趣和热情。
二、教学内容本章节的教学内容主要包括排序算法的原理和实现、排序算法的性能分析和应用。
具体的教学大纲如下：1.排序算法的概念和作用–介绍排序算法的定义和目的；–解释排序算法在计算机科学中的应用。
2.冒泡排序–介绍冒泡排序的原理和实现方式；–分析冒泡排序的时间复杂度和空间复杂度。
3.选择排序–介绍选择排序的原理和实现方式；–分析选择排序的时间复杂度和空间复杂度。
4.插入排序–介绍插入排序的原理和实现方式；–分析插入排序的时间复杂度和空间复杂度。
5.排序算法的性能分析–介绍排序算法的性能分析方法；–分析不同排序算法的性能特点和适用场景。
6.排序算法的应用–举例说明排序算法在实际问题中的应用；–引导学生思考如何选择合适的排序算法解决实际问题。
三、教学方法为了达到本章节的教学目标，我将采用以下教学方法：1.讲授法：通过讲解排序算法的原理和实现方式，帮助学生理解排序算法的基本概念和思路。
2.案例分析法：通过分析具体的排序算法案例，让学生能够更好地理解排序算法的应用和性能特点。
3.实验法：让学生通过编写C语言程序实现排序算法，培养学生的编程能力和问题解决能力。
4.讨论法：引导学生进行小组讨论，分享各自的排序算法实现和性能分析结果，促进学生之间的交流和合作。
课程设计排序综合一、教学目标本课程的教学目标是使学生掌握排序综合的基本知识和技能，能够运用排序算法解决实际问题。
具体目标如下：1.知识目标：学生能够理解排序算法的概念和原理，掌握常见的排序算法（如冒泡排序、选择排序、插入排序等）的实现和优缺点。
2.技能目标：学生能够运用排序算法解决实际问题，如对给定的数据集进行排序，并分析排序算法的性能。
3.情感态度价值观目标：学生通过学习排序算法，培养逻辑思维能力、问题解决能力和创新意识，提高对计算机科学和信息技术的兴趣。
二、教学内容本课程的教学内容主要包括排序算法的概念、原理和实现。
具体安排如下：1.排序算法的概念和原理：介绍排序算法的定义、分类和性能评价指标。
2.常见排序算法的实现：介绍冒泡排序、选择排序、插入排序等常见排序算法的具体实现。
3.排序算法的应用：通过实际问题，引导学生运用排序算法解决问题，并分析排序算法的性能。
4.排序算法的优化：介绍排序算法的优化方法和策略，如快速排序、归并排序等。
三、教学方法为了实现本课程的教学目标，采用多种教学方法相结合的方式，包括：1.讲授法：通过讲解排序算法的概念、原理和实现，使学生掌握相关知识。
2.讨论法：学生进行小组讨论，分享排序算法的应用经验和优化策略。
3.案例分析法：通过分析实际问题，引导学生运用排序算法解决问题。
4.实验法：安排实验课，让学生动手实现排序算法，并分析其性能。
四、教学资源为了支持本课程的教学内容和教学方法的实施，准备以下教学资源：1.教材：选择一本合适的教材，如《数据结构与算法》。
2.参考书：提供相关的参考书籍，如《排序与搜索》。
3.多媒体资料：制作PPT、教学视频等多媒体资料，以便于讲解和演示。
4.实验设备：准备计算机、网络等实验设备，以便于学生进行实验操作。
五、教学评估本课程的评估方式包括平时表现、作业和考试等。
评估方式应客观、公正，能够全面反映学生的学习成果。
具体安排如下：1.平时表现：通过观察学生在课堂上的参与度、提问和回答问题的表现，评估学生的学习态度和理解程度。
课课程设计排序综合一、教学目标本课程的教学目标是使学生掌握排序综合的基本概念、原理和方法，能够运用排序综合的思路分析实际问题，并熟练使用相关工具进行数据处理和分析。
具体来说，知识目标包括：了解排序综合的基本概念和原理，掌握排序综合的主要方法和步骤，理解排序综合在实际应用中的意义和价值。
技能目标包括：能够运用排序综合的方法分析实际问题，熟练使用相关工具进行数据处理和分析，能够撰写排序综合的分析报告。
情感态度价值观目标包括：培养学生的逻辑思维能力、创新意识和团队协作精神，提高学生分析问题和解决问题的能力。
二、教学内容本课程的教学内容主要包括排序综合的基本概念、原理和方法，以及排序综合在实际应用中的案例分析。
具体来说，教学大纲安排如下：1.排序综合的基本概念和原理：介绍排序综合的定义、特点和基本原理，包括排序综合的数学基础和相关概念。
2.排序综合的主要方法和步骤：讲解排序综合的主要方法，如快速排序、归并排序、堆排序等，以及排序综合的基本步骤，包括数据预处理、排序和结果分析。
3.排序综合在实际应用中的案例分析：通过具体案例分析，使学生了解排序综合在实际问题中的应用和效果，包括数据处理和分析的过程和方法。
三、教学方法本课程的教学方法主要包括讲授法、案例分析法和实验法。
具体来说，教学方法安排如下：1.讲授法：通过教师的讲解和演示，使学生掌握排序综合的基本概念、原理和方法，以及相关工具的使用。
2.案例分析法：通过具体案例的分析，使学生了解排序综合在实际问题中的应用和效果，培养学生的分析能力和解决问题的能力。
3.实验法：通过实验操作，使学生熟练掌握相关工具的使用，提高学生的实际操作能力和实践能力。
四、教学资源本课程的教学资源主要包括教材、参考书、多媒体资料和实验设备。
具体来说，教学资源安排如下：1.教材：选择适合本课程的教材，作为学生学习的主要参考资料，包括相关概念、原理和方法的讲解，以及案例分析和实验操作的指导。
《数据结构》课程设计报告学生姓名:学号：学院: 理学院班级:题目: 题目33 排序综合指导教师：职称:讲师实验师讲师2012年12月28日目录目录 (I)一、选题背景 (1)1.1 背景 (1)1.2 摘要 (1)1.3 性能比较.............................................. 错误!未定义书签。
1.4 总体框架 (2)1.5 操作函数说明 (2)二、算法设计 (3)2.1 插入排序 (3)2.2 希尔排序 (3)2.3 折半插入排序 (4)2.4 冒泡排序 (4)2.5 快速排序 (4)2.6 简单选择排序 (5)2.7 归并排序 (5)三、程序及功能说明 (6)3.1 随机数生成函数 (6)3.2 文件的存储与读取 (6)3.3 插入排序 (7)3.4 希尔排序 (8)3.5 折半插入排序 (9)3.6 冒泡排序 (9)3.7 快速排序 (10)3.8 简单选择排序 (11)3.9 归并排序 (12)3.10 退出函数 (13)3.11 菜单函数 (14)四、结果分析 (18)4.1 操作说明 (18)4.2 运行时间 (22)五、总结 (26)六、课程设计心得体会 (27)参考文献 (30)源程序 (31)文件内容 (43)一、选题背景1.1 摘要该课程设计的主要内容是：设计一个对生成的随机数进行综合排序的程序，进行九种排序算法，并计算时间复杂度，选出两种较快的方法。
九种排序算法分别是：直接插入排序、希尔排序、折半插入排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序。
将随机生成的数写入文件中，打开文件，则可通过不同的方法进行排序。
另外该程序还具备界面选择输入输出、文件读写等功能。
该程序还可以由用户自己设定随机数的个数与范围以及生成随机数文件的路径，设定每种排序算法的排序个数。
在综合排序这个功能中，还将每种排序算法所用时间写入到了指定文件中。
排序综合课程设计c语言一、教学目标本课程的学习目标包括知识目标、技能目标和情感态度价值观目标。
知识目标要求学生掌握C语言的基本语法、数据类型、运算符、控制结构、函数等；技能目标要求学生能够使用C语言编写简单的程序，解决实际问题；情感态度价值观目标要求学生培养编程兴趣，提高自主学习能力，培养团队协作和解决问题的能力。
二、教学内容根据课程目标，本章节的教学内容主要包括C语言的基本语法、数据类型、运算符、控制结构、函数等。
具体安排如下：1.第一课时：C语言概述，基本语法，数据类型和运算符。
2.第二课时：控制结构，函数的定义和调用。
3.第三课时：循环语句，数组和字符串。
4.第四课时：指针，引用，动态内存分配。
5.第五课时：结构体，共用体，枚举类型。
6.第六课时：文件操作，位运算。
7.第七课时：编程实践，解决实际问题。
三、教学方法本课程采用讲授法、讨论法、案例分析法和实验法等多种教学方法。
通过多样化教学方法，激发学生的学习兴趣和主动性。
1.讲授法：讲解C语言的基本语法、数据类型、运算符、控制结构、函数等知识，使学生掌握基础知识。
2.讨论法：学生进行小组讨论，分享学习心得，互相答疑解惑。
3.案例分析法：分析实际编程案例，让学生学会将所学知识应用于实际问题。
4.实验法：安排编程实验，让学生动手实践，提高编程能力。
四、教学资源本课程所需教学资源包括教材、参考书、多媒体资料和实验设备。
1.教材：选用权威、实用的C语言教材，如《C程序设计语言》（K&R）、《C Primer Plus》等。
2.参考书：提供丰富的参考书籍，如《C语言编程思想》、《C语言深度探索》等。
3.多媒体资料：制作精美的PPT课件，提供视频教程、在线编程练习等多媒体资源。
4.实验设备：配置计算机实验室，确保每位学生都能进行编程实践。
五、教学评估本课程的教学评估方式包括平时表现、作业、考试等。
评估方式应客观、公正，能够全面反映学生的学习成果。
课程设计课程设计名称：排序综合专业班级： 0000000000000 学生姓名： 0000000000000学号： 00000000000000 指导教师： 00000000000000 课程设计时间： 2010.6.21-2010.6.25计算机科学与技术专业课程设计任务书说明：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页信息科学与工程学院课程设计成绩评价表课程名称：数据结构课程设计1、需求分析1.1、直接插入排序思路:设有一组关键字{K1,K2,…….,Kn},排序开始变认为K1是一个有序的序列,让K2插入到表长为1的有序序列,使之成为一个表长为2的有序序列, 让K3插入到表长为2的有序序列,使之成为一个表长为3的有序序列,依次类推,最后让Kn插入上述表长为n-1的有序序列,得到一个表长为n的有序序列.1.2、希尔排序思路：先取一个正整数d1(d1<n),把全部记录分成d1个组,所有距离为d1的倍数的记录看成是一组,然后在各组内进行插入排序;然后取d2(d2<d1),重复上述分组和排序操作,直到取di=1(>=1),即所有记录成为一个组为此.一般选d1约为n/2,d2为d1/2,…….,di=11.3、快速排序:（递归和非递归）思路:以第一个关键字K1为控制字，将[K1、K2、….Kn]分成两个子区，使左区的有关键字小于等于K1，右区所有关键字大于等于K1，最后控制居两个子区中间的适当位置。
在子区内数据尚处于无序状态。
将右区首、尾指针保存入栈，对左区进行与第（1）步相类似的处理，又得到它的左子区和右子区，控制字区中。
重复第（1）、（2）步，直到左区处理完毕。
然后退栈对一个个子区进行相类似的处理，直到栈空分区处理函数hoare思路：首先用两个指针i、j分别指向首、尾两个关键字，i=1，j=8。
如对(46、56、14、43、95、10、19、72)。
第一个关键字46作为控制字，该关键字所属的记录另存储在一个x变量中。
从文件右端元素r[j].key开始与控制字x.key相比较，当r[j].key大于等于x.key时，r[j]不移动，修改指针j，j--，直到r[j].key<x.key，把记录r[j]移动到文件左边i所指向的位置;然后在文件左边修改i指针,i++，让r[i].key与x.key相比较，当r[i].key小于等于x.key 时，r[i]不移动，修改指针i，i--，直到r[i].key<x.key, 把记录r[i]移动到文件右边j所指向的位置;然后在文件右边修改j指针j--。
重复上面的步骤.1.4、堆排序思路：把n个记录存于向量r之中，把它看成完全二叉树，此时关键字序列不一定满足堆的关系。
堆排序大体分为两步处理：初建堆，从堆的定义出发，当i=1、2、。
、[2/n]时应满足ki<=k2i和ki<=k2i+1.所以先取i=[n/2](它一定是第n个结点的双亲编号),将以i结点为根的子树调整为堆，然后令i=i-1，将以不结点为根的子树调整为堆。
此时可能会反复调整某些结点，直到i=1为止，堆初步建成。
堆排序，首先输出堆顶元素（一般是最小值）,让堆中最后一个元素上移到原堆顶位置，然后恢复堆。
因为经过第一步输出堆顶元素的操作后，往往破坏了堆关系，所以要恢复堆；重复执行输出堆顶元素、堆尾元素上移和恢复堆的步骤。
2、概要设计2.1、头文件#include<stdio.h>#include<stdlib.h>#include<cstdlib>#include<time.h>2.2 、ADTstruct element{int key;}list[20];struct rnode{int key;int point;};2.3、各种操作函数：（1）创建一个数组函数：int creat()；（2）输出数组函数：void print(struct element a[20],int n)；（3）保存函数：void save(struct element a[SIZE],int n, char fileName[] )（4）直接插入排序函数：void insert_sort(element a[], int n)（5）希尔排序函数：void shell(struct element a[20],int n)；（6）快速排序函数（分区处理函数）：int hoare(struct element a[20],int l,int h)；（7）非递归的快速排序函数：void quick1(struct element a[20],int n)；（8）递归的快速排序函数：void quick2(struct element a[20],int l,int h)；（9）堆排序（调整堆的函数）：void heap(struct element a[20],int i,int m)；（10）堆排序（主体函数）：void heapsort(struct element a[20],int n)；（11）时间函数：start = clock();end = clock();2.4、主函数Void main(){接受命令（选择要执行的操作）；处理命令；输出结果；}3、详细设计3.1、程序源代码：#include<stdio.h>#include<stdlib.h>#include<cstdlib>#include<time.h>#define SIZE 1000000struct element{int key;}list[SIZE];///////创建一个数组////////int creat(){int i,n;int num;n=0;printf("请输入元素个数:");scanf("%d",&num);for( i = 0;i < num; i++ ){list[n].key = rand() % 10000;n++;}return(n);}/////////////输出数组/////////////void print(struct element a[SIZE],int n){int i;for(i=0;i<n;i++)printf("%5d",a[i ].key);printf("\n");}/////////////保存到文件/////////////void save(struct element a[SIZE],int n, char fileName[] ) {int m_wr=0; // 写入TXT文件变量FILE *fp;if ( ( fp = fopen ( fileName, "w" ) ) == NULL )printf("File writer error\n");for (int m=0; m<n; m++ ){m_wr = a[m].key;fprintf ( fp, "%d ", m_wr ); // 写入TXT中}fclose ( fp );}//////////////////// 直接插入排序///////////////////void insert_sort(element a[], int n){int i, j;element next;for(i=1; i<n; i++){next = a[i];for(j=i-1;j>=0 && next.key < a[j].key;j--)a[j+1].key=a[j].key;a[j+1]=next;}printf("输出直接插入排序的结果:\n");}/////////////////希尔排序//////////////////////void shell(struct element a[SIZE],int n){int i,j,k;for(i=n;i>=1;i--)a[i].key=a[i-1].key;k=n/2;while(k>=1){for(i=k+1;i<=n;i++){a[0].key=a[i].key;j=i-k;while((a[j].key>a[0].key)&&(j>=0)){a[j+k].key=a[j].key;j=j-k;}a[j+k]=a[0];}k=k/2;}for(i=0;i<n;i++)a[i].key=a[i+1].key;printf("输出希尔排序的结果:\n");}////////////////////快速排序///////////////////////////int hoare(struct element a[SIZE],int l,int h)//分区处理函数{int i,j;struct element x;i=l;j=h;x.key=a[i].key;do{while((i<j)&&(a[j].key>=x.key))if(i<j){a[i].key=a[j].key;i++;}while((i<j)&&(a[i].key<=x.key))i++;if(i<j){a[j].key=a[i].key;j--;}}while(i<j);a[i].key=x.key;return(i);}void quick1(struct element a[SIZE],int n) //非递归的快速排序{int i,l,h,tag,top;int s[20][2];l=0;h=n-1;tag=1;top=0;do{while(l<h){i=hoare(a,l,h);s[top][0]=i+1;s[top][1]=h;h=h-1;}if(top==0)tag=0;else{l=s[top][0];h=s[top][1];top--;}}while(tag==1);}void quick2(struct element a[SIZE],int l,int h)//递归的快速排序{int i;if(l<h){i=hoare(a,l,h); //划为两个区quick2(a,l,i-1); //对左分区快速排序quick2(a,i+1,h); //对右分区快速排序}}////////////////////堆排序函数////////////////////////////调整堆的函数void heap(struct element a[SIZE],int i,int m)/*i是根结点编号,m是以i为根的子树的最后一个结点编号*/{struct element x;int j;x.key=a[i].key; //保存记录内容j=2*i; //j 为左孩子编号while(j<=m){if(j<m)if(a[j].key>a[j+1].key) //当结点i有左,右两个孩子时,j 取关键较小的孩子编号j++;if(a[j].key<x.key) //向下一层探测{a[i].key=a[j].key;i=j;j=2*i;}elsej=m+1; //x.key小于左,右孩子的关键字时,使j>m,以便结束循环}a[i].key=x.key;}//堆排序的主体函数void heapsort(struct element a[SIZE],int n)int i,v;struct element x;for(i=n;i>0;i--)a[i].key=a[i-1].key;for(i=n/2;i>=1;i--)heap(a,i,n);for(v=n;v>=2;v--){x.key=a[1].key; //堆顶堆尾元素交换a[1].key=a[v].key;a[v].key=x.key;heap(a,1,v-1); //这次比上次少处理一个记录}for(i=0;i<n;i++)a[i].key=a[i+1].key;for(i=0;i<n/2;i++){int k;k=a[i].key;a[i].key=a[n-i-1].key;a[n-i-1].key=k;}}void main()int num,l,h,c;clock_t start, end;c=1;char file1[50] = "直接插入排序.txt";char file2[50] = "希尔排序.txt";char file3[50] = "非递归的快速排序.txt";char file4[50] = "递归的快速排序.txt";char file5[50] = "堆排序.txt";printf("***********欢迎使用本系统学习各种排序*************\n");printf("*温馨提示：首先请生成用于排序的元素，以便进行排序*\n");printf("********************主菜单************************\n");printf("* 1 生成随机排序元素*\n");printf("* 2 直接插入排序*\n");printf("* 3 希尔排序*\n");printf("* 4 非递归的快速排序*\n");printf("* 5 递归的快速排序*\n");printf("* 6 堆排序*\n");printf("* 0 退出*\n");printf("**************************************************\n");while(c!=0){printf("*请输入0-6进行操作\n");scanf("%d",&c);switch(c){case 1:num=creat();print(list,num);break;case 2:start = clock();insert_sort(list,num);end = clock();print(list,num);save(list,num, file1) ;printf("The time : %d ms\n", end - start );break;case 3:start = clock();shell(list,num);end = clock();print(list,num);save(list,num,file2) ;printf("The time : %d ms\n", end - start );break;case 4:start = clock();quick1(list,num);end = clock();print(list,num);save(list,num,file3) ;printf("The time : %d ms\n", end - start );break;case 5:l=0;h=num-1;start = clock();quick2(list,l,h);end = clock();printf("输出递归快速排序结果:\n");print(list,num);save(list,num,file4);printf("The time : %d ms\n", end - start );break;case 6:start = clock();heapsort(list,num);end = clock();print(list,num);save(list,num,file5);printf("The time : %d ms\n", end - start );break;}}}//main end4、调试分析4.1、insertion_sort排序算法分析：该算法的时间复杂度为O(n*n).直接插入排序是稳定的排序方法。
