课程设计报告----内排序算法比较.doc

数据结构课程设计报告提交日期： 8月20日 成绩： 指导老师：实验题目： 内排序算法比较问题解析（对问题的分析、理解和解题方法）：1. 伪随机数的产生是由 time. h 头文件,以rand(time(0)为随机种子的函数rand()产生，可以保持数据的无序性。2. 生成三种文件，分别保存正序.逆序.和随机产生的数据，并在程序执行过程中可选择用某一文件中的数据。3. 用类涵盖六种排序算法的内部操作，并定义数组元素类。4. 输入以文件的方式来进行，必须保证对六种排序算法的输入数据是一样且连续的。5. 对于比较次数的统计加在比较判断的前边，在判断失败时也能统计到比较次数。6. 对于存在递归的快速排序和存在子函数的堆排序的比较次数.移动次数统计采用以引用做函数参数。数据结构选择：选用动态数组为内部基本运算结构，外部数据选用文件。算法设计：构建动态数组元素类，六种排序操作.输出操作为该类的函数，输入操作包含在构造函数中。需求分析：外部数据只可以手动输入随机数的个数。程序运行中可选择采用多种文件用各种算法测试多次。程序主线：产生正序文件f1.txt，倒序文件f2.txt，并生成三个随机文件f3.txt f4.txt f5.txt。选择将某一文件导入程序，进行排序，并测试各种算法的移动和比较次数。最后对结果进行分析。任务分工、进度计划：周一：六种排序算法嵌入各主程序，并进行初步测算。周二：主要解决程序文件输入，输出问题和各函数的接口问题。周三：对程序进行调整，解决部分错误输出。用户手册： 用户需要选择是否生成新的文件，还需要外部输入待排序数组元素个数即可，程序运行中用户可选择用某一文件进行排序。测试结果：请输入排序元素个数:10000请输入读入何种待排序文件:(0：正序 1：逆序 2：随机文件1 3：随机文件2 4：随机文件3)0bubble:比较次数=9999 移动次数：=0insertsort:比较次数=9999 移动次数：=19998ssort:比较次数=49995000 移动次数：=29997qsort:比较次数=19998 移动次数：=39996shellsort:比较次数=120009 移动次数：=240018heapsort:比较次数=264502 移动次数：=394251是否继续测试:(按任意键继续，按0退出:)1请输入排序元素个数:10000请输入读入何种待排序文件:(0：正序 1：逆序 2：随机文件1 3：随机文件2 4：随机文件3)1bubble:比较次数=49995000 移动次数：=149985000insertsort:比较次数=9999 移动次数：=19998ssort:比较次数=49995000 移动次数：=29997qsort:比较次数=19998 移动次数：=39996shellsort:比较次数=120009 移动次数：=240018heapsort:比较次数=264502 移动次数：=394251是否继续测试:(按任意键继续，按0退出:)1请输入排序元素个数:12000请输入读入何种待排序文件:(0：正序 1：逆序 2：随机文件1 3：随机文件2 4：随机文件3)2bubble:比较次数=71963151 移动次数：=109210041insertsort:比较次数=11999 移动次数：=23998ssort:比较次数=71994000 移动次数：=35997qsort:比较次数=19742 移动次数：=38153shellsort:比较次数=144012 移动次数：=288024heapsort:比较次数=324068 移动次数：=482526是否继续测试:(按任意键继续，按0退出:)1请输入排序元素个数:13000请输入读入何种待排序文件:(0：正序 1：逆序 2：随机文件1 3：随机文件2 4：随机文件3)3bubble:比较次数=84487519 移动次数：=126842301insertsort:比较次数=12999 移动次数：=25998ssort:比较次数=84493500 移动次数：=38997qsort:比较次数=21614 移动次数：=41570shellsort:比较次数=156009 移动次数：=312018heapsort:比较次数=353720 移动次数：=526605是否继续测试:(按任意键继续，按0退出:)1请输入排序元素个数:14000请输入读入何种待排序文件:(0：正序 1：逆序 2：随机文件1 3：随机文件2 4：随机文件3)4bubble:比较次数=97891310 移动次数：=146827053insertsort:比较次数=13999 移动次数：=27998ssort:比较次数=97993000 移动次数：=41997qsort:比较次数=23354 移动次数：=44780shellsort:比较次数=168011 移动次数：=336022heapsort:比较次数=383566 移动次数：=571275是否继续测试:(按任意键继续，按0退出:)总结（对所做程序进行分析、评价运行结果、总结遇到的问题及解决办法）：总结：能输出各种算法对同一数组的比较.交换次数，能较直观的比较各种算法在不同情况下的优劣。遇到如下问题：问题1：快速排序的递归中和堆排序的子函数中比较次数和移动次数无法同时返回解决办法:引用比较次数compare和移动次数move作为函数的参数。问题2：在数组很大10000，正序或逆序时，快速排序堆栈溢出解决办法：在编译器中修改了堆栈上限。程序清单：#include#include#includeusing namespace std;class listspublic:int n;void savefile();lists();int getlist(int n)return listn;void output();void bubble();void insertsort();void ssort();void qqsort(int m,int n,int &,int &);void qsort();void shellsort();void restore(int *tree,const int root,const int n,int &,int &);void heapsort();private:int *list;lists:lists() int s0; savefile(); cout请输入读入何种待排序文件:(0：正序 1：逆序 2：随机文件1 3：随机文件2 4：随机文件3)s0; list=new intn; switch(s0) case 0:ifstream infile(f1.txt,ios:in); for(int i=0;ilisti; infile.close();break; case 1:ifstream infile(f2.txt,ios:in); for(int i=0;ilisti; infile.close();break; case 2:ifstream infile(f3.txt,ios:in); for(int i=0;ilisti; infile.close();break; case 3:ifstream infile(f4.txt,ios:in); for(int i=0;ilisti; infile.close();break; case 4:ifstream infile(f5.txt,ios:in); for(int i=0;ilisti; infile.close();break; void lists:output()for(int i=0;in;i+)coutlistiendl;/冒泡排序void lists:bubble()int bound,j,t;int e;int compare=0,move=0;bound=n-1;while(bound)t=0;for(j=0;jlistj+1)move+=3;e=listj;listj=listj+1;listj+1=e;t=j;bound=t;coutbubble:比较次数=compare 移动次数：=moveendl;/直接插入排序void lists:insertsort()int e,i;int compare=0,move=0;/list-1=0;for(int j=1;jn;j+)e=listj;move+;i=j-1;compare+;while(elisti)listi+1=listi;move+;i-;listi+1=e;move+;coutinsertsort:比较次数=compare 移动次数：=move=1;j-)t=0;for(int i=1;i=j;i+)compare+;if(listtlisti)t=i;e=listt;listt=listj;listj=e;move+=3;coutssort:比较次数=compare 移动次数：=moveendl;/快速排序void lists:qqsort(int m,int n,int &a,int &b)int i,j,k,temp;if(mn)i=m;j=n+1;k=listm;b+;while(ij)i+;a+;while(listik)j-;if(ij)temp=listi;listi=listj;listj=temp;b+=3;temp=listm;listm=listj;listj=temp;b+=3;qqsort(m,j-1,a,b);qqsort(j+1,n,a,b);/快速排序void lists:qsort()int compare=0,move=0;qqsort(0,n-1,compare,move);coutqsort:比较次数=compare 移动次数：=move=1)gap=gap/2;for(i=0;igap;i+)int e;int t;for(int j=i+gap;jn;j=j+gap)e=listj;t=j-gap;move+;compare+;while(elistt)listt+gap=listt;t=t-gap;move+;if(t=i)break;listt+gap=e;move+;coutshellsort:比较次数=compare 移动次数：=moveendl;/重建堆void lists:restore(int *tree,const int root,const int n,int &a,int &b)int m,e;int j=root;while(j=n/2-1)a+;if(2*jn-1)&(tree2*jtree2*j+1)m=2*j+1;else m=2*j;a+;if(treej=0;i-)restore(list,i,n,compare,move);for(i=n-1;i0;i-)e=listi;listi=list0;list0=e;restore(list,0,i,compare,move);coutheapsort:比较次数=compare 移动次数：=moveendl;void lists:savefile() int i; srand(time(0); cout请输入排序元素个数:n; list=new intn; ofstream outfile1(f1.txt,ios:out); for(i=0;in;i+)listi=i+1;outfile1listiendl; outfile1.close(); ofstream outfile2(f2.txt,ios:out); for(i=0;in;i+)listi=n-i;outfile2listiendl; outfile2.close(); ofstream outfile3(f3.txt,ios:out); for(i=0;in;i+)listi=rand()%10000+1;outfile3listiendl;outfile3.close(); ofstream outfile4(f4.txt,ios:out); for(i=0;in;i+)listi=rand()%10000+1;outfile4listiendl;outfile4.close(); ofstream outfile5(f5.txt,ios:out); for(i=0;in;i+)listi=rand()%10000+1;outfile5listiendl;outfile5.close();#include#include排序.husing namespace std;int s