数据结构内部算法排序实验程序与结果分析.doc

内部算法排序实验比较算法的原理及程序实现：#define CPP C+#define MPP M+#define MP2 M+=2#define MP3 M+=3#include #include #include #include #include const int maxsize=100000; /排序表容量typedef int datatype;typedef struct datatype key; /关键字域 /othertype other; /其它域 rectype; /记录类型typedef rectype listmaxsize+2; /排序表类型，0号单元不用_int64 C,M; /比较和移动次数void check(list R,int n) /检验排序结果 int i; for(i=2;i=n;i+) if(Ri.keyRi-1.key) coutError!n;return; coutCorrect! ;void disp(list R,int n) /显示排序后的结果 int i; for(i=1;i=n;i+) coutsetw(4)Ri.key; / if(i%20=0) coutendl; coutendl;/直接插入部分 /*无序区第一记录Ri 插入有序区R1Ri-1，找插入位置和移动记录交替进行：从有序区的后部j开始，如果该位置记录大于待插记录，则后移一位；待插记录插入到最后空出的位置上*/ void InsertSort1(list R,int n) /直接插入排序，带监视哨(并不改变关键字次数) int i,j; for(i=2;i=Ri-1.key) continue; /Ri大于有序区最后一个记录，则本趟不需插入 MPP,R0=Ri; /R0是监视哨 j=i-1; do /查找Ri的插入位置 MPP,Rj+1=Rj;j-; /记录后移，继续向前搜索 while(CPP,R0.keyRj.key); MPP,Rj+1=R0; /插入Ri void InsertSort2(list R,int n) /直接插入排序，无监视哨 int i,j;rectype x; /x为辅助量(用R0代替时间变长) for(i=2;i=Ri-1.key) continue; MPP,x=Ri; /待排记录暂存到x j=i-1; do /顺序比较和移动 MPP,Rj+1=Rj;j-; while(j=1 & (CPP,x.keyRj.key); MPP,Rj+1=x; /插入Ri /折半插入排序void BInsertSort(rectype *R,long n)long i,j,low,m,high;for(i=2;i=n;i+)R0.key=Ri.key; /Ri.key暂存到R0.keylow=1;high=i-1;while(low=high) /在Rlow.heigh中折半查找有序插入位置m=(low+high)/2; /折半*/if(CPP,R0.key=high+1;j-) /记录后移CPP,Rj+1.key=Rj.key;Rhigh+1.key=R0.key; /插入/希尔排序部分 /* 希尔排序又称缩小增量排序，是1959年由D.L.Shell提出来的,其中运用的直接插入排序算法简单，在n值较小时，效率比较高，在n值很大时，若序列按关键码基本有序，效率依然较高。排序表分成若干组，相隔为某个“增量”的记录为一组，各组内直接插入排序；初始增量d1较大，分组较多(每组的记录数少)，以后增量逐渐减少，分组减少(每组的记录数增多)，直到最后增量为1(d1d2dt=1)，所有记录放为同一组，再整体进行一次直接插入排序。*/void ShellInsert(list R,int n) /根据h不同能处理的数据量有所不同 /一趟插入排序，h为本趟增量 int i,j,k,h;for(h=1;h=10;h=h+2) /增量h分别取1，3，5，7，9 for(i=1;i=h;i+) /i为组号 for(j=i+h;j=Rj-h.key) continue; MPP,R0=Rj; /R0保存待插记录，但不是监视哨 k=j-h; /待插记录的前一个记录 do /查找插入位置 MPP,Rk+h=Rk;k=k-h; /后移记录，继续向前搜索 while(CPP,k0 & R0.key=1) / 最后一个步长取1 for (i=k+1;i0 & x.key=1) / 最后一个步长取1 for (i=k+1;i0 & x.keyRj.key)/找到该组有序区第一个不比x大的 MPP, Rj+k=Rj; j=j-k; /将这位后面到有序区最后一位依次后移一位 MPP, Rj+k=x; / 第i个元素的合适位置 k=(k-1)/3; /步长减小return; /下一趟 /直接选择排序/*所有记录组成初始无序区，每趟都从无序区中选出键值最小的记录，与无序区第一个记录交换，有序区增加了一个记录。n-1趟排序后，整个排序表就全部有序了。类似冒泡排序*/ void SelectSort(list R,int n) int i, j, k; rectype x; for (i=1;i=n-1;i+) /n-1趟排序 k=i; / 假定第i个元素的关键字最小 for (j=i+1;j=n;j+) / 无序区中找最小Rk if (CPP,Rj.keyRk.key) k=j; if (k!=i) MP3,x=Ri;Ri=Rk;Rk=x; / 交换Ri和Rk，x作辅助 /冒泡排序部分 /*交换排序的基本思想：依次两两比较相邻关键字，并交换不满足排序要求的关键字，直至全部有序*/void BubbleSort1(list R,int n) /上升法冒泡排序 int i,j,flag;rectype x; /x为辅助量(可用R0代替) for(i=1;i=i+1;j-) /从下向上扫描 if(CPP,Rj.keyRj-1.key) /交换记录 flag=1; MP3,x=Rj;Rj=Rj-1;Rj-1=x;/交换 if(!flag) break; /本趟未交换过记录，排序结束 void BubbleSort2(list R,int n) /下沉法，冒泡排序 int i,j,flag;rectype x; /x为辅助量(可用R0代替) for(i=1;i=n-1;i+) /做n-1趟扫描 flag=0; /置未交换标志 for(j=1;jRj+1.key) /交换记录 flag=1; MP3,x=Rj;Rj=Rj+1;Rj+1=x;/交换 if(!flag) break; /本趟未交换过记录，排序结束 void BubbleSort3(list R,int n)/冒泡排序:双向起泡 int i,j,k;rectype x; int left=1; int right=n-1;do /正向 for(i=right;i=left;i-)/正向起泡第一次循环找到最小数 if(CPP,Ri.keyRi-1.key) MP3,x=Ri;/从底部开始，相邻两数比较,将较小的数上浮 Ri=Ri-1; Ri-1=x; k=i; left=k+1;/记录到前面已排好序的位置k，则反向从k+1开始 /反向 for(i=left;i=right+1;i+)/反向起泡第一次循环找到最大数 if(CPP,Ri.keyRi-1.key) MP3,x=Ri;/从前面开始未排好序的开始，相邻两数比较，较大数下沉 Ri=Ri-1; Ri-1=x; k=i; right=k-1;/记录到底部排好序的位置，下次正向则跳过排好的部分 while(left=x.key) & ij) j-;/从右向左扫描(取消=变快) if(ij) MPP,Ri=Rj;i+; /交换Ri和Rj while(CPP,Ri.key=x.key) & ij) i+;/从左向右扫描 if(ij) MPP,Rj=Ri;j-; /交换Ri和Rj while(i=t) return; /只有一个记录或无记录时无需排序 i=Partition(R,s,t); /对Rs到Rt做划分 QuickSort1(R,s,i-1); /递归处理左区间 QuickSort1(R,i+1,t); /递归处理右区间/堆排序/*堆排序基本思想是：首先对n个记录的键值进行两两比较。然后在其中n/2个较小者之间再进行两两比较。如此重复，直至选出最小键值的记录为止。*/void Sift(list R,int p, int q) /Rp-Rq直接的建堆过程，非递归int i,j; R0=Rp; i=p; j=2*i; while(j=q) if(jq & (CPP,Rj.keyRj.key) break; MPP,Ri=Rj; i=j; j=2*i; Ri=R0;void Sift0(list R, int p, int q) /Rp-Rq递归建堆过程 int i,j; if(p=q) return; i=p; j=2*i; if(jq & CPP,(Rj.keyRj.key) return; MP3,R0=Rj;Rj=Ri;Ri=R0; Sift0(R,j,q);void HeapSort(list R, int n) /堆排序，非递归 int i; for(i=n/2;i=1;i-) Sift(R,i,n); for(i=n;i=2;i-) MP3, R0=R1;R1=Ri;Ri=R0; Sift(R,1,i-1); /归并排序/*初始排序表看成n个长度为1的有序子表，两两归并，得到 n/2 个有序的子表（当n为奇数时，归并后仍有一个长度为1的子表）；再把这些有序子表两两归并，如此反复，直到最后得到一个长度为n的有序表为止。*/void Merge(list R,list R1,int low,int mid,int high) /合并R的两个子表：RlowRmid、Rmid+1Rhigh，结果在R1中 int i,j,k; i=low; j=mid+1; k=low; while(i=mid & j=high) if(CPP,Ri.key=Rj.key) MPP,R1k+=Ri+; /取小者复制 else MPP,R1k+=Rj+; while(i=mid) MPP,R1k+=Ri+; /复制左子表的剩余记录 while(j=high) MPP,R1k+=Rj+; /复制右子表的剩余记录/*调用归并操作将相邻的一对子表进行归并时，必须对子表的个数可能是奇数、以及最后一个子表的长度小于len，这两种特殊情况进行特殊处理，具体算法如下：*/void MergePass(list R,list R1,int n,int len) /对R做一趟归并，结果在R1中 int i,j; i=1; /i指向第一对子表的起始点 while(i+2*len-1=n) /归并长度为len的两个子表 Merge(R,R1,i,i+len-1,i+2*len-1); i=i+2*len; /i指向下一对子表起始点 if(i+len-1n) /剩下两个子表，其中一个长度小于len Merge(R,R1,i,i+len-1,n); else /子表个数为奇数,剩一段 for(j=i;j=n时排序完成，二路算法如下：*/void MergeSort(list R,list R1,int n) /对R二路归并排序，结果在R中(非递归算法) int len; len=1; while(len=0) x=x1; else x=x1+M; r=1.*x/M;if(r0.5) g+; n+;r1+=r;r2+=r*r; if(n%maxsize=0) coutx=r g n=n r1/n r2/n (r2-r1)/n+.25endl; return x;int main() rectype *R,*R1,*S; /R1用于归并排序的辅助存储，S用于保存初始排序数据 R=new list;if(R=NULL) cout数组太大!n;exit(-1); R1=new list;if(R1=NULL) cout数组太大!n;exit(-1); S=new list;if(S=NULL) cout数组太大!n;exit(-1); int i,n=maxsize; int choice; clock_t t1,t2; float s,t;/ srand( (unsigned)time( NULL ) ); for(i=1;i=n;i+) Si.key=random3(n); /生成0-n之间的随机数 do C=M=0; for(i=1;i=n;i+) Ri.key=Si.key; /取出初始数据用于排序 coutchoice; switch(choice) case 1: /按下菜单的数字时跳到对应的排序方法并输出结果 t1=clock(); InsertSort1(R,n); t2=clock(); break; case 2: t1=clock(); InsertSort2(R,n); t2=clock(); break; case 3: t1=clock(); BInsertSort(R,n); t2=clock(); break; case 4: t1=clock(); ShellInsert(R,n); t2=clock(); break; case 5: t1=clock(); ShellInsert2(R,n); t2=clock(); break; case 6: t1=clock(); ShellInsert3(R,n); t2=clock(); break; case 7: t1=clock(); SelectSort(R,n); t2=clock(); break; case 8: t1=clock(); BubbleSort1(R,n); t2=clock(); break; case 9: t1=clock(); BubbleSort2(R,n); t2=clock(); break; case 10: t1=clock(); BubbleSort3(R,n); t2=clock(); break; case 11: t1=clock(); QuickSort1(R,1,n); t2=clock(); break; case 12: t1=clock(); HeapSort(R,n); t2=clock(); break; case 13: t1=clock(); MergeSort(R,R1,n); t2=clock(); break; default:; check(R,n);/ disp(R,n); cout C=C/1e6 M=M/1e6 C+M=(C+M)/1e6; cout time=：float(t2-t1)/CLK_TCKendl; while(choice!=0); delete R;delete S;/ delete R1;实验结果分析：直接插入排序部分移动次数较多，查找时长太长，排序表容量在106以上是查找时间大于5分钟，总体效率较低；带有监视哨时，查找时间有所缩短，但效