内部排序课程设计---内部排序算法的比较.doc

长 沙 学 院课程设计说明书题目内部排序算法的比较系(部)计算机科学与技术系专业(班级)软件八班姓名张宁宁学号2011022819指导教师曾俊勇起止日期16课程设计任务书课程名称：数据结构与算法设计题目：内部排序算法的比较已知技术参数和设计要求：问题描述：通过随机数据比较各内部排序算法的关键字比较次数和关键字移动的次数，以取得直观感受。基本要求：1待排序表的表长不小于100；至少要用5组不同的输入数据作比较；排序算法不少于5种。2 待排序的元素的关键字为整数。3 比较的指标为有关键字参加的比较次数和关键字的移动次数(关键字交换以3次计)。4演示程序以人机对话的形式进行。每次测试完毕显示各种比较指标的列表，以便比较各种排序的优劣。5 最后要对结果作简单的分析。测试数据：用伪随机数产生程序产生。选作内容：对不同的表长做试验分析两个指标相对于表长变化关系。设计工作量：40课时工作计划：班级时间节次教室内容指导教师11软件8班15周周一1-4节致远楼1413布置任务曾俊勇15周周一5-8节致远楼1502上机调试15周周二1-4节I涵虚楼C3201答疑15周周二5-8节致远楼1503上机调试15周周三1-4节涵虚楼C3202答疑16周周一1-4节致远楼1413上机调试16周周一5-8节致远楼1502上机调试16周周二1-4节涵虚楼C3201答疑16周周二5-8节致远楼1503上机调试16周周三1-4节致远楼1408答辩指导教师签名：日期:教研室主任签名： 日期：系主任签名： 日期： 长沙学院课程设计鉴定表姓名张宁宁学号2011022819专业软件工程班级八班设计题目内部排序算法的比较指导教师曾俊勇指导教师意见：评定等级： 教师签名： 日期： 答辩小组意见：评定等级：答辩小组长签名：日期：教研室意见：教研室主任签名： 日期： 系（部）意见：系主任签名：日期：说明课程设计成绩分“优秀”、“良好”、“及格”、“不及格”四类；目录摘要4第一章 系统总体设计52.1 原始数据52.2 输出数据52.3 系统架构设计52.3.1 程序的主要模块52.3.2进入排序过程52.3.3程序流程6第二章 算法与数据设计73.1选择排序73.2插入排序73.3冒泡排序73.4快速排序73.5希尔排序8第三章 总结9参考文献10附录代码A11摘要本次课程设计是在数据结构基础上设计的，它的目的是帮助同学更深入的了解数据结构这门课程，使同学达到熟练掌握的程度。课程设计其中一个内容是内部排序算法的比较，它要求通过随机数据比较各内部排序算法的关键字比较次数和关键字移动的次数，以取得直观感受。并且待排序表的表长不小于100；至少要用5组不同的输入数据作比较；排序算法不少于5种；比较的指标为有关键字参加的比较次数和关键字的移动次数演示程序以人机对话的形式进行。每次测试完毕显示各种比较指标的列表，以便比较各种排序的优劣。用到的序的种类有：直接选择排序，冒泡排序，折半插入排序、快速排序、归并排序。通过这几种方法的比较：快速排序、归并排序的效率较高，但适合用于数据多的情况；插入排序的时间复杂度同于直接选择排序、冒泡排序，但它大大降低比较次数，所有它的效率高于直接选择排序，冒泡排序。 关键字：选择排序；冒泡排序；插入排序；快速排序；希尔排序 第一章 系统总体设计2.1 原始数据 用户输入关键字的个数，数据由随机序列生成器和特殊序列生成器生成 。2.2 输出数据 产生的序列分别用选择排序、插入排序、冒泡排序、快速排序、希尔排序等这些排序方法 进行排序，输出关键字的排序时间 、比较次数、移动次数。2.3 系统架构设计 2.3.1 程序的主要模块 程序的主要模块主要模块排序算法演示模块 2.3.2进入排序过程a.选择排序，根据简单选择排序的算法，输出排序时间、比较次数、移动次数b.插入排序，根据插入排序算法，输出排序时间、比较次数、移动次数c.冒泡排序，根据冒泡排序的算法，输出排序时间、比较次数、移动次数d.快速排序，根据快速排序的算法，输出排序时间、比较次数、移动次数e.希尔排序，根据归并排序的算法，输出排序时间、比较次数、移动次数2.3.3程序流程开始 结束步骤循环5次快速排序这五种排序方法各自比较次数，移动次数，运行时间希尔排序冒泡排序选择排序插入排序随机获取20000个数据第二章 算法与数据设计3.1选择排序简单选择排序的每一趟都是从待排的数据元素中选出一个最小（最大）的一个元素，顺序的放在已经排好的数列的最后，直到全部待排序的数据元素排序完毕。3.2插入排序这是一种最简单的排序方法，它的基本操作时将一个记录插入到一个已经排好序的有序表中，从而得到一个新的记录数增1的有序表。其效率：从空间的角度来看待，它只需要一个辅助的空间，从时间上来看的话，排序的基本操作是比较两个关键字的大小和移动（本程序中将移动和交换看成一样）记录。在整个排序的过程中，当待排序列中的关键字非递减有序的话，那么比较次数最小n-1，且不需要移动，当待排序列逆序时，比较次数达到最大（n+2）（n-1）/2，记录的移动的次数也达到最大值（n+4）（n-1）/2。取平均值得时候直接插入排序的时间复杂度O(n)。排序是稳定的。3.3冒泡排序这种排序的比较基本思想就是两两比较待排序的数据元素的大小，发现两个数据元素的次序相反时候，就进行交换，知道没有反序的数据为止。冒泡排序是一次的比较找出最小（最大）值，然后将其放置序列的最后一个位置，再将剩下的从第一个位置开始至n-i的位置进行重复的操作。3.4快速排序首先在r1.n中，第一趟，确定一个轴r1，并把轴上的关键字复制给r0。先从最高位开始比较,若r1=rhigh，则high；若r1rhigh,rlow=rhigh,在高位找到第一个比r1小的的值后.再从低位开始比较，若rlowr1,rhigh=rlow,在低位找到第一个比r1大的数，依次重复上叙两个比较动作，直到全部比较完成，将ri放到中间某个位置上使得r1左边所有的关键字小于r1右边所有记的关键字，并保留该位置，使得数组分成了两组。再采用递归，直至每组只有一个数据，即已排好了序。算法分析就平均速度而言，快速排序是已知内部排序方法中最好的一种排序方法，其时间复杂度为O(nlog(n)。但是，在最坏情况下（基本有序时）快速排序所需的比较次数和冒泡排序的比较次相同，其时间复杂度为O（n2）。快速排序需要一个栈作辅助空间，用来实现递归处理左、右子两组。在最坏情况下，递归深度为n，因此所需栈的空间大小为O(n)数量级。快速排序是不稳定的。3.5希尔排序属于一种插入排序类的方法，先将整个待排序记录分成若干个子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对整体记录进行一次直接插入排序。实质上就是一个将序列分块化，然后再对各个块进行排序，化整为零的操作，最后待序列差不多有序的时候进行一次化零为整操作，实现最后一次的插入排序。第三章 总结我做的课程设计是内部排序的比较，之所以选择这个题目是因为老师说这个实用性比较强。并且，对于排序我是懂的少之又少，也希望通过这次实训能够将它掌握好。这次实训的理论基础是建立在最后一段时间的学习数据结构中的内部排序算法上，通过对各个内部排序的算法的分析，比较它们所要花费的时间，移动次数、比较次数等等。确实，这次的课程设计让我对排序有了很深刻的了解。首先，几乎是一筹莫展，因为，在上理论课将排序的时候没认真听。所以，不得不把书关于排序的一字一字的仔细看，仔细理解。然后就开始编写代码。先是把各个排序的代码写出来，我所用的排序有希尔排序、快速排序、冒泡排序、插入排序、选择排序。当然，在写代码的过程中也遇到了些许问题。比如说写那个随机取数的函数的时候不知道怎么写，后来自己百度了一下，然后也询问了老师、同学最后才把它写出来。另外，我觉得还有一个难点就是计算每个排序用的时间。因为，要用到一个时间函数嘛，然后之前又没有接触过，所以，在写代码的时候，在那里就卡壳了。后来还是问了同学，老师的指点才弄明白。总的来说，觉得这次的课程设计还是偏容易的，我也有很大的收获。加强了自己的动手操作能力，也让自己学会独立思考，同时增加了自己的知识。最重要的是，对排序有了更为深刻的了解。当然，通过这次的课程设计也发现了自己很多的不足。深深地意识到了自己的操作能力还有待加强。在平时，应该多编写一些程序，同时，也应该扩大自己的知识面，多去钻研，多动脑、动手。最后，对传授自己数据结构知识的曾俊勇老师说一声谢谢！参考文献谭浩强著，C语言设计题解与上机指导，清华大学出版社，2001.3附录代码A#include #include #include #include #define MAX 20000#define SWAP(x,y) int t; t = x; x = y; y = t; / 交换函数void selsort(int,int &,int &); / 选择排序void insort(int,int &,int &);/ 插入排序void bubsort(int,int &,int &);/ 冒泡排序void quicksort(int,int,int,int &,int &);/ 快速排序int printfTime();/ 获取时间void shellsort(int ,int &,int &);/ 希尔排序int main()system(color 4f);/定义界面颜色int quicksortMoves=0,quicksortCompare=0,insortCompare=0,insortMoves=0,selsortCompare=0,selsortMoves=0,bubsortCompare=0,bubsortMoves=0,shellsortCompare=0,shellsortMoves=0;int number1MAX = 0;int number2MAX = 0;int number3MAX = 0;int number4MAX = 0;int number5MAX = 0;int i,selsortTime1,selsortTime2,insortTime1,insortTime2,bubsortTime1,bubsortTime2,quicksortTime1,quicksortTime2,mergeTime1,mergeTime2,shellsortTime1,shellsortTime2;srand(time(NULL);/使用系统定时/计数器的值做为随机种子for(i = 0; i MAX; i+)number1i = rand()%100; /0100之间的整数number2i = number1i;number3i = number1i;number4i = number1i;number5i = number1i;selsortTime1=printfTime();selsort(number1,selsortMoves,selsortCompare);selsortTime2=printfTime();insortTime1=printfTime();insort(number2,insortMoves,insortCompare);insortTime2=printfTime();bubsortTime1=printfTime();bubsort(number3,bubsortMoves,bubsortCompare);bubsortTime2=printfTime();quicksortTime1=printfTime();quicksort(number4,0, MAX-1, quicksortMoves,quicksortCompare);quicksortTime2=printfTime();shellsortTime1=printfTime();shellsort(number5,shellsortMoves,shellsortCompare);shellsortTime2=printfTime();printf(nntttt五种排序算法的比较nn);printf(nt算法名称t移动次数t比较次数t耗时（单位毫秒）nn);printf(nt选择排序t%d %d %d 毫秒nn,selsortMoves,selsortCompare,selsortTime2-selsortTime1);printf(nt插入排序t%d %d %d 毫秒nn,insortMoves,insortCompare,insortTime2-insortTime1);printf(nt冒泡排序t%d %d %d 毫秒nn,bubsortMoves,bubsortCompare,bubsortTime2-bubsortTime1);printf(nt快速排序t%d %d %d 毫秒nn,quicksortMoves,quicksortCompare,quicksortTime2-quicksortTime1);printf(nt希尔排序t%d %d %d 毫秒nn,shellsortMoves,shellsortCompare,shellsortTime2-shellsortTime1);printf(nt);return 0;/选择排序/void selsort(int number,int &selsortMoves,int &selsortCompare)/引用使得实参的值在调用函数与被调用函数都改变，有指针的作用int i, j, m,t;for(i = 0; i MAX-1; i+) m = i;for(j = i+1; j MAX; j+)if(numberj numberm)m = j;selsortCompare+;if( i != m)SWAP(numberi, numberm);selsortMoves+;/插入排序/void insort(int number,int &insortMoves,int &insortCompare)int i, j,temp,t;for(j = 1; j MAX; j+) temp = numberj;i = j - 1;while(temp numberi) numberi+1 = numberi;insortMoves+;/记录移动次数insortCompare+;/记录比较次数i-;if(i = -1)break;insortCompare+;numberi+1 = temp;/冒泡排序/void bubsort(int number,int &bubsortMoves,int &bubsortCompare)int i, j, flag = 1,t;for(i = 0 ;i MAX-1 & flag = 1; i+) flag = 0;for(j = 0; j MAX-i-1; j+) if(numberj+1 numberj) SWAP(numberj+1, numberj);bubsortMoves+;flag = 1;bubsortCompare+;/快速排序/void quicksort(int number, int left, int right,int &quicksortMoves,int &quicksortCompare)