学号武汉理工大学华夏学院课程设计课程名称数据结构题目:用C语言实现成绩表的快速排序程序设计专业软件工程班级姓名成绩指导教师2009 年6月28日至2009年7月3 日课程设计任务书设计题目：用C语言实现成绩表的快速排序程序设计设计目的1.巩固和加深课堂所学知识、学会分析研究数据对象的特性及数据的组织方法；2.选择合适的数据的逻辑结构和存储结构以及相应操作，实现一个班的成绩统计3. 提高程序设计能力、加强查阅、运用资料的能力、算法分析与程序设计素质培养；设计任务（在规定的时间内完成下列任务）〔问题描述〕给出n个学生的1门课程的考试成绩信息，每条信息由姓名与分数组成，要求设计快速排序算法，进行：（1）按成绩排序；（2）输出形式为：张强张平曾芽王华孙军李应程滨90888278706965〔基本要求〕学生的考试成绩必须通过键盘输入，且需对输出进行格式控制；〔算法提示〕利用快速排序算法求解；具体要完成的任务是：A.编制完成上述问题的C语言程序、进行程序调试并能得出正确的运行结果。
B.写出规范的课程设计报告书；时间安排6月 29日布置课程设计任务，查阅相关资料，确定设计课题；6月 30日查阅资料、准备程序；6月30～7月2日上机调试程序、教师验收程序、书写课程设计报告；7月3 日下午4点前提交课程设计报告及相关文档。
具体要求1. 课程设计报告按统一通用格式书写，具体内容如下：①设计任务与要求②总体方案与说明③软件主要模块的流程图④源程序清单与注释⑤问题分析与解决方案（包括调式报告，即在调式过程中遇到的主要问题、解决方法及改进设想）；⑥小结与体会附录：①源程序（必须有简单注释）②使用说明③参考资料2．每位学生应独立完成各自的任务且每天至少在设计室工作半天；指导教师签名：09 年6月27日教研室主任（或责任教师）签名：09 年6月28日成绩表的快速排序程序设计一、实验报告实验目的1.掌握用Turbo C 上机调试常规算法的程序；2.掌握快速排序的基本方法和过程；基本原理与方法：利用快速排序算法原理用C语言编程实现实验设备：PC机一台、配置Turbo C软件二、实验内容[问题描述] 对于用户输入的数据序列，用快速排序法按从大到小或从小到大两种顺序进行排序，并显示每一趟的排序过程；[基本要求] 采用递归算法和非递归算法两种算法；[算法实现] 采用快速排序原理编写C程序；[基本思想] 通过一趟排序将待排序记录分割成独立的两个区间，其中左区间记录的关键字的值均比右区间中记录的关键字的值小，再分别对这两个区间中的记录进行快速排序，以达到整个序列有序为止。
[快速排序性质]1)内部排序快速排序是一种内部排序方法。
也就是说快速排序的排序对象是读入内存的数据。
2)比较排序快速排序确定元素位置的方法基于元素之间关键字大小的比较。
所有基于比较方法的排序方法的时间下界不会低于O(nlgn)。
这个结论的具体证明，请参考有关算法的书籍，例如《算法导论》（第一版）第8章（第二版在第七章QuickSort)。
3)在理想情况下，能严格地达到O(nlgn)的下界。
一般情况下，快速排序随机化快速排序的平均情况性能都达到了O(nlgn)。
4)不稳定性快速排序是一种不稳定的排序方法。
简单地说，元素a1, a2的关键字有a1.key=a2.key，则不稳定的排序方法不能保证a1, a2在排序后维持原来的位置先后关系。
5)原地排序在排序的具体操作过程中，除去程序运行实现的空间消费（例如递归栈），快速排序算法只需消耗确定数量的空间（即S(1)，常数级空间）。
这个性质的意义，在于在内存空间受到限制的系统（例如MCU）中，快速排序也能够很好地工作。
[排序过程] 在待排序的n各记录中任取一条记录（通常去第一条记录），把它作为基准元素，确定该条记录的最终位置，即该条记录左边的记录的所有记录的关键字的值均小于该记录，右边的所有记录的关键字的值均大于等于该记录。
待排序序列以基准元素为界限被分割成两个区域，这个过程称作一次快速排序。
之后对所有的区间分别重复上述过程，直至每个区间只有一条记录为止。
快速排序是一个递归过程，整个排序过程中对不同的区间进行快速排序。
假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。
一躺快速排序的算法是：1）、设置两个变量I、J，排序开始的时候I：=1，J：=N；2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；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 快速排序的一次划分程[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=ji j[36 15 18 36 30] 45 [48 93 72 53] 一趟排序的结果图2一次完整的快速排序的排序过程（待排序区间以中括号括起来）[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] 9315 18 30 36 36 45 48 53 72 93[参考程序]#include <stdio.h>#include <stdlib.h>#define SIZE 35void quick_sort(int data[], int x, int y);int pation(int data[], int x, int y);int main( ){ int i, data[SIZE];for(i=0; i<SIZE; ++i)scanf("%d", &data[i]);quick_sort(data, 0, SIZE-1);for(i=0; i<SIZE; ++i)printf("%d ",data[i]);system("pause");}void quick_sort(int data[],int x,int y){ int q;if(x>=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){int n=data[x],i=x+1,j=y,temp;while(1){while(data[i]<n) ++i;while(data[j]>n) --j;if(i>=j) break;temp=data[i];data[i]=data[j];data[j]=temp; }data[x]=data[j];data[j]=n;return j;}[算法实现流程图]快速排序算法流程图[调试过程]1. 首先打开桌面上的软件。
2.将事先写好的程序逐条输入正文中，注意英文与中文符号间的区别。
3.用鼠标单击工具栏中的“编译连接”按钮。
4. 若显示的消息框为“恭喜，编译成功”，则程序输入正确。
若显示“编译失败，您需要检查错误”，则根据窗口下边提示的错误依次改正，直至编译成功为止。
w=a[1]i<ji=1;j=nw<a[j]a[i]=w a[i]=a[j]i=i+1 w>a[i] i=i+1 a[j]=a[i] j=j-1j=j-1—++——+输入数据+END5.当第四步完成后，单击工具拦上的“编译连接并运行”按钮，先出现第四步中的“恭喜，编译成功”，然后显示程序输入框（如图3）。
图3程序数据输入框6．在第四步的窗口中随意输入一组数据，查看结果。
如图 4图4三、实验结果与分析。
例1：若输入的数据序列为：56 75 65 78 45 88 76 59 66 60 85 71 449068 75 62 54 84 65 35 91 47 65 73 49 85 64 92 49 67程序执行结果是：35 44 45 47 49 49 54 57 59 60 62 64 65 65 65 66 67 68 71 73 7575 76 78 84 85 85 88 90 91 92）。
但是，在结果分析：由事例容易得出快速排序的的平均实际复杂度为O（n㏒n2待排序的记录已经有的情况下，排序工作反而最长。
快速排序递归算法需要堆栈来实现，栈中存放待排序记录序列的首尾位置，一般情况下需要栈空间O（㏒n）：在最坏的情况下，需要的栈空间为O（n）。
快速排2序是不稳定的。
快速排序不使用于记录基本有序的场合。
例2：输入学生成绩并排序：张强张平曾芽王华孙军李应程滨90 88 82 78 70 69 65结果如图5图5四、课程设计体会课程设计是对我们平时学习的一种考察，我们要正确地对待。
不断地锻炼自己动手动脑的能力、把知识赋予实践就是我们学习的目标！既然学校给我们这么好的机会，让我们自己在实验室作操作，我们应该好好抓住机会，把我们平时学习的东西用自己的作品展现出来。
这次，我做的是《学生成绩：快速排序》的设计，这给了我充分锻炼的机会。
我会用自己学到的东西的设计出一副好的作品。
通过四天的制作，我以基本完成了自己的作品。
从中我明白：要学好《数据结构》，首先要有一颗坚毅的心，有恒心，有信心，在学习过程中，坎坷是避免不了的，但千万不要灰心，不要气馁，要继续努力，刚开始是会感到很无助的，也许会产生放弃的念头，千万顶住，只要克服了开始的难关，以后的路才会充满阳光，充满快乐。