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

《数据结构课程设计：快速排序.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计：快速排序.doc（10页珍藏版）》请在三一文库上搜索。

1、学号 武汉理工大学华夏学院 课 程 设 计 课程名称 数据结构 题 目:用C语言实现成绩表的快速排序程序设计 专 业 软件工程 班 级 姓 名 成 绩 指导教师 2009 年6月28日至2009年7月3 日 课程设计任务书设计题目：用C语言实现成绩表的快速排序程序设计设计目的1.巩固和加深课堂所学知识、学会分析研究数据对象的特性及数据的组织方法；2.选择合适的数据的逻辑结构和存储结构以及相应操作，实现一个班的成绩统计3. 提高程序设计能力、加强查阅、运用资料的能力、算法分析与程序设计素质培养 ；设计任务 （在规定的时间内完成下列任务）问题描述给出n个学生的1门课程的考试成绩信息，每条信息由姓名

2、 与分数组成，要求设计快速排序算法，进行：（1）按成绩排序；（2）输出形式为：张强 张平 曾芽 王华 孙军 李应 程滨 90 88 82 78 70 69 65基本要求 学生的考试成绩必须通过键盘输入，且需对输出进行格式控制；算法提示利用快速排序算法求解； 具体要完成的任务是： A. 编制完成上述问题的C语言程序、进行程序调试并能得出正确的运行结果。 B. 写出规范的课程设计报告书；时间安排 6月 29日 布置课程设计任务，查阅相关资料，确定设计课题；6月 30日 查阅资料、 准备程序； 6月307月2日 上机调试程序、教师验收程序、书写课程设计报告； 7月3 日 下午4点前提交课程设计报告及

3、相关文档。具体要求1. 课程设计报告按统一通用格式书写，具体内容如下： 设计任务与要求 总体方案与说明 软件主要模块的流程图 源程序清单与注释 问题分析与解决方案（包括调式报告，即在调式过程中遇到的主要问题、解决方法及改进设想）； 小结与体会附录： 源程序（必须有简单注释） 使用说明 参考资料2每位学生应独立完成各自的任务且每天至少在设计室工作半天；指 导 教 师 签 名： 09 年 6月 27日教研室主任（或责任教师）签名： 09 年 6月 28日 成绩表的快速排序程序设计一、实验报告实验目的1. 掌握用Turbo C 上机调试常规算法的程序；2. 掌握快速排序的基本方法和过程；基本原理与方

4、法：利用快速排序算法原理用C语言编程实现实验设备：PC机一台、配置Turbo C软件二、实验内容问题描述 对于用户输入的数据序列，用快速排序法按从大到小或从小到大两种顺序进行排序，并显示每一趟的排序过程；基本要求 采用递归算法和非递归算法两种算法；算法实现 采用快速排序原理编写C程序；基本思想 通过一趟排序将待排序记录分割成独立的两个区间，其中左区间记录的关键字的值均比右区间中记录的关键字的值小，再分别对这两个区间中的记录进行快速排序，以达到整个序列有序为止。快速排序性质 1) 内部排序 快速排序是一种内部排序方法。也就是说快速排序的排序对象是读入内存的数据。2) 比较排序 快速排序确定元素位

5、置的方法基于元素之间关键字大小的比较。 所有基于比较方法的排序方法的时间下界不会低于O(nlgn)。这个结论的具体证明，请参考有关算法的书籍，例如算法导论（第一版）第8章（第二版在第七章QuickSort)。3) 在理想情况下，能严格地达到O(nlgn)的下界。一般情况下，快速排序 随机化快速排序的平均情况性能都达到了O(nlgn)。4) 不稳定性 快速排序是一种不稳定的排序方法。简单地说，元素a1, a2的关键字有a1.key=a2.key，则不稳定的排序方法不能保证a1, a2在排序后维持原来的位置先后关系。5) 原地排序在排序的具体操作过程中，除去程序运行实现的空间消费（例如递归栈），快

6、速排序算法只需消耗确定数量的空间（即S(1)，常数级空间）。 这个性质的意义，在于在内存空间受到限制的系统（例如MCU）中，快速排序也能够很好地工作。排序过程 在待排序的n各记录中任取一条记录（通常去第一条记录），把它作为基准元素，确定该条记录的最终位置，即该条记录左边的记录的所有记录的关键字的值均小于该记录，右边的所有记录的关键字的值均大于等于该记录。待排序序列以基准元素为界限被分割成两个区域，这个过程称作一次快速排序。之后对所有的区间分别重复上述过程，直至每个区间只有一条 记录为止。快速排序是一个递归过程，整个排序过程中对不同的区间进行 快速排序。 假设要排序的数组是A1AN，首先任意选取

7、一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是： 1）、设置两个变量I、J，排序开始的时候I：=1，J：=N； 2）以第一个数组元素作为关键数据，赋值给X，即X：=A1； 3）、从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换； 4）、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换； 5）、重复第3、4步，直到I=J； 事例模范 例：将数据45 53 18 36 72 30 48 93 15 36进行快速排序。 图1

