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

《数据结构排序算法大总结 c++》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、#defineCPPC++//比较#defineMPPM++//移动#defineMP2M+=2#defineMP3M+=3#include#include#include#include#include#include//存储结构（数组）constintmaxsize=1000;//排序表容量，假设为100..typedefintdatatype;//假设存储元素是整形类型typedefstruct{dataty

2、pekey;//关键字域}rectype;//记录类型typedefrectypelist[maxsize+1];//排序表类型，0号单元不用；__int64C,M;//比较和移动次数voidcheckup(listR,intn){//检验升序排序结果inti;for(i=2;i<=n;i++)if(R[i].key

3、2;i<=n;i++)if(R[i].key>R[i-1].key){cout<<"Error!";return;}cout<<"Correct!"<

4、/素数模乘同余法,0~MintA=16807;//16807,39722040,764261123,63036001648271?intM=2147483647;//有符号4字节最大素数,2^31-1intQ=M/A;intR=M%A;staticintx=1;//seed(setto1)intx1;x1=A*(x%Q)-R*(x/Q);if(x1>=0)x=x1;elsex=x1+M;returnx;}//直接插入排序(有监视哨)voidInsertSort(listR,intn){inti,j;for(i=2;i<=n;i++

5、){//依次插入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

6、i<=h;i++){//i为组号for(j=i+h;j<=n;j+=h){//每组从第2个记录开始插入if(CPP,R[j].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

7、stR,intn,intd[],intt){//d[]为增量序列，t为增量序列长度inti;for(i=0;i=1;j--)//从下往上扫描if(CPP,R[j].key

8、]=R[j-1];R[j-1]=R[0];}if(!flag)break;}}//下沉冒泡排序voidBubbleSort0(listR,intn){inti,j,flag;for(i=n-1;i>=1;i--){//做n-1趟扫描flag=0;/