排序算法与性能分析

目录TOC\o"1-3"\h\z摘要 1前言 2正文 31. 采用类c语言定义相关的数据类型 32. 各模块的伪码算法 33. 函数的调用关系图 74. 调试分析 75. 测试结果 86. 源程序〔带注释〕 11总结 20参考文献 21致谢 22附件Ⅰ局部源程序代码 23摘要计算机的日益开展，其应用早已不局限于简单的数值运算，而涉及到问题的分析、数据结构框架的设计以及插入、删除、排序、查找等复杂的非数值处理和操作。算法与数据结构的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论、方法和技术根底。算法与数据结构旨在分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算法到达最优。数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由哪些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。《算法与数据结构》主要介绍一些最常用的数据结构及根本算法设计，说明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程。它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要根底，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和计算机编程技能，找出自己的缺乏，在以后的学习中更加努力！本次的课程设计主要是对《算法与数据结构》的所有内部排序算法进行了一个汇总、集合，并通过算法设计实现对其性能的分析和评价。在设计过程中重温了C语言中的根本语法以及个别函数的用法，稳固了设计思维方向。关键词：排序算法；性能分析；排序算法性能分析；C语言前言排序是计算机程序设计中的一种重要操作。它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。内部排序的方法很多，但是就其全面性能而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点，适合在不同的环境下使用。如果按排序过程中依据的不同原那么对内部排序方法进行分类，那么大致可分为插入排序，冒泡排序，快速排序，归并排序、选择排序、堆排序等。本课程实现了对应用于随机、正序、逆序等数据录入方式，针对各内部排序的算法，并分析算法的复杂程度，记录排序过程中的比拟次数和移动次数；另通过动画形象表现出了各排序算法的排序过程，使人一目了然。正文采用类c语言定义相关的数据类型#defineN1000//定义数组最大为100constintt=3;//定义希尔排序次数intd[3]={4,3,1};//定义希尔排序比拟量intm;intqmt;//快速排序的移动次数intqct;//快速排序的比拟次数printf("%d\t",)各模块的伪码算法(1)直接插入排序InsertSort(RecordnodeR[],intn){for(i=2;<=n;++i)if(R[i]<R[i-1])//如果待插表中最后一个小，那么将其插入表中{R[0]=R[i];for(j=i-1;R[0]<R[j];--j)R[j+1]=R[j];//记录后移R[j+1]=R[0];//插入到正确位置}}(2)折半插入排序BinsertSort(RecordnodeR[],intn){for(i=2;<=n;++i){R[0]=R[i];low=1;high=i-1;while(low<=high){m=(low+hige)/2if(R[0]<R[m].key)high=m-1;//插入点在前半区elselow=m+1;//插入点在后半区}for(j=i-1;j>=high+1;--j)R[j+1]=R[j];R[high+1]=R[0];}}(3)希尔排序ShellSort(RecordnodeR[],intn){//用希尔排序法对一个记录r[]排序inti,j,d;intbool;intx;d=n;do{d=[d/2];bool=1for(i=1;i<=L.length-d;i++){j=i+dif(R[i]>R[j]){x=R[i];R[i]=R[j];R[j]=xbool=0}}while(d>1)}}(4)冒泡排序voidBubbleSort(SeqListR){ //R(1…n)是待排序的文件，采用自上向下扫描，对R做冒泡排序 inti,j; Booleanexchange;//交换标志 for(i=1;i<n;i++) {//最多做n-1趟排序exchange=FALSE;//本趟排序开始前，交换标志应为假for(j=n-1;j<=i;j--)//对当前无序区R[i…n]自下向上扫描if(R[j+1].key<R[j].key)//交换记录 { R[0]=R[j+1];//R[0]不是哨兵，仅做暂存单元 R[j+1]=R[j]; R[j]=R[0]; exchange=TRUE;//发生了交换，故将交换标志置为真 } if(!exchange)//本趟排序未发生交换，提前终止算法 return; } } (5)快速排序 voidQuickSort(SeqListR,intlow,inthigh){//对R[low…high]快速排序 intpivotpos;//划分后的基准记录的位置 if(low<high) {//仅当区间长度大于1时才须排序 pivotpos=Partition(R,low,high);//对R[low…high]做划分 QuickSort(R,low,pivotpos-1);//对做区间递归排序 QuickSort(R,pivotpos+1,high);//对右区间递归排序 }}//QuickSortintPartition(SeqListR,inti,intj){//调用Partition(R,low.high)时，对R[low…high]做划分，返回基准记录的位置ReceTypepivot=R[i];//用区间的第1个记录作为基准while(i<j){//从区间两端交替向中间扫描，直至i=j为止 while(i<j&&R[j].key>=pivot.key)//pivot相当于在位置i上 j--;//从右向左扫描，查找第1个关键字小于pivot.key的记录R[j] if(i<j)//表示找到的R[j]的关键字<pivot.key R[i++]=R[j];//相当于交换R[i]和R[j]，交换后i指针加1 while(i<j&&R[i].key<=pivot.key)//pivot相当于在位置j上 i++;//从左向右扫描，查找第1个关键字大于pivot.key的记录R[i] if(i<j)//表示找到了R[i]，使R[i].key>pivot.keyR[j--]=R[i];//相当于交换R[i]和R[j]，交换后j指针减1 } R[i]=pivot;//基准记录已被最后定位 returni; }//partition 排序算法性能分析选择数据录入方式随机正序排序算法性能分析选择数据录入方式随机正序逆序手动输入执行执行插入排序插入排序希尔排序冒泡排序快速排序选择排序归并排序调试分析调试中遇到的问题及对问题的解决方法对随机函数的应用中怎样保证其每次产生随机序列的不重复解决方法：利用系统时间，调用time函数排序中移动次数和比拟次数确实定解决方法：动态跟踪函数循环，并分析算法的时间复杂度和空间复杂度排序方法平均时间最坏情况最好情况辅助时间稳定性直接插入排序O(n2)O(n2)O(n)O(1)稳定直接选择排序O(n2)O(n2)O(n2)O(1)稳定冒泡排序O(n2)O(n2)O(n)O(1)稳定快速排序O(nlog2n)O(n2)O(nlog2n)O(log2)不稳定堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不稳定归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定测试结果源程序〔带注释〕#include<stdio.h>#include<time.h>#include<stdlib.h>#include<stdio.h>#defineN1000//定义数组最大为100constintt=3;//定义希尔排序次数intd[3]={4,3,1};//定义希尔排序比拟量intm;intqmt;//快速排序的移动次数intqct;//快速排序的比拟次数voidrandoming(inta[]){srand((int)time(0));for(intx=0;x<1000;x++) printf("%d\t",rand()%100); }voidoutput(intn,inta[],intct,intmt)//内部排序中调用的输出函数{inti;printf("\n排序结果:");for(i=0;i<n;i++)printf("%d\t",a[i]);//输出各排序完成的数组printf("\n比拟次数:%d\n",ct);//输出各排序比拟次数printf("移动次数:%d\n\n",mt);//输出各排序移动次数}voidbubble_sort(intn,intA[])//冒泡排序{intmt=0;//移动次数mt=movetimeintct=0;//比拟次数ct=cmdtimeinti,j,temp;inta[N];for(i=0;i<n;i++)a[i]=A[i];//使数组a[]与数组A[]完全相同,对数组a[]进行操作(不改动A[],可以使A[]被其他函数调用)for(i=0;i<n-1;i++){for(j=0;j<n-1-i;j++,ct++){if(a[j+1]<a[j])//前后比拟temp=a[j],a[j]=a[j+1],a[j+1]=temp,mt+=3;//关键字交换计为3次移动}}printf("冒泡排序");output(n,a,ct,mt);}voidselection_sort(intn,intA[])//选择排序{intmt=0;//移动次数movetimeintct=0;//比拟次数cmdtimeinti,j,temp,k;inta[N];for(i=0;i<n;i++)a[i]=A[i];//使数组a[]与数组A[]完全相同,对数组a[]进行操作(不改动A[],可以使A[]被其他函数调用)for(i=0;i<n-1;i++){k=i;for(j=i+1;j<n;j++,ct++)if(a[k]>a[j])k=j;temp=a[i],a[i]=a[k],a[k]=temp,mt+=3;//关键字交换计为3次移动}printf("选择排序");output(n,a,ct,mt);}voidquick(inta[],intlow,intup)//快速排序递归算法{inti,j,temp;if(low<up){i=low;j=up;temp=a[low],qmt++;while(i!=j){qct++;while(i<j&&a[j]>temp)j--,qct++;if(i<j)a[i++]=a[j],qct++;qmt++;while(i<j&&a[i]<=temp)i++,qct++;if(i<j)a[j--]=a[i],qct++,qmt++;}a[i]=temp,qmt++;quick(a,low,j-1);quick(a,i+1,up);}}voidquick_sort(intn,intA[])//快速排序(通过调用快速排序递归算法完成){inti;inta[N];for(i=0;i<n;i++)a[i]=A[i];//使数组a[]与数组A[]完全相同,对数组a[]进行操作(不改动A[],可以使A[]被其他函数调用)quick(a,0,n-1);//调用快速排序递归算法printf("快速排序");output(n,a,qct,qmt);}voidinsertion_sort(intn,intA[])//插入排序{intmt=0;//移动次数movetimeintct=0;//比拟次数cmdtimeinti,j,temp;inta[N];for(i=0;i<n;i++)a[i]=A[i];//使数组a[]与数组A[]完全相同,对数组a[]进行操作(不改动A[],可以使A[]被其他函数调用)for(i=1;i<n;i++){temp=a[i],mt++;for(j=i-1;j>=0&&temp<a[j];j--,ct++)a[j+1]=a[j],mt++;a[j+1]=temp,mt++;}printf("插入排序");output(n,a,ct,mt);}voidshell_sort(intn,intA[])//希尔排序{intmt=0;//移动次数movetimeintct=0;//比拟次数cmdtimeinti,j,k,h,y;inta[N];for(i=0;i<n;i++)a[i]=A[i];//使数组a[]与数组A[]完全相同,对数组a[]进行操作(不改动A[],可以使A[]被其他函数调用)for(i=0;i<t;i++){h=d[i];for(j=h;j<n;j++){y=a[j],mt++;for(k=j-h,ct++,mt++;k>=0&&y<a[k];k-=h)a[k+h]=a[k];a[k+h]=y;}}printf("希尔排序");output(n,a,ct,mt);}voidmain(){ char*c10="color20",*c11="color27";system(c10);//屏幕颜色 inti,j,n; intA[N]; printf("\n\n\n\n\t\t************************************\n"); printf("\t\t\t排序算法性能分析--王吉玉\n"); printf("\t\t************************************"); printf("\n\n\n\n\t\t\t选择一种数据输入形式:\n"); printf("\t\t\t1randomdata\n"); printf("\t\t\t2inscredata\n"); printf("\t\t\t3descredata\n"); printf("\t\t\t4Inputdata\n");printf("\n"); scanf("%d",&j); if(j==1) randoming(A);//产生一组随机数据 if(j==2)//产生一组递增序列 for(m=0;m<=N;m++) A[m]=m; if(j==3)//产生一组递减序列 for(m=0;m<=N;m++) A[m]=N-m+1; if(j==4)//由用户自己输入数据序列，设这组数据中不含0，以0作为结束 { printf("PleaseInputthesortdata:(endof0)\n");A[0]=1; m=0; while((m<N)&&A[m]) { m++; scanf("%d",&(A[m])); }//m--; }//输出排序前的序列printf("Thesourcedata:\n"); for(i=1;i<=m;i++) printf("%d\t",A[i]); printf("\t\t选择一种排序方法：\n"); printf("\t\t1InsertSort\n");printf("\t\t2BubbleSort\n"); printf("\t\t3SelectSort\n"); printf("\t\t4QuickSort\n");printf("\t\t5shell_sort\n");//插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序、归并排序scanf("%d",&j);if(j==1)insertion_sort(m,A);//直接插入排序if(j==2)bubble_sort(m,A);//冒泡排序if(j==3)selection_sort(m,A);//直接选择排序if(j==4)quick_sort(m,A);//快速排序if(j==5)shell_sort(m,A);//希尔排序//heapsort(m);//堆排序}总结通过本次课程设计，我对内部各种算法以及它的递归与非递归应用，查找任意数有了更深刻的了解，稳固了课堂学习的关于各种算法的知识。当遇到一个算法问题时，首先要知道自己以前有没有处理过这种问题，如果见过，那么你一般会做出来；如果没见过，那么考虑以下问题：1、问题是否是建立在某种的熟悉的数据结构〔例如，选择，冒泡，堆等〕上？如果不是，那么要自己设计数据结构。2、问题所要求编写的算法属于以下哪种类型？〔建立数据结构，修改数据结构，遍历，查找，排序……〕3、分析问题所要求编写的算法的数学性质，是否具备递归特征？〔对于递归程序设计，只要设计出合理的参数表以及递归结束的条件，那么根本上大功告成。〕4、确认你的思路可行，然后开始编写程序，在编写代码的过程中，尽可能把各种问题考虑的详细，周密，程序应该具有良好的结构，并且在关键的地方配有注释。更重要的是对VC++有了更深的认识，初步学会了运用MFC，根本掌握了简单的连接。同时在课程设计的过程中也深深地感到了自己专业知识的匮乏，动手能力极差。在今后的学习中加强动手能力的培养，加强实践！参考文献1严蔚敏，吴伟民.《数据结构〔C语言版〕》.清华大学出版社.2严蔚敏，吴伟民.《数据结构题集〔C语言版〕》.清华大学出版社.3《DATASTRUCTUREWITHC++》.WilliamFord,WilliamTopp.清华大学出版社〔影印版〕.4谭浩强.《c语言程序设计》.清华大学出版社.致谢附件Ⅰ局部源程序代码随机函数生成函数：voidrandoming(inta[]){srand((int)time(0));for(intx=0;x<1000;x++) printf("%d\t",rand()%100); 输出函数：voidoutput(intn