欢迎来到天天文库
浏览记录
ID:39569796
大小:30.23 KB
页数:16页
时间:2019-07-06
《内部排序演示C++-课程设计》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、内部排序演示C++-课程设计【问题描述】设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。【基本要求】(1)对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较;(2)待排序的元素的关键字为整数。其中的数据要用伪随机产生程序产生(如10000个),至少用5组不同的输入数据做比较,再使用各种算法对其进行排序,记录其排序时间,再汇总比较。(gettickcount())【数据结构描述】输入一个无序数组,分别使用内部排序的几种方法:bubble_sort(n,A);冒泡排序, insertion_sort(n,A);插入排序 selection_
2、sort(n,A);选择排序 quick_sort(n,A);快速排序 shell_sort(n,A);希尔排序求出分别的比较次数和移动次数。【主要算法流程描述】源程序代码 #include#defineN100//定义数组最大为100constintt=3;//定义希尔排序次数intd[t]={4,3,1};//定义希尔排序比较量intqmt;//快速排序的移动次数intqct;//快速排序的比较次数voidoutput(intn,inta[],intct,intmt)//内部排序中调用的输出函数{ inti; printf("排序结果:");
3、 for(i=0;i4、+) a[i]=A[i];//使数组a[]与数组A[]完全相同,对数组a[]进行操作(不改动A[],可以使A[]被其他函数调用) for(i=0;i5、 } } printf("冒泡排序"); output(n,a,ct,mt);}voidselection_sort(intn,intA[])//选择排序{ intmt=0;//移动次数movetime intct=0;//比较次数cmdtime inti,j,temp,k; inta[N]; for(i=0;i6、=0;ia[j]) k=j; temp=a[i], a[i]=a[k], a[k]=temp, mt+=3;//关键字交换计为3次移动 } pr7、intf("选择排序"); output(n,a,ct,mt);}voidquick(inta[],intlow,intup)//快速排序递归算法{ inti,j,temp; if(low
4、+) a[i]=A[i];//使数组a[]与数组A[]完全相同,对数组a[]进行操作(不改动A[],可以使A[]被其他函数调用) for(i=0;i5、 } } printf("冒泡排序"); output(n,a,ct,mt);}voidselection_sort(intn,intA[])//选择排序{ intmt=0;//移动次数movetime intct=0;//比较次数cmdtime inti,j,temp,k; inta[N]; for(i=0;i6、=0;ia[j]) k=j; temp=a[i], a[i]=a[k], a[k]=temp, mt+=3;//关键字交换计为3次移动 } pr7、intf("选择排序"); output(n,a,ct,mt);}voidquick(inta[],intlow,intup)//快速排序递归算法{ inti,j,temp; if(low
5、 } } printf("冒泡排序"); output(n,a,ct,mt);}voidselection_sort(intn,intA[])//选择排序{ intmt=0;//移动次数movetime intct=0;//比较次数cmdtime inti,j,temp,k; inta[N]; for(i=0;i6、=0;ia[j]) k=j; temp=a[i], a[i]=a[k], a[k]=temp, mt+=3;//关键字交换计为3次移动 } pr7、intf("选择排序"); output(n,a,ct,mt);}voidquick(inta[],intlow,intup)//快速排序递归算法{ inti,j,temp; if(low
6、=0;ia[j]) k=j; temp=a[i], a[i]=a[k], a[k]=temp, mt+=3;//关键字交换计为3次移动 } pr
7、intf("选择排序"); output(n,a,ct,mt);}voidquick(inta[],intlow,intup)//快速排序递归算法{ inti,j,temp; if(low
此文档下载收益归作者所有