《数据结构课程设计：快速排序》由会员分享，可在线阅读，更多相关《数据结构课程设计：快速排序（11页珍藏版）》请在金锄头文库上搜索。
1、学号武汉理工大学华夏学院课程设计课程名称数据结构题 目：用C语言实现成绩表的快速排序程序设计专 业软件工程班 级姓 名成 绩指导教师2009年6月28日至2009年7月3日课程设计任务书设计题目：用C语言实现成绩表的快速排序程序设计 设计目的1. 巩固和加深课堂所学知识、学会分析研究数据对象的特性及数据的组织方法；2. 选择合适的数据的逻辑结构和存储结构以及相应操作，实现一个班的成绩统计3. 提高程序设计能力、加强查阅、运用资料的能力、算法分析与程序设计素质培养；设计任务（在规定的时间内完成下列任务）问题描述给出n个学生的1门课程的考试成绩信息，每条信息由姓名与分数组成，要求 设计快速排序算法
2、，进行：（1）按成绩排序；（2）输出形式为：张强90张平曾芽王华孙军李应程滨888278706965基本要求学生的考试成绩必须通过键盘输入，且需对输出进行格式控制；算法提示利用快速排序算法求解；具体要完成的任务是：A. 编制完成上述问题的C语言程序、进行程序调试并能得出正确的运行结果。B. 写出规范的课程设计报告书；时间安排6月29日布置课程设计任务，查阅相关资料，确定设计课题；6月30日查阅资料、准备程序；6月307月2日上机调试程序、教师验收程序、书写课程设计报告;7月3日下午4点前提交课程设计报告及相关文档。具体要求1. 课程设计报告按统一通用格式书写，具体内容如下： 设计任务与要求 总
3、体方案与说明 软件主要模块的流程图 源程序清单与注释 问题分析与解决方案（包括调式报告，即在调式过程中遇到的主要问题、解决方法及改进设想）; 小结与体会附录：源程序（必须有简单注释） 使用说明 参考资料2. 每位学生应独立完成各自的任务且每天至少在设计室工作半天；44指 导教师签名：09年6月27日教研室主任（或责任教师）签名：09年6月28日成绩表的快速排序程序设计、实验报告实验目的1. 掌握用Turbo C上机调试常规算法的程序；2. 掌握快速排序的基本方法和过程；基本原理与方法：利用快速排序算法原理用C语言编程实现实验设备：PC机一台、配置Turbo C软件、实验内容问题描述对于用户输入
4、的数据序列，用快速排序法按从大到小或从小到大两种顺序 进行排序，并显示每一趟的排序过程；基本要求采用递归算法和非递归算法两种算法；算法实现采用快速排序原理编写C程序；基本思想通过一趟排序将待排序记录分割成独立的两个区间，其中左区间记录的关 键字的值均比右区间中记录的关键字的值小，再分别对这两个区间中的记 录进行快速排序，以达到整个序列有序为止。快速排序性质1）内部排序快速排序是一种内部排序方法。也就是说快速排序的排序对象是读入内存 的数据。2）比较排序快速排序确定元素位置的方法基于元素之间关键字大小的比较。所有基于比较方法的排序方法的时间下界不会低于O（nlgn）。这个结论的 具体证明，请参考
5、有关算法的书籍，例如算法导论（第一版）第8章（第 二版在第七章QuickSort）。3）在理想情况下，能严格地达到O（nlgn）的下界。一般情况下，快速排序 随机化快速排序的平均情况性能都达到了 O（nlgn）。4）不稳定性快速排序是一种不稳定的排序方法。简单地说，元素al, a2的关键字有 al.key=a2.key，则不稳定的排序方法不能保证a1, a2在排序后维持原 来的位置先后关系。5）原地排序在排序的具体操作过程中，除去程序运行实现的空间消费（例如递归栈）， 快速排序算法只需消耗确定数量的空间（即S（1），常数级空间）。这个性质的意义，在于在内存空间受到限制的系统（例如MCU）中，快
6、速 排序也能够很好地工作。排序过程在待排序的n各记录中任取一条记录（通常去第一条记录），把它作为基 准元素，确定该条记录的最终位置，即该条记录左边的记录的所有记录的 关键字的值均小于该记录，右边的所有记录的关键字的值均大于等于该记 录。待排序序列以基准元素为界限被分割成两个区域，这个过程称作一次 快速排序。之后对所有的区间分别重复上述过程，直至每个区间只有一条记录为止。快速排序是一个递归过程，整个排序过程中对不同的区间进行 快速排序。假设要排序的数组是A1AN，首先任意选取一个数据（通常选用 第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它 大的数都放到它后面，这个过程称为一
7、躺快速排序。一躺快速排序的算法 是：1）、设置两个变量I、J,排序开始的时候I： =1, J： =N；2）以第一个数组元素作为关键数据，赋值给X,即X： =A1；3）、从J开始向前搜索，即由后开始向前搜索J： =J-1），找到第一个小于 X的值，两者交换；4）、从I开始向后搜索，即由前开始向后搜索（I： =1+1），找到第一个大于 X的值，两者交换；5）、重复第3、4步，直到I=J；事例模范例：将数据45 53 18 36 72 30 48 93 15 36进行快速排序。图1快速排序的一次划分程45531836723048i36531836723048i36451836723048i36151
8、836723048塑15183备i45L3048塑151813630j454836151836i打3045489315翌移动比较j931545交换位置并比较j931553交换位置并比较j934553交换位置并比较j937253交换位置并比较937253交换位置，i=j937253趟排序的结果图2一次完整的快速排序的排序过程（待排序区间以中括号括起来）4553183672304893153630361836154548937253181530363645489372531518303636454893725315183036364548937253151830363645489372531518
9、303636454853729315183036364548537293参考程序ttincludest dio.httincludestdlib.h#define SIZE 35voidquick_sort(int data, int x, int y);intpation(int data, int x, int y);intmain( ) int i, dataSIZE;for(i=0; iSIZE; +i)scanf(%d, &datai);quick_sort(data, 0, SIZE-1);for(i=0; i=y) return;q=pa tio n(da ta,x,y);qui
10、ck_so rt(dat a,x,q-1);quick_so rt(dat a,q+1,y);int pation(int data, int x,int y)int n=da tax,i=x+1,j=y,t emp;while(l)while(datain)+i;while(datajn)j;if(i=j) break;temp=datai;datai=dataj;dataj=temp;datax=dataj;dataj=n;return j;算法实现流程图快速排序算法流程图输入数据w=a1调试过程1.首先打开桌面上的Win-tc.lnk软件。2.将事先写好的程序逐条输入正文中，注意英文与中
11、文符号间的区别。3. 用鼠标单击工具栏中的“编译连接”按钮。4. 若显示的消息框为“恭喜，编译成功”，则程序输入正确。若显示“编译失 败，您需要检查错误”，则根据窗口下边提示的错误依次改正，直至编译成功为止。5. 当第四步完成后，单击工具拦上的“编译连接并运行”按钮,先出现第四步 中的“恭喜，编译成功”，然后显示程序输入框(如图3)。图3程序数据输入框6 .在第四步的窗口中随意输入一组数据，查看结果。如图4图4实验结果与分析。例 1：若输入的数据序列为：56 75 65 78 45 88 76 59 66 60 85 71 44 9068 756254846535914765734985649
12、24967程序执行结申曰.果疋：35 44454749495457596062646565656667 68 71 73 7575 767884858588909192结果分析：由事例容易得出快速排序的的平均实际复杂度为0 (n bgn)但是，在2待排序的记录已经有的情况下，排序工作反而最长。快速排序递归算法需要堆栈来实现，栈中存放待排序记录序列的首尾位置，一般情况下需要栈空间o（吨n）：在最坏的情况下需要的栈空间为o（心快速排序是不稳定的。快速排序不使用于记录基本有序的场合。 例2：输入学生成绩并排序：张强 张平 曾芽王华孙军 李应 程滨90888278706965结果如图5CA H:课程设计KUAISUl.exe Ini x|105P9 6t 20 U87 Pe89S86in student1s achieuement:7870696578828890 Press any key to continue 四、课程设计体会课程设计是对我们平时学习的一种考察，我们要正确地对待。不断地锻炼自 己动手动脑的能力、把知识赋予实践就是我们学习的目标！既然学校给我们这么好的机会，让我们自己在实验室作操作，我们应该好好 抓住机会，把我们平时学习的东西用自己的作品展现出来。这
