排序综合-课程设计报告

《排序综合-课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、课程设计课程设计名称：排序综合专业班级：0000000000000学生姓名：0000000000000学号：00000000000000指导教师：00000000000000课程设计时间：2010.6.21-2010.6.25计算机科学与技术专业课程设计任务书学生姓名专业班级学号题目排序综合课题性质A．工程设计课题来源D．自拟课题指导教师同组姓名无主要内容综合应用所学知识，设计完成一个排序综合系统。本系统拟实现以下功能：1.直接插入排序2.希尔排序3.快速排序4.堆排序5.结果保存6.计算排序时间系统要求采用VC6.0工具进行开发实现。

2、任务要求综合运用和融化所学理论知识，提高分析和解决实际问题的能力，使用c语言设计一个排序综合系统。完成课程设计报告，报告中对关键部分给出图表说明。要求格式规范，工作量饱满。参考文献[1]数据结构.严蔚敏，吴伟民编著.清华大学出版社.2007年03月[2]数据结构、算法与应用：C++语言描术.（美）萨尼（Sahni,S.）著，汪诗林等译.机械工业出版社.2005年03月审查意见指导教师签字：教研室主任签字：2010年6月24日说明：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页信息科学与工程学院课程设计成绩评

3、价表课程名称：数据结构课程设计设计题目：排序序号评审项目分数满分标准说明1内容思路清晰；语言表达准确，概念清楚，论点正确；实验方法科学，分析归纳合理；结论严谨，设计有应用价值。任务饱满，做了大量的工作。2创新内容新颖，题目能反映新技术，对前人工作有改进或突破，或有独特见解3完整性、实用性整体构思合理，理论依据充分，设计完整，实用性强4数据准确、可靠数据准确，公式推导正确5规范性设计格式、绘图、图纸、实验数据、标准的运用等符合有关标准和规定6纪律性能很好的遵守各项纪律，设计过程认真；7答辩准备工作充分，回答问题有理论依据，基本概念清楚。主

4、要问题回答简明准确。在规定的时间内作完报告。总分综合意见指导教师年月日1、需求分析1.1、直接插入排序思路:设有一组关键字{K1,K2,…….,Kn},排序开始变认为K1是一个有序的序列,让K2插入到表长为1的有序序列,使之成为一个表长为2的有序序列,让K3插入到表长为2的有序序列,使之成为一个表长为3的有序序列,依次类推,最后让Kn插入上述表长为n-1的有序序列,得到一个表长为n的有序序列.1.2、希尔排序思路：先取一个正整数d1(d1

5、取d2(d2=1),即所有记录成为一个组为此.一般选d1约为n/2,d2为d1/2,…….,di=11.3、快速排序:（递归和非递归）思路:以第一个关键字K1为控制字，将[K1、K2、….Kn]分成两个子区，使左区的有关键字小于等于K1，右区所有关键字大于等于K1，最后控制居两个子区中间的适当位置。在子区内数据尚处于无序状态。将右区首、尾指针保存入栈，对左区进行与第（1）步相类似的处理，又得到它的左子区和右子区，控制字区中。重复第（1）、（2）步，直到左区处理完毕。然后退栈对一个个子区

6、进行相类似的处理，直到栈空分区处理函数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

7、y小于等于x.key时，r[i]不移动，修改指针i，i--，直到r[i].key

8、堆。此时可能会反复调整某些结点，直到i=1为止，堆初步建成。堆排序，首先输出堆顶元素（一般是最小值）,让堆中最后一个元素上移到原堆顶位置，然后恢复堆。因为经过第一步输出堆顶元素的操作后，往往破坏了堆关系，所