课程设计——内部排序算法比较.doc

内部排序算法比较需求分析 各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间，存在一定的却缺陷。我们将通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。所设计的程序应能够将产生的随机数据同时用不同的内部排序算法排序，并列出关键字比较次数与移动次数，方便比较。待排序表的表长不少于100，为方便起见，我们令表长等于100，用5组随机的数据排序的结果作比较。概要设计2.1 可能排序表的抽象数据类型定义：ADT OrderableList数据对象：D=|IntegerSet，i=1，2，n，n0数据关系：R1=,|,D,i=2,n基本操作：InitList（n）操作结果：构造一个长度为n，元素值依次为1，2，n的有序表。RandomizeList(d,isInverseOrder)操作结果：首先根据isInverseOrder为True或False，将表置为逆序或正序，然后将表进行d（0d8）级随机打乱。d为0时表不打乱，d越大，打乱程度越高。RecallList（）操作结果：恢复最后一次用RandomizeList随机大乱的可排序表。ListLength（）操作结果：返回可排序的长度。ListEmpty（）操作结果：若可排序表为空表，则返回True，否则返回False。BubbleSort（&c，&s）操作结果：进行冒泡排序，返回关键字比较次数c和移动次数s。InsertSort（&c，&s）操作结果：进行插入排序，返回关键字比较次数c和移动次数s。SelectSort（&c，&s）操作结果：进行选择排序，返回关键字比较次数c和移动次数s。QuickSort（&c，&s）操作结果：进行快速排序，返回关键字比较次数c和移动次数s。ShellSort（&c，&s）操作结果：进行希尔排序，返回关键字比较次数c和移动次数s。HeapSort（&c，&s）操作结果：进行堆排序，返回关键字比较次数c和移动次数s。ListTraveres（visit()）操作结果：依次对L中的每个元素调用函数visit（）。ADT OrderableList2.2 本程序包含两个模块： 2.2.1 主程序模块： void main()初始化；do接受命令；处理命令； while （命令!=退出）； 2.2.2 可排序表单元模块：实现可排序表的抽象数据类型;主程序模块可排序表单元模块详细设计3.1 直接插入排序直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到已牌号序的有序表中，从而得到一个新的、记录数增1的有序表。其算法如下：void insertsort(sqlist b,int n)int i,j;int s=0,t=0;for(i=2;in;i+) b0=bi; s+; j=i-1; t+; while(b0.keybj.key) bj+1=bj; j-; s+; t+; bj+1=b0; s+; cout移动次数=s,比较次数=tendl;3.2 折半排序由于插入排序的基本操作是在一个有序表中进行查找和插入，可知这个“查找”操作可利用“折半查找”来实现，由此进行的插入排序称之为折半插入排序，其算法如下：void BInsertSort (int *data,long *p_movetime ,long *p_comparetime)int i ,j ,amount,low,high,m; *p_movetime = *p_comparetime = 0;amount = *data;for( i = 2;i =amount; +i)*(data) = *(data+i); (*p_movetime)+;low = 1; high = i-1;while(low=high)(*p_comparetime)+;m = (low+high)/2;(*p_comparetime)+; /针对于接下来的*(data)和*(data+m)的比较if( *(data) =high+1;-j)*(data+j+1) = *(data+j); (*p_movetime)+;*(data+high+1) = *(data);(*p_movetime)+;3.3 二路插入排序二路插入排序是在折半插入排序的基础上再改进之，其目的是减少排序过程中移动记录的次数，但为此需要n个记录的辅助空间。算法如下:void TwoWaySort(int *data,long *p_movetime ,long *p_comparetime) int amount;int first,final,i,j; /first和final分别指示有序序列中的第一个记录和最后一个记录在d中的位置;int d33000;*p_movetime = *p_comparetime = 0;amount = *data;d1 = *(data+1);first = 1; final = 1;for(i=2; i= d1) /插入前部for(j=final; dj*(data+i); j-)(*p_comparetime)+;dj+1 = dj;(*p_movetime)+;dj+1 = *(data+i);(*p_movetime)+;final+;else /插入后部if(first=1)first = amount; dfirst = *(data+i);(*p_movetime)+; elsefor(j=first; dj*(data+i) & j=amount; j+)(*p_comparetime)+;dj-1=dj;(*p_movetime)+; dj-1=*(data+i);(*p_movetime)+; first-;/forfor(i=first,j=1; j0) for(i=gap+1;i0) t+; if(bj.keybj+gap.key) x=bj;bj=bj+gap; bj+gap=x;j=j-gap; s+=3; else j=0; gap=gap/2; cout移动次数=s,比较次数=tendl;3.5起泡排序：冒泡排序的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。算法如下：void gensort(int b,int n)int i,j;int s=0,t=0;for(i=0;in-1;i+) for(j=i+1;jbj) int temp=bi; bi=bj; bj=temp; s+=3; cout移动次数=s,比较次数=tendl;4、调试分析4.1 调试问题分析编程过程中出现了各种各样的错误,如输错代码,未定义变量,数组下标越界,产生随机数据的程序不工作等等,导致编译没能通过没有结果.最后和组员讨论,又请教一些同学,终于把所有问题都解决掉,运行出了结果.4.2 经验体会通过完成本次课程设计,我学到了很多.编程过程中出现了很多的问题,对程序进行了很多次的调试,自己调试程序的能力有了很大的提升.同时也意识到一个人的力量实在有限,应该多和同学交流合作,这样既能加深了同学之间的友谊也能提高效率,实在没有必要耗费大量的时间去钻牛角尖.5、用户使用说明内部排序算法比较用户使用说明本系统采用Visual C+语言编写,运用软件工程的思想, 采用面向对象分析、设计的方法学完成。本程序主要用于人们比较排序算法，从直观感受各种排序的优缺点。6、测试数据与测试结果下图是自动产生的五组随机产生的100个数据的排序结果，由图可知希尔排序、快速排序的关键字移动次数和比较次数都相对较少。起泡排序、选择排序中关键字比较次数很大，起泡排序、插入排序移动次数很大。这样方便我们快捷的看出排序优缺点。参考文献1 严蔚敏，吴伟民. 数据结构(C语言版) M. 北京：清华大学出版社，1997.042 严蔚敏，吴伟民. 数据结构题集(C语言版) M. 北京：清华大学出版社，1997.043 汪杰等，数据结构经典算法实现与习题解答M. 北京：人民邮电出版社，20044 陈媛，何波，涂晓红等，算法与数据结构M. 北京：清华大学出版社，20055李春葆.数据结构习题与解析(第二版) M.北京：清华大学出版社，2004.07 附录 源程序清单#include#include#include#include#include#define N 100int p,q;/起泡排序void gensort(int b,int n)int i,j;int s=0,t=0;for(i=0;in-1;i+) for(j=i+1;jbj) int temp=bi; bi=bj; bj=temp; s+=3; cout移动次数=s,比较次数=tendl;/插入排序typedef int KeyType;struct rec KeyType key;typedef rec sqlistN;void insertsort(sqlist b,int n)int i,j;int s=0,t=0;for(i=2;in;i+) b0=bi; s+; j=i-1; t+; while(b0.keybj.key) bj+1=bj; j-; s+; t+; bj+1=b0; s+; cout移动次数=s,比较次数=t0) for(i=gap+1;i0) t+; if(bj.keybj+gap.key) x=bj;bj=bj+gap; bj+gap=x;j=j-gap; s+=3; else j=0; gap=gap/2; cout移动次数=s,比较次数=tendl;/选择排序 void gentsort(int b,int n)int i,j,k;int s=0,t=0;for(i=0;in-1;i+) k=i; for(j=i+1;jbj) k=j; if(k!=i) int temp=bk; bk=bi; bi=temp; s+=3; cout移动次数=s,比较次数=tendl;/快速排序void output(sqlist b,int n)/输出元素值for(int i=0;in;i+) coutsetw(4)bi.key;coutendl;void display(int n,int m)/输出计数cout移动次数=n,比较次数=mendl;void BeforeSort()/初始化计数器p=0;q=0;void quicksort(sqlist r,int s,int t)int i=s,j=t;if(st) r0=rs;p+; while(ij) p+; while(i=r0.key) j-; ri=rj; q+; p+; p+; while(ij&ri.key=r0.key) i+; rj=ri;q+;p+; ri=r0;p+; else return;quicksort(r,s,j-1);quicksort(r,j+1,t); void sort(sqlist r,int s,int t)BeforeSort();quicksort(r,s,t);display(p,q);/堆排序void sift(sqlist r,int s,int m)int j;rec x;x=rs;for(j=2*s;j=m;j*=2)q+;if(jm&(rj.keyrj+1.key) +j;q+;if(!(x.key0;-i) sift(r,i,m);for(i=m;i1;-i) w=ri;ri=r1; r1=w; p+=3; sift(r,1,i-1);void sorting(sqlist &r,int t)BeforeSort();heapsort(r,t);display(p,q);void init(int a)/随机生成N个整数并 int i; srand ( ( unsigned int ) time ( NULL ) ); for(i=0;iN;i+) ai=rand()%99+1;void main()int a1N,i;int e=N;sqlist a,b,c,d;int c1N;int low=0,high=10;init(a1);for(i=0;iN;i+)c1i=a1i;ai.key=a1i;bi.key=a1i;ci.key=a1i;di.key=a1i;cout排序前数组:n;for(i=0;iN;i+)co