基于C语言的多种排序方法的实现.doc

基于c语言的多种排序方法的实现1 引 言1.1 课题背景排序问题源远流长，一直是数学地重要组成部分。随着各种信息的快速更新，排序问题也走进了其他领域以及我们地日常生活。如何高效地排序一直困扰着我们。1.2 课程设计目的排序是数学的重要组成部分，工作量大是其存在的问题。如何高效地排序？本程序就是解决这个问题而设计。程序中，把数列储存在数组中，采用插入排序等十种排序方法对数组元素进行排序，高效地解决了排序问题。本软件开发的平台为最新的微软公司出版的市面最新系统windows 2000，而且可以作为自身的运行平台非常广泛，包括 windows 98/2000/xp/vista等等。1.3课程设计内容本程序把对数列的排序转化为对数组元素的排序，用户可以根据自己的实际问题选择系统提供的七种排序方法的任意一种进行排序。程序通过自身的判断以及处理实现排序。程序最后输出每趟排序及初始排序结果。 2 系统分析与设计方案 2.1 系统分析 设计一个排序信息管理系统，使之能够操作实现以下功能：1) 显示需要输入的排序长度及其各个关键字2) 初始化输入的排序序列3) 显示可供选择的操作菜单4) 显示输出操作后的移动次数和比较次数5) 显示操作后的新序列5) 可实现循环继续操2.2 设计思路通过定义c语言顺序表来存储排序元素信息，构造相关函数，对输入的元素进行相应的处理。 22.3 设计方案设计方案如图2.1所示开始定义顺序表相关函数的声明主函数退出系统图2.1 设计方案具体流程见图2.2开始菜单插入排序冒泡排序快速排序堆排序是否继续操作结束退出排序折半插入排序简单选择排序 输入数据图2.2 程序流程图3功能设计3.1 sqlist顺序表其中包括顺序表长度，以及顺序表。源代码如下：1typedef struct keytype key; /关键字项 infotype otherinfo; /其他数据项redtype;typedef struct redtype rmaxsize+1; /r0作为监视哨int length; /顺序表长度sqlist;3.2 直接插入排序 直接插入排序是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表有序序列r1i-1无序系列rinri有序序列r1i 无序系列ri+1n 图3.1 直接插入排序示意图将第i个记录的关键字ri.key顺序地与前面记录的关键字ri-1.key,ri-2.key,，r1.key进行比较，把所有关键字大于ri.key的记录依次后移一位，直到关键字小于或者等于ri.key的记录rj，直接将ri插入到rj后面，循环以上过程直到最后一个纪录也插入到合理的位置。整个排序过程是从第2个记录开始的，视第1个记录为已经排好序的集合。3.3 冒泡排序 13.25 13.15 13.02 12.92 12.95 13.10交换 冒泡排序是对所有相邻的记录进行比较，若这两个元素刚好与排序结果逆序，则将这两个元素的位置进行交换。 过程描述如下图所示： 13.15 13.25 13.02 12.92 12.95 13.10交换交换 13.15 13.02 13.25 12.92 12.95 13.10图3.2 冒泡排序第一趟的前三次比较 13.15 13.02 12.92 12.95 13.10 13.25图3.3 冒泡排序的第一趟比较结果（1）、将整个的待排序序列的记录序列划分为有序区和无序区，初始状态有序区为空，无序区包括所有待排序的记录。（2）、对无序区从前向后依次将相邻记录的数据进行比较，若两结果的大小刚好与排序结果相反，则将其交换，从而始数据值大的记录向右边移动。计较完无序区的最后两个记录，一趟冒泡排序结束。无序区最后一个记录进入有序区。（3）、重复步骤（2），直到无序区中只剩下一个记录。3.4 快速排序快速排序是首先选择一个轴值，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键均小于等于轴值，另一部分记录的关键字均大于等于轴值，再分别对这两部分继续进行排序，以达到整个序列有序。 过程描述路下图所示：初始关键字序列 72 6 57 88 60 42 83 73 48 85 i j j 进行1次交换之后 48 6 57 88 60 42 83 73 85 i i j进行2次交换之后 48 6 57 60 42 83 73 88 85 i j j进行3次交换之后 48 6 57 42 60 83 73 48 85 i j j完成一趟排序 48 6 57 42 60 72 83 73 88 85图3.4 一趟快速排序过程初始状态 72 6 57 88 60 42 83 73 48 85一次划分之后 48 6 57 42 60 72 83 73 48 85分别进行快速排序 42 6 48 57 60 6 42 结束 57 60 结束 73 83 88 85 结束 85 88 结束有序序列 6 42 48 57 60 72 73 83 85 88图3.5 快速排序的完整过程3.5 堆排序 （1）、用建堆算法建立原始堆；（2）、堆尾元素与堆顶元素互换；（3）、再次调用建堆算法建堆；（4）、重复执行步骤（2）直到所有元素排好序。过程描述：假设，待排序的序列为：36 15 53 18 45 30 48 72 93第一步，建立原始堆结构361553184530487293361553184530487293 a、从第4个节点开始调整 b、对第3个节点进行调整153630184530487293361530184553487293 c、对第2个节点进行调整 d、连续向下筛选151830364553487293e、原始堆 图3.6 建立原始堆第二步，15与93交换位置后，重新调整为堆，18为堆顶元素18931830364553487215363072455348931530 93图3.7 第二次调整36483036539345724572485315181815图3.8 第三次调整3.6 折半插入排序因为 r1.i-1 是一个按关键字有序的有序序列，则可以利用折半查找实现“在r1.i-1中查找ri的插入位置”，如此实现的插入排序为折半插入排序。如同直接插入排序，只是确定插入的位置时，选择折半查找的方法。7、简单选择排序假设排序过程中，待排记录序列的状态为：无序序列 ri.n有序序列r1.i-1 图3.9 待排序记录序列排序过程：第i简单选择排序，从无序序列中选择最小的一个元素，插入到有序序列当中去。有序序列r1.i无序序列 ri+1.n4 运行结果 图3.10 进行一趟简单选择排序后得序列4 技术难点与分析4.1 将四个子程序串成一个整体 解决方法：通过编写一个主程序 4void main()int i,k;char ch=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程序设计（第三版）.北京：清华大学出版社，20053 谭浩强，c语言程序设计题解与上机指导(第三版).北京：清华大学出版社，20054 jeri r.hanly，elliot b. koffman，问题求解与程序设计c语言版（第四版）.北京：清华大学出版社，2007-15 何钦铭，颜晖，c语言设计教程.北京:高等教育出版社，2008年6 吴文虎，程序设计基础.北京:清华大学出版社，2003附 录 ：系统源程序代码#include#include#include#define maxsize 10 /顺序表的最大长度typedef int keytype; /定义关键字的类型为整数类型typedef int infotype; /定义其他类型为整数类型int ptime=0;int a=0,b=0,c=0,d=0; /置快速排序和堆排序的移动和比较次数typedef struct keytype key; /关键字项 infotype otherinfo; /其他数据项redtype;typedef struct redtype rmaxsize+1; /r0作为监视哨int length; /顺序表长度sqlist; void print(sqlist *l)int i;for(i=1;ilength;i+)printf(%5d,l-ri.key);printf(n);/-/直接插入排序void insertsort(sqlist *l,int m,int n)/对数组元素r1到rl-length中的n个元素进行直接插入排序 /r0中的内容不作为排序数据，作为一个标记又称为监视哨int i,j;for(i=2;ilength;i+) /n-1次循环l-r0=l-ri; /将需要插入的值ri赋值给r0,设置监视哨j=i-1;m+;while(l-r0.keyrj.key&+n) /查找插入位置l-rj+1=l-rj; /前值覆盖后值j-;m+;l-rj+1=l-r0; /将原ri中的记录存入第j+1个位置printf(第%d趟排序结果为:,i-1); print(l);printf(直接插入排序的移动次数为：%d,比较次数为：%dn,m,n);/-/冒泡排序void bubblesort(sqlist *l,int m,int n)int i,j,k=0; redtype temp;for(i=l-length;i1;i-) /n-1趟比较for(j=1;jrj.keyl-rj+1.key&+n)temp=l-rj; /交换数据l-rj=l-rj+1;l-rj+1=temp;m=m+3;k+;printf(第%d趟排序结果为:,k); print(l);printf(冒泡排序的移动次数为：%d,比较次数为：%dn,m,n);/-/快速排序void quicksort (sqlist *l, int left,int right) int i,j,temp; i=left;j=right;temp=l-ri.key;/设置初始的排序区 /将i和j分别记录待排序区域的最左侧记录和最右侧记录的位置 while(ij) while (ij&temprj.key) /从右侧开始扫描 j-; b+; /找到第一个小于基准记录的数据 l-ri=l-rj;/覆盖l-ri a+; while (iri.keyrj=l-ri; /覆盖l-rja+; l-ri.key=temp;/找到正确位置 a+; ptime+; printf(第%d次划分排序为:,ptime); print(l); if (lefti-1) quicksort(l,left,i-1); /递归调用对左侧分区域再进行快速排序 if (i+1rx的关键字使l-rx.y成为一个大堆void heapadjust(sqlist *l, int x,int y)int j;l-r0=l-rx ;for(j=2*x;j=y;j=j*2)if(jrj.keyrj+1.key)+j;/j为key值较大的记录下标 d+;if(l-r0.keyl-rj.key)d+;break;l-rx=l-rj;c+;x=j;l-rx=l-r0;c+;/对顺序表l进行堆排序void heapsort(sqlist *l)int i,j;for(i=l-length/2;i=0;-i) /将l-r1.i建成初始堆heapadjust(l,i,l-length);printf(初始序列建成堆：);print(l);for(j=l-length;j1;-j) /对当前l-r1.i进行堆排序，共做n-1趟l-r0=l-rj;l-rj=l-r1;l-r1=l-r0;c=c+3;heapadjust(l,1,j-1);printf(第%d趟建堆结果为:,l-length-j+1);print(l); void binsort (sqlist *l, int length)/*对记录数组r进行折半插入排序，length为数组的长度*/int i,j;redtype x;int low,high,mid;for ( i=2; i ri;low=1; high=i-1;while (low=high ) /* 确定插入位置*/ mid=(low+high) / 2;if ( x.key rmid.key ) high=mid-1;else low=mid+1;for ( j=i-1 ; j= low; -j ) l-rj+1= l-rj; /* 记录依次向后移动 */ l-rlow=x; /* 插入记录 */ printf(第%d趟排序结果为:,i-1); print(l);/*binsort*/void selectsort(sqlist *l, int length)/*对记录数组r做简单选择排序，length为数组的长度*/int i,j,k;int n;redtype x; n=length;for ( i=1 ; i= n-1; +i) k=i;for ( j=i+1 ; jrj.key rk.key ) k=j;if ( k!=i) x= l-ri; l-ri= l-rk;l-rk=x;printf(第%d趟排序结果为:,i); print(l); /* selectsort */ void main()int i,k;char ch=y;sqlist *l; l=(sqlist *)malloc(sizeof(sqlist );while(ch=y)int m=0,n=0; /置直接插入排序和冒泡排序的移动和比较次数printf(nnn); printf(ttn);printf(tt#*#*#*#*欢迎进入排序管理系统*#*#*#*#n);printf(ttn);printf(nnn);printf(如果碰到意外结束的情况或者排序不正确的情况，请及时联系管理员李立强、nn);printf(本系统为免费系统，如带来任何问题，自己负责、nn);printf(tt欢迎使用排序管理系统n); printf(tt 请选择所需功能: n);printf(tt 1.直接插入排序 n);printf(tt 2.冒泡排序 n);printf(tt 3.快速排序 n);printf(tt 4.堆排序 n);printf(tt 5.折半插入排序 n);printf(tt 6.简单选择排序 n);printf(tt 7.退出系统 n);printf(tt欢迎使用排序管理系统n);printf(nnn);printf(请选择：);scanf(%d,&k);switch (k)case 1:printf(n您选择的是直接插入排序：n); printf(输入要排序列表的长度n：); scanf(%d,&l-length); for(i=1;ilength;i+) printf(输入第%d个记录的关键字：,i); scanf(%d,&l-ri.key); printf(初始输入序列为：); print(l); insertsort(l,m,n); printf(直接插入排序后记录为:); print(l); break;case 2:printf(n您选择的是冒泡排序：n); printf(输入要排序列表的长度n：); scanf(%d,&l-length); for(i=1;ilength;i+) printf(输入第%d个记录的关键字：,i); scanf(%d,&l-ri.key); printf(初始输入序列为：); print(l); bubblesort(l,1,l-length); printf(冒泡排序后记录为：); print(l); break; case 3:printf(n您选择的是快速排序：n); printf(输入要排序列表的长度n：); scanf(%d,&l-length); for(i=1;ilength;i+) printf(输入第%d个记录的关键字：,i); scanf(%d,&l-ri.key); printf(初始输入序列为：); print(l); quicksort(l,1,l-length); printf(快速排序的移动次数为：%d,比较次数为：%dn,a,b); printf(快速排序后记录为:); print(l); break; case 4:printf(n您选择的是堆排序：n); printf(输入要排序列表的长度n：); scanf(%d,&l-length); for(i=1;ilength;i+) printf(输入第%d个记录的关键字：,i); scanf(%d,&l-ri.key); printf(初始输入序列为：); print(l); heapsort(l); printf(堆排序的移动次数为：%d,比较次数为：%dn,c,d); printf(堆排序后记录为：); print(l); break; case 5:printf(n您选择的是折半插入排序：n); printf(输入要排序列表的长度n：); scanf(%d,&l-length); for(i=1;ilength;i+) printf(输入第%d个记录的关键字：,i); scanf(%d,&l-ri.key); printf(初始输入序列为：); print(l); binsort (l,l-length); printf(快速排序后记录为:); print(l); break; case 6:printf(n您选择的是简单选择排序：n); printf(输入要排序列表的长度n：); scanf(%d,&l-length); for(i=1;ilength;i+) printf(输入第%d个记录的关键字：,i); scanf(%d,&l-ri.key); printf(初始输入序列为：); print(l); selectsort(l, l-length); printf(快速排序后记录为:); print(l); break; case 7:break;default:printf(没有找到你需要的排序方法); break;printf(n是否继续操作(y/n):);getchar();ch=getchar(); 致 谢时间飞逝，大学的学习生活很快就要过去，在这四年的学习生活中，收获了很多，而这些成绩的取得是和一直关心帮助我的人分不开的。首先非常感谢学校开设这个课题，为本人日后从事计算机方面的工作提供了经验，奠定了基础。本次毕业设计大概持续了半年，现在终于到结尾了。本次毕业设计是对我大学四年学习下来最好的检验。经过这