《衡阳师范学院计算机科学与技术课程设计08级1班邓建华》由会员分享，可在线阅读，更多相关《衡阳师范学院计算机科学与技术课程设计08级1班邓建华（8页珍藏版）》请在金锄头文库上搜索。
1、衡阳师范学院 08 级 1 班 邓建华 2011年 06.19#define CPP C+ /比较#define MPP M+ /移动 #define MP2 M+=2 #define MP3 M+=3#include#include #include#include #include #include/存储结构（数组）const int maxsize=1000; /排序表容量，假设为 100.typedef int datatype; /假设存储元素是整形类型typedef struct datatype key; /关键字域rectype; /记录类型typedef rectype li
2、stmaxsize+1; /排序表类型，0 号单元不用；_int64 C,M; /比较和移动次数void checkup(list R,int n) /检验升序排序结果int i;for(i=2;iRi-1.key) cout=0) x=x1;else x=x1+M;return x;/直接插入排序(有监视哨)void InsertSort(list R,int n)int i,j;for(i=2;i=Ri-1.key) continue; /Ri插入时刚好是升序序列无需移动MPP,R0=Ri; /R0作为监视哨j=i-1;doMPP,Rj+1=Rj; j-;while(CPP,R0.key=
3、Rj-h.key) continue; /Rj大于有序区最后一个记录，则不需要插入MPP,R0=Rj;k=j-h;do /查找正确的插入位置MPP,Rk+h=Rk; k=k-h; /后移记录，继续向前搜索while(CPP,k0 & R0.key=1;j-) /从下往上扫描if(CPP,Rj.key=1;i-) /做 n-1 趟扫描flag=0; /直末交换标志for(j=n;j=1;j-) /从下往上扫描if(CPP,Rj.keyRj-1.key)flag=1;MP3,R0=Rj; Rj=Rj-1; Rj-1=R0;if(!flag) break;/快速排序int Partition(lis
4、t R,int p,int q) /被无序区 Rp到 Rq划分，返回划分后基准的位置int i,j;i=p;j=q;MPP,R0=Ri; /R0作辅助量，存放基准，基准取为无序区第一个记录while(i=R0.key & i=t) return; /只有一个记录或无记录时无需排序i=Partition(R,s,t); /对 Rs到 Rt做划分 QuickSort(R,s,i-1); /递归处理左区间QuickSort(R,i+1,t); /递归处理右区间/直接选择排序void SelectSort(list R,int n)int i,j,k;for(i=1;iRj.key) break; /
5、结点键值大于孩子结点，已经是堆，调整结束！MPP,Rp=Rj; /将 Rj换到双亲位置上p=j; /修改当前被调整结点 j=2*p; /j指向 Rp的左孩子MPP,Rp=R0; /原根结点放入正确位置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-) /进行 n-1趟堆排序MP3,R0=R1;R1=Ri;Ri=R0; /R1到 Ri-1重建成新堆Sift(R,1,i-1);/* 归并排序 */两个子表合并void Merge(list R,list R1,int low,int
6、 mid,int high)/合并 R的两个子表，结果在 R1中int i,j,k;i=low; j=mid+1; k=low;while(ichoice;switch(choice) case 0:return;break;case 1:t1=clock();InsertSort(R,n); /有监视哨的直接插入排序t2=clock();checkup(R,n);break;case 2:t1=clock(); int ts; /shell排序ts=int(log(n)/log(2)-1);int demaxsize;de0=int(n/2);for(i=1;its-1;i+)dei=int
7、(dei-1/2);dets-1=1;ShellSort(R,n,de,ts);t2=clock();checkup(R,n);break;case 3:t1=clock();BubbleSort(R,n); /上升法冒泡t2=clock();checkup(R,n);break;case 4:t1=clock();BubbleSort0(R,n); /下沉法冒泡t2=clock();checkdown(R,n);break;case 5:t1=clock();QuickSort(R,1,n); /快速排序t2=clock();checkup(R,n);break;case 6:t1=cloc
8、k();SelectSort(R,n); /直接选择排序t2=clock();checkup(R,n);break;case 7:t1=clock();HeapSort(R,n); /堆排序，非递归 t2=clock();checkup(R,n);break;case 8:t1=clock();MergeSort(R,R1,n);t2=clock();checkup(R,n);break;default:cout输入错误!请重新开始n; disp(R,n); /显示排序后的数据 cout C=C/1e6 M=M/1e6 C+M=(C+M)/1e6;cout 时间:float(t2-t1)/CLK_TCKendl; while(choice!=0);delete R;delete S; /释放空间
