搜索
李立强《基于C语言的多种排序方法的实现》第1页共30页1引言1.1课题背景排序问题源远流长，一直是数学地重要组成部分。随着各种信息的快速更新，排序问题也走进了其他领域以及我们地日常生活。如何高效地排序一直困扰着我们。1.2课程设计目的排序是数学的重要组成部分，工作量大是其存在的问题。如何高效地排序？本程序就是解决这个问题而设计。程序中，把数列储存在数组中，采用插入排序等十种排序方法对数组元素进行排序，高效地解决了排序问题。本软件开发的平台为最新的微软公司出版的市面最新系统Windows2000，而且可以作为自身的运行平台非常广泛，包括Windows98/2000/XP/Vista等等。1.3课程设计内容本程序把对数列的排序转化为对数组元素的排序，用户可以根据自己的实际问题选择系统提供的七种排序方法的任意一种进行排序。程序通过自身的判断以及处理实现排序。程序最后输出每趟排序及初始排序结果。2系统分析与设计方案2.1系统分析设计一个排序信息管理系统，使之能够操作实现以下功能：1)显示需要输入的排序长度及其各个关键字2)初始化输入的排序序列3)显示可供选择的操作菜单4)显示输出操作后的移动次数和比较次数5)显示操作后的新序列5)可实现循环继续操2.2设计思路通过定义C语言顺序表来存储排序元素信息，构造相关函数，对输入的元素进行相应的处理。[2]2.3设计方案设计方案如图2.1所示图2.1设计方案开始定义顺序表相关函数的声明主函数退出系统具体流程见图2.2图2.2程序流程图开始菜单插入排序冒泡排序快速排序堆排序退出排序输入数据是否继续操作结束折半插入排序简单选择排序3功能设计3.1SqList顺序表其中包括顺序表长度，以及顺序表。源代码如下：[1]typedefstruct{KeyTypekey;//关键字项InfoTypeotherinfo;//其他数据项}RedType;typedefstruct{RedTyper[MaxSize+1];//r[0]作为监视哨intlength;//顺序表长度}SqList;3.2直接插入排序直接插入排序是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表图3.1直接插入排序示意图有序序列r[1……i-1]无序系列r[i……n]r[i]有序序列r[1……i]无序系列r[i+1……n]将第i个记录的关键字r[i].key顺序地与前面记录的关键字r[i-1].key,r[i-2].key,……，r[1].key进行比较，把所有关键字大于r[i].key的记录依次后移一位，直到关键字小于或者等于r[i].key的记录r[j]，直接将r[i]插入到r[j]后面，循环以上过程直到最后一个纪录也插入到合理的位置。整个排序过程是从第2个记录开始的，视第1个记录为已经排好序的集合。3.3冒泡排序冒泡排序是对所有相邻的记录进行比较，若这两个元素刚好与排序结果逆序，则将这两个元素的位置进行交换。过程描述如下图所示：图3.2冒泡排序第一趟的前三次比较图3.3冒泡排序的第一趟比较结果13.1513.0213.2512.9212.9513.10交换13.1513.0212.9212.9513.1013.2513.2513.1513.0212.9212.9513.10交换13.1513.2513.0212.9212.9513.10交换（1）、将整个的待排序序列的记录序列划分为有序区和无序区，初始状态有序区为空，无序区包括所有待排序的记录。（2）、对无序区从前向后依次将相邻记录的数据进行比较，若两结果的大小刚好与排序结果相反，则将其交换，从而始数据值大的记录向右边移动。计较完无序区的最后两个记录，一趟冒泡排序结束。无序区最后一个记录进入有序区。（3）、重复步骤（2），直到无序区中只剩下一个记录。3.4快速排序快速排序是首先选择一个轴值，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键均小于等于轴值，另一部分记录的关键字均大于等于轴值，再分别对这两部分继续进行排序，以达到整个序列有序。过程描述路下图所示：初始关键字序列7265788604283734885ijj进行1次交换之后48657886042837385iij进行2次交换之后48657604283738885Ijj进行3次交换之后48657426083734885Ijj完成一趟排序4865742607283738885图3.4一趟快速排序过程初始状态{7265788604283734885}一次划分之后{486574260}72{83734885}分别进行快速排序{426}48{5760}{6}42结束57{60}结束{73}83{8885}结束{85}88结束有序序列{6424857607273838588}图3.5快速排序的完整过程3.5堆排序（1）、用建堆算法建立原始堆；（2）、堆尾元素与堆顶元素互换；（3）、再次调用建堆算法建堆；（4）、重复执行步骤（2）直到所有元素排好序。过程描述：假设，待排序的序列为：361553184530487293第一步，建立原始堆结构a、从第4个节点开始调整b、对第3个节点进行调整c、对第2个节点进行调整d、连续向下筛选361553184530487293361553184530487293361530184553487293153630184530487293e、原始堆图3.6建立原始堆第二步，15与93交换位置后，重新调整为堆，18为堆顶元素图3.7第二次调整图3.8第三次调整3.6折半插入排序因为R[1..i-1]是一个按关键字有序的有序序列，则可以利用折半查找实现“在R[1..i-1]中查找R[i]的插入位置”，如此实现的插入排序为折半插入排序。如同直接插151830364553487293931830364553487215183630724553489315933630724553481815303648724553931815入排序，只是确定插入的位置时，选择折半查找的方法。7、简单选择排序假设排序过程中，待排记录序列的状态为：图3.9待排序记录序列排序过程：第i简单选择排序，从无序序列中选择最小的一个元素，插入到有序序列当中去。4运行结果图3.10进行一趟简单选择排序后得序列4技术难点与分析4.1将四个子程序串成一个整体解决方法：通过编写一个主程序[4]有序序列R[1..i-1]无序序列R[i..n]有序序列R[1..i]无序序列R[i+1..n]voidmain(){inti,k;charch='y';SqList*l;l=(SqList*)malloc(sizeof(SqList));while(ch=='y'){……InsertSort(l,m,n);……BubbleSort(l,1,l-length);……子程序调用QuickSort(l,1,l-length);……HeapSort(l);……}printf(\n是否继续操作(y/n):);getchar();ch=getchar();}}对四个子程序进行调用，始之构成一个整体。4.2如何对四个子程序的比较和移动次数进行定义如果都采用整体变量，则在执行过程中会出现数据累加现象，导致计算结果出错，故在定义过程中部分采用整体变量，部分采用局部变量，以此来避免产生冲突。整体变量执行一次之后的结果如图4.1所示：图4.1采用整体变量执行一次整体变量执行二次之后的结果如图4.2所示：出现数据累加现象图4.2采用整体变量执行二次整体和局部变量并用执行两次的结果如图4.3所示，无数据累加情况图4.3整体和局部变量并用执行两次5系统测试5.1系统主界面图5.1系统主界面5.2直接插入排序测试图5.2直接插入排序测试5.3冒泡排序测试图5.3冒泡排序测试结果5.4快速选择排序测试图5.4快速选择排序测试结果5.5堆排序测试图5.5堆排序测试结果5.6折半插入排序图5.6折半插入排序测试结果5.7简单选择排序图5.7简单选择排序6结束语数据结构课程设计和现代计算机技术的实际应用相结合，是我们在本学期学完理论课程之后对自己学习能力的一次很好的检验，从开始的算法思路到运行调试后的可执行程序，都是一个很好的学习和锻炼的过程。既可以使我们巩固了原有的理论知识，培养了我们灵活运用和组合集成所学过知识及技能来分析、解决实际问题的能力，也可以使我们体会到自身知识和能力能在实际中的应用和发挥。不但可以激发创新意识，还可以开发创造能力、培养沟通能力。这次数据结构课程设计的时间里虽然时间有限，但确实使我受益非浅。通过实践课程设计我丰富了编译工具操作经验，更加深了对C语言的了解，熟悉了其环境，更增强了对排序算法的理解与运用。而且，在完成本课程设计的过程中，也充满磨练了我的意志，锻炼了我的耐心、认真。在实践的过程中，需要不断的查阅资料，甚至需要求助于老师、同学。在课程设计中要善于思考，多动手。我深知，独立完成这样一项任务需要克服许多困难。总之，数据结构课程设计让我受益良多，我会好好珍惜像这种难得的机会，努力学习知识。也感谢帮助了我的老师、同学。参考文献[1]严蔚敏，吴伟民，数据结构（C语言版）.北京：清华大学出版社，1997[2]谭浩强，C程序设计（第三版）.北京：清华大学出版社，2005[3]谭浩强，C语言程序设计题解与上机指导(第三版).北京：清华大学出版社，2005[4]JeriR.Hanly，ElliotB.Koffman，问题求解与程序设计C语言版（第四版）.北京：清华大学出版社，2007-1[5]何钦铭，颜晖，C语言设计教程.北京:高等教育出版社，2008年[6]吴文虎，程序设计基础.北京:清华大学出版社，2003附录：系统源程序代码#includestdio.h#includestdlib.h#includemalloc.h#defineMaxSize10//顺序表的最大长度typedefintKeyType;//定义关键字的类型为整数类型typedefintInfoType;//定义其他类型为整数类型intptime=0;inta=0,b=0,c=0,d=0;//置快速排序和堆排序的移动和比较次数typedefstruct{KeyTypekey;//关键字项InfoTypeotherinfo;//其他数据项}RedType;typedefstruct{RedTyper[MaxSize+1];//r[0]作为监视哨intlength;//顺序表长度}SqList;voidprint(SqList*l){inti;for(i=1;i=l-length;i++)printf(%5d,l-r[i].key);printf(\n);}//--------------------------------------------------------------------------------------------------------------------------------//直接插入排序voidInsertSort(SqList*l,intm,intn){//对数组元素r[1]到r[l-length]中的n个元素进行直接插入排序//r[0]中的内容不作为排序数据，作为一个标记又称为监视哨inti,j;for(i=2;i=l-length;i++)//n-1次循环{l-r[0]=l-r[i];//将需要插入的值r[i]赋值给]r[0],设置监视哨j=i-1;m++;while(l-r[0].keyl-r[j].key&&++n)//查找插入位置{l-r[j+1]=l-r[j];//前值覆盖后值j--;m++;}l-r[j+1]=l-r[0];//将原r[i]中的记录存入第j+1个位置printf(第%d趟排序结果为:,i-1);print(l);}printf(直接插入排序的移动次数为：%d,比较次数为：%d\n,m,n);}//---------------------------