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

学号

武汉理⼯⼤学华夏学院课程设计课程名称数据结构

题⽬:⽤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#include#define SIZE 35

void 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

scanf(\"%d\quick_sort(data, 0, SIZE-1);for(i=0; i

printf(\"%d \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]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]ii=1;j=nw

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—++——

+输⼊数据+END

5.当第四步完成后，单击⼯具拦上的“编译连接并运⾏”按钮，先出现第四步中的“恭喜，编译成功”，然后显⽰程序输⼊框（如图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

四、课程设计体会

课程设计是对我们平时学习的⼀种考察，我们要正确地对待。不断地锻炼⾃⼰动⼿动脑的能⼒、把知识赋予实践就是我们学习的⽬标！

既然学校给我们这么好的机会，让我们⾃⼰在实验室作操作，我们应该好好抓住机会，把我们平时学习的东西⽤⾃⼰的作品展现出来。这次，我做的是《学⽣成绩：快速排序》的设计，这给了我充分锻炼的机会。我会⽤⾃⼰学到的东西的设计出⼀副好的作品。

通过四天的制作，我以基本完成了⾃⼰的作品。从中我明⽩：要学好《数据结构》，⾸先要有⼀颗坚毅的⼼，有恒⼼，有信⼼，在学习过程中，坎坷是避免不了的，但千万不要灰⼼，不要⽓馁，要继续努⼒，刚开始是会感到很⽆助的，也许会产⽣放弃的念头，千万顶住，只要克服了开始的难关，以后的路才会充满阳光，充满快乐。

⽽且，在程序算法设计过程中我也遇到了很多问题。但是在⽼师和同学的帮助下，我⼀次次将难题解决。对此，我由衷地感谢那些在我制作表格过程中帮助过我的⼈。

我相信通过我以后很加刻苦的学习，我会更加热爱我的专业课程。五、问题答辩

设计过程中质疑（或答辩）记载：

问题⼀：如何将学⽣成绩的排序数进⾏增加或减少？

答：将程序中的“#define SIZE 35”中的数据“35”改写成你需要的任意数据即可，如改写成“8”。问题⼆：如何⽤递归⽅法实现快速排序？

答：（1）分割——取未排序数组中的第⼀个元素，确定它在最终排序的数组中的位置。这时数组中的所有⼩于该元素的元素都位于它的左边，所有⼤于该元

素的元素都位于它的右边。⾄此，有⼀个元素已经处于它该处的位置，另外还有两个未排序的⼦数组。

（2）递归——对每⼀个未排序的数组执⾏步骤（1）。六、教师评语指导教师评语：签名：09 年7 ⽉⽇