8、快速排序的一次划分程 45 53 18 36 72 30 48 93 15 36 移动比较i j 36 53 18 36 72 30 48 93 15 45 交换位置并比较 i j 36 45 18 36 72 30 48 93 15 53 交换位置并比较 i j 36 15 18 36 72 30 48 93 45 53 交换位置并比较 i j 36 15 18 36 45 30 48 93 72 53 交换位置并比较 i j 36 15 18 36 30 45 48 93 72 53 交换位置，i=j i j 36 15 18 36 30 45 48 93 72 53 一趟排序的结果 图2

9、一次完整的快速排序的排序过程（待排序区间以中括号括起来） 45 53 18 36 72 30 48 93 15 36 30 36 18 36 15 45 48 93 72 53 18 15 30 36 36 45 48 93 72 53 15 18 30 36 36 45 48 93 72 53 15 18 30 36 36 45 48 93 72 53 15 18 30 36 36 45 48 93 72 53 15 18 30 36 36 45 48 53 72 93 15 18 30 36 36 45 48 53 72 93 参考程序#include #include #define S

10、IZE 35void quick_sort(int data, int x, int y);int pation(int data, int x, int y);int main( ) int i, dataSIZE; for(i=0; iSIZE; +i) scanf(%d, &datai); quick_sort(data, 0, SIZE-1); for(i=0; i=y) return; q=pation(data,x,y); quick_sort(data,x,q-1); quick_sort(data,q+1,y); int pation(int data,int x,int y)

11、 int n=datax,i=x+1,j=y,temp; while(1) while(datain) -j; if(i=j) break; temp=datai;datai=dataj;dataj=temp; datax=dataj; dataj=n; return j; 算法实现流程图 快速排序算法流程图w=a1 ij i=1;j=nwaii=i+1aj=ai j=j-1j=j-1+输入数据+END 调试过程 1. 首先打开桌面上的软件。2. 将事先写好的程序逐条输入正文中，注意英文与中文符号间的区别。3. 用鼠标单击工具栏中的“编译连接”按钮。4. 若显示的消息框为“恭喜，编译成功”，则

12、程序输入正确。若显示“编译失败，您需要检查错误”，则根据窗口下边提示的错误依次改正，直至编译成功为止。 5. 当第四步完成后，单击工具拦上的“编译连接并运行”按钮，先出现第四步中的“恭喜，编译成功”，然后显示程序输入框（如图3）。 图3程序数据输入框 6在第四步的窗口中随意输入一组数据，查看结果。如图4 图4三、实验结果与分析。例1：若输入的数据序列为：56 75 65 78 45 88 76 59 66 60 85 71 44 90 68 75 62 54 84 65 35 91 47 65 73 49 85 64 92 49 67程序执行结果是：35 44 45 47 49 49 54 5

13、7 59 60 62 64 65 65 65 66 67 68 71 73 75 75 76 78 84 85 85 88 90 91 92 结果分析：由事例容易得出快速排序的的平均实际复杂度为O（n）。但是，在待排序的记录已经有的情况下，排序工作反而最长。快速排序递归算法需要堆栈来实现，栈中存放待排序记录序列的首尾位置，一般情况下需要栈空间O（）：在最坏的情况下，需要的栈空间为O（n）。快速排序是不稳定的。快速排序不使用于记录基本有序的场合。 例2：输入学生成绩并排序： 张强 张平 曾芽 王华 孙军 李应 程滨 90 88 82 78 70 69 65 结果如图5 图5四、课程设计体会 课程

14、设计是对我们平时学习的一种考察，我们要正确地对待。不断地锻炼自己动手动脑的能力、把知识赋予实践就是我们学习的目标！ 既然学校给我们这么好的机会，让我们自己在实验室作操作，我们应该好好抓住机会，把我们平时学习的东西用自己的作品展现出来。这次，我做的是学生成绩：快速排序的设计，这给了我充分锻炼的机会。我会用自己学到的东西的设计出一副好的作品。 通过四天的制作，我以基本完成了自己的作品。从中我明白：要学好数据结构，首先要有一颗坚毅的心，有恒心，有信心，在学习过程中，坎坷是避免不了的，但千万不要灰心，不要气馁，要继续努力，刚开始是会感到很无助的，也许会产生放弃的念头，千万顶住，只要克服了开始的难关，以

15、后的路才会充满阳光，充满快乐。 而且，在程序算法设计过程中我也遇到了很多问题。但是在老师和同学的帮助下，我一次次将难题解决。对此，我由衷地感谢那些在我制作表格过程中帮助过我的人。 我相信通过我以后很加刻苦的学习，我会更加热爱我的专业课程。五、问题答辩设计过程中质疑（或答辩）记载： 问题一：如何将学生成绩的排序数进行增加或减少？答：将程序中的“#define SIZE 35”中的数据“35”改写成你需要的任意数据即可，如改写成“8”。 问题二：如何用递归方法实现快速排序？ 答：（1）分割取未排序数组中的第一个元素，确定它在最终排序的数组中的位置。这时数组中的所有小于该元素的元素都位于它的左边，所有大于该元素的元素都位于它的右边。至此，有一个元素已经处于它该处的位置，另外还有两个未排序的子数组。 （2）递归对每一个未排序的数组执行步骤（1）。 六、教师评语指导教师评语： 签名： 09 年 7 月 日10