数据结构排序算法大总结C++下载_在线阅读_8

#defineCPPC++//比较#defineMPPM++//移动#defineMP2M+=2#defineMP3M+=3#include#include#include#include#include#include//存储结构（数组）constintmaxsize=1000;//排序表容量，假设为100..typedefintdatatype;//假设存储元素是整形类型typedefstruct{datatypekey;//关键字域}rectype;//记录类型typedefrectypelist[maxsize+1];//排序表类型，0号单元不用；__int64C,M;//比较和移动次数voidcheckup(listR,intn){//检验升序排序结果inti;for(i=2;i<=n;i++)if(R[i].keyR[i-1].key){cout<<"Error!\n";return;}cout<<"Correct!"<=0)x=x1;elsex=x1+M;returnx;}//直接插入排序(有监视哨)voidInsertSort(listR,intn){inti,j;for(i=2;i<=n;i++){//依次插入R[2],R[],R[].......R[]if(CPP,R[i].key>=R[i-1].key)continue;//R[i]插入时刚好是升序序列无需移动MPP,R[0]=R[i];//R[0]作为监视哨j=i-1;do{MPP,R[j+1]=R[j];j--;}while(CPP,R[0].key=R[j-h].key)continue;//R[j]大于有序区最后一个记录，则不需要插入MPP,R[0]=R[j];k=j-h;do{//查找正确的插入位置MPP,R[k+h]=R[k];k=k-h;//后移记录，继续向前搜索}while(CPP,k>0&&R[0].key=1;j--)//从下往上扫描if(CPP,R[j].key=1;i--){//做n-1趟扫描flag=0;//直末交换标志for(j=n;j>=1;j--)//从下往上扫描if(CPP,R[j].key>R[j-1].key){flag=1;MP3,R[0]=R[j];R[j]=R[j-1];R[j-1]=R[0];}if(!flag)break;}}//快速排序intPartition(listR,intp,intq){//被无序区R[p]到R[q]划分，返回划分后基准的位置inti,j;i=p;j=q;MPP,R[0]=R[i];//R[0]作辅助量，存放基准，基准取为无序区第一个记录while(i=R[0].key&&i=t)return;//只有一个记录或无记录时无需排序i=Partition(R,s,t);//对R[s]到R[t]做划分QuickSort(R,s,i-1);//递归处理左区间QuickSort(R,i+1,t);//递归处理右区间}//直接选择排序voidSelectSort(listR,intn){inti,j,k;for(i=1;i<=n-1;i++){//n-1趟排序k=i;for(j=i+1;j<=n;j++)//在当前无序区中找键值最小的记录R[k]if(CPP,R[j].keyR[j].key)break;//结点键值大于孩子结点，已经是堆，调整结束！MPP,R[p]=R[j];//将R[j]换到双亲位置上p=j;//修改当前被调整结点j=2*p;//j指向R[p]的左孩子}MPP,R[p]=R[0];//原根结点放入正确位置}voidHeapSort(listR,intn){inti;for(i=n/2;i>=1;i--)Sift(R,i,n);//建初始堆for(i=n;i>=2;i--){//进行n-1趟堆排序MP3,R[0]=R[1];R[1]=R[i];R[i]=R[0];//R[1]到R[i-1]重建成新堆Sift(R,1,i-1);}}/*归并排序*/\//两个子表合并voidMerge(listR,listR1,intlow,intmid,inthigh){//合并R的两个子表，结果在R1中inti,j,k;i=low;j=mid+1;k=low;while(i<=mid&&j<=high)if(CPP,R[i].key<=R[j].key)MPP,R1[k++]=R[i++];//取小者复制elseMPP,R1[k++]=R[j++];while(i<=mid)MPP,R1[k++]=R[i++];//复制左子表的剩余记录while(j<=high)MPP,R1[k++]=R[j++];//复制右子表的剩余记录}//一趟归并voidMergePass(listR,listR1,intn,intlen){//对R做一趟归并，结果在R1中inti=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)//剩下两个子表，其中一个长度小于lenMerge(R,R1,i,i+len-1,n);elsefor(j=i;j<=n;j++)MPP,R1[j]=R[j];}//二路归并voidMergeSort(listR,listR1,intn){//对R二路归并排序，结果在R中（非递归算法）intlen;len=1;while(len>choice;switch(choice){case0:return;break;case1:t1=clock();InsertSort(R,n);//有监视哨的直接插入排序t2=clock();checkup(R,n);break;case2:t1=clock();intts;//shell排序ts=int(log(n)/log(2)-1);intde[maxsize];de[0]=int(n/2);for(i=1;i

                    本文档为【数据结构排序算法大总结C++】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

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

你可能还喜欢