数据结构课程设计：快速排序.docVIP

学号 武汉理工大学华夏学院 课 程 设 计 课程名称 数据结构 题 目:用C语言实现成绩表的快速排序程序设计 专 业 软件工程 班 级 姓 名 成 绩 指导教师 2009 年6月28日至2009年7月3 日 课程设计任务书 设计题目：用C语言实现成绩表的快速排序程序设计 设计目的 1.巩固和加深课堂所学知识、学会分析研究数据对象的特性及数据的组织方法； 2.选择合适的数据的逻辑结构和存储结构以及相应操作，实现一个班的成绩统计 3. 提高程序设计能力、加强查阅、运用资料的能力、算法分析与程序设计素质培养 ； 设计任务 （在规定的时间内完成下列任务） 〔问题描述〕给出n个学生的1门课程的考试成绩信息，每条信息由姓名 与分数组成，要求设计快速排序算法，进行： （1）按成绩排序； （2）输出形式为：张强 张平 曾芽 王华 孙军 李应 程滨 90 88 82 78 70 69 65 〔基本要求〕 学生的考试成绩必须通过键盘输入，且需对输出进行格式控制； 〔算法提示〕利用快速排序算法求解； 具体要完成的任务是： A. 编制完成上述问题的C语言程序、进行程序调试并能得出正确的运行结果。 B. 写出规范的课程设计报告书； 时间安排 6月 29日 布置课程设计任务，查阅相关资料，确定设计课题； 6月 30日 查阅资料、 准备程序； 6月30～7月2日 上机调试程序、教师验收程序、书写课程设计报告； 7月3 日 下午4点前提交课程设计报告及相关文档。 具体要求 1. 课程设计报告按统一通用格式书写，具体内容如下： ① 设计任务与要求 ② 总体方案与说明 ③ 软件主要模块的流程图 ④ 源程序清单与注释 ⑤ 问题分析与解决方案（包括调式报告，即在调式过程中遇到的主要问题、解决方法及改进设想）； ⑥ 小结与体会 附录：① 源程序（必须有简单注释） ② 使用说明 ③ 参考资料 2．每位学生应独立完成各自的任务且每天至少在设计室工作半天； 指 导 教 师 签 名： 09 年 6月 27日 教研室主任（或责任教师）签名： 09 年 6月 28日 成绩表的快速排序程序设计 一、实验报告 实验目的 掌握用Turbo C 上机调试常规算法的程序； 掌握快速排序的基本方法和过程； 基本原理与方法：利用快速排序算法原理用C语言编程实现 实验设备：PC机一台、配置Turbo C软件 二、实验内容 [问题描述] 对于用户输入的数据序列，用快速排序法按从大到小或从小到大两种顺序进行排序，并显示每一趟的排序过程； [基本要求] 采用递归算法和非递归算法两种算法； [算法实现] 采用快速排序原理编写C程序； [基本思想] 通过一趟排序将待排序记录分割成独立的两个区间，其中左区间记录的关键字的值均比右区间中记录的关键字的值小，再分别对这两个区间中的记录进行快速排序，以达到整个序列有序为止。 [快速排序性质] 内部排序 　　 快速排序是一种内部排序方法。也就是说快速排序的排序对象是读入内存的数据。 比较排序 　　 快速排序确定元素位置的方法基于元素之间关键字大小的比较。 　 　所有基于比较方法的排序方法的时间下界不会低于O(nlgn)。这个结论的具体证明，请参考有关算法的书籍，例如《算法导论》（第一版）第8章（第二版在第七章QuickSort)。 在理想情况下，能严格地达到O(nlgn)的下界。一般情况下，快速排序 随机化快速排序的平均情况性能都达到了O(nlgn)。 不稳定性 　　 快速排序是一种不稳定的排序方法。简单地说，元素a1, a2的关键字有 a1.key=a2.key，则不稳定的排序方法不能保证a1, a2在排序后维持原来的位置先后关系。 原地排序 在排序的具体操作过程中，除去程序运行实现的空间消费（例如递归栈），快速排序算法只需消耗确定数量的空间（即S(1)，常数级空间）。 　　 这个性质的意义，在于在内存空间受到限制的系统（例如MCU）中，快速