数据结构排序算法大总结 C++.doc

#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 listmaxsize+1; /排序表类型，0号单元不用；_int64 C,M; /比较和移动次数void checkup(list R,int n) /检验升序排序结果int i;for(i=2;i=n;i+)if(Ri.keyRi-1.key) coutError!n;return;coutCorrect! endl;void checkdown(list R,int n) /检验降序排序结果int i;for(i=2;iRi-1.key) coutError!n;return;coutCorrect! endl;void disp(list R,int n) /显示数组中的数据int i;for(i=1;i=n;i+) coutsetw(8)Ri.key;if(i%10=0) coutendl;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.keyRj.key);MPP,Rj+1=R0;/希尔排序(无设置监视哨)void ShellInsert(list R,int n,int h) /一趟插入排序，h为本趟增量int i,j,k;for(i=1;i=h;i+) /i为组号for(j=i+h;j=Rj-h.key) continue; /Rj大于有序区最后一个记录，则不需要插入MPP,R0=Rj;k=j-h;do /查找正确的插入位置MPP,Rk+h=Rk; k=k-h; /后移记录，继续向前搜索while(CPP,k0 & R0.keyRk.key); MPP,Rk+h=R0;/希尔排序(调用若干趟插入排序)void ShellSort(list R,int n,int d,int t) /d为增量序列，t为增量序列长度int i;for(i=0;it;i+) /各趟插入排序ShellInsert(R,n,di);/* 交换排序 */上升冒泡排序void BubbleSort(list R,int n) int i,j,flag;for(i=1;i=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(list R,int p,int q) /被无序区Rp到Rq划分，返回划分后基准的位置int i,j;i=p;j=q;MPP,R0=Ri; /R0作辅助量，存放基准，基准取为无序区第一个记录while(i=R0.key & ij) j-; /从右向左扫描if(ij) MPP,Ri=Rj; i+; /交换 Ri 和 Riwhile(CPP,Ri.key=R0.key & ij) i+; /从左向右扫描if(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;i=n-1;i+) /n-1趟排序k=i;for(j=i+1;j=n;j+) /在当前无序区中找键值最小的记录Rkif(CPP,Rj.keyRk.key) k=j;if(k!=i) MP3,R0=Ri; Ri=Rk; Rk=R0; /交换Rk和Ri的值,R0坐中间辅助量/堆排序void Sift(list R,int p,int q)/堆范围为RpRq,调整Rp为堆，非递归算法int j;MPP,R0=Rp; /R0作辅助量j=2*p; /j指向Rp的左孩子while(j=q)if(CPP,jq & Rj.keyRj.key) break; /结点键值大于孩子结点，已经是堆，调整结束！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 mid,int high)/合并R的两个子表，结果在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+; /复制右子表的剩余记录/一趟归并void MergePass(list R,list R1,int n,int len) /对R做一趟归并，结果在R1中int i=1,j; /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-1=n) /剩下两个子表，其中一个长度小于 len Merge(R,R1,i,i+len-1,n);else for(j=i;j=n;j+) MPP,R1j=Rj;/二路归并void MergeSort(list R,list R1,int n) /对R二路归并排序，结果在R中（非递归算法）int len;len=1;while(lenn) MergePass(R,R1,n,len); len=len*2; /一趟归并，结果在R1中MergePass(R1,R,n,len); len=len*2; /再次归并结果在R中void 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;for(i=1;i=n;i+)Si.key=random1(n); /生成0-n之间的随机数disp(S,n); /输出0到n之间的随机数do C=M=0;for(i=1;i=n;i+) Ri.key=Si.key; /取出初始数据用于排序coutchoice;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(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=clock();SelectSort(R,n); /直接选择排序t2=clock();checkup(R,n);break;case 7:t1=clock();HeapSort(R,n); /堆排序，非递归 t2=clock();checkup(R,n);break;case 8:t