请教一下关于c++程序代码

你好，这个我以前做过，一下代码，给你做做参考吧，基本上能满足，你提出的三点要求，有两点点不同：1.数据时随机产生的（产生1000个随机数），不能手动输入，这个你可以根据需要修改一下；2.每一次数据排序之后，都可以看到排序的移动，交换次数以及排序的时间，提示：排序的时间与电脑配置，性能和排序算法的有关要是电脑配置，性能好的话，时间太快，可能会出现时间为0 的情况代码：#define CPP C++ //比较#define MPP M++ //移动#define MP2 M+=2#define MP3 M+=3#include<iostream.h>#include <string.h>#include<stdlib.h>#include <iomanip.h>#include <math.h>#include<time.h>//存储结构（数组）const int maxsize=1000; //排序表容量，假设为100..typedef int datatype; //假设存储元素是整形类型typedef struct {datatype key; //关键字域}rectype; //记录类型typedef rectype list[maxsize+1]; //排序表类型，0号单元不用； __int64 C,M; //比较和移动次数void checkup(list R,int n) { //检验升序排序结果int i;for(i=2;i<=n;i++)if(R[i].key<R[i-1].key) {cout<<"Error!\n";return;}cout<<"Correct! "<<endl;}void checkdown(list R,int n) { //检验降序排序结果int i;for(i=2;i<=n;i++)if(R[i].key>R[i-1].key) {cout<<"Error!\n";return;}cout<<"Correct! "<<endl;}void disp(list R,int n) { //显示数组中的数据int i;for(i=1;i<=n;i++) {cout<<setw(8)<<R[i].key;if(i%10==0) cout<<endl;}cout<<endl;}int random1(int num) {return rand();} //0~RAND_MAX=32767int random2(int num) {//素数模乘同余法,0~Mint A=16807; // 16807,39722040,764261123,630360016 48271?int M=2147483647; //有符号4字节最大素数,2^31-1int Q=M/A;int R=M%A;static int x=1; //seed(set to 1)int x1;x1=A*(x%Q)-R*(x/Q);if(x1>=0) x=x1;else x=x1+M;return x;}//直接插入排序(有监视哨)void InsertSort(list R,int n){int i,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].key);MPP,R[j+1]=R[0];}}//希尔排序(无设置监视哨)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<=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<R[k].key);MPP,R[k+h]=R[0];}}}//希尔排序(调用若干趟插入排序)void ShellSort(list R,int n,int d[],int t) {//d[]为增量序列，t为增量序列长度int i;for(i=0;i<t;i++) //各趟插入排序ShellInsert(R,n,d[i]);}/* 交换排序 *///上升冒泡排序void BubbleSort(list R,int n) {int i,j,flag;for(i=1;i<n-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;}}//下沉冒泡排序void BubbleSort0(list R,int n) {int i,j,flag;for(i=n-1;i>=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;}}//快速排序int Partition(list R,int p,int q) { //被无序区R[p]到R[q]划分，返回划分后基准的位置int i,j;i=p;j=q;MPP,R[0]=R[i]; //R[0]作辅助量，存放基准，基准取为无序区第一个记录while(i<j) {while(CPP,R[j].key>=R[0].key && i<j) j--; //从右向左扫描if(i<j) { MPP,R[i]=R[j]; i++; } //交换 R[i] 和 R[i]while(CPP,R[i].key<=R[0].key && i<j) i++; //从左向右扫描if(i<j) { MPP,R[j]=R[i]; j--; } //交换 R[i] 和 R[i]}MPP,R[i]=R[0]; //将基准移到最后的正确位置return i;}void QuickSort(list R,int s,int t) { //对R[s]到R[t]快速排序int i;if(s>=t) return; //只有一个记录或无记录时无需排序i=Partition(R,s,t); //对R[s]到R[t]做划分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++) //在当前无序区中找键值最小的记录R[k]if(CPP,R[j].key<R[k].key) k=j;if(k!=i) { MP3,R[0]=R[i]; R[i]=R[k]; R[k]=R[0]; }//交换R[k]和R[i]的值,R[0]坐中间辅助量}}//堆排序void Sift(list R,int p,int q){//堆范围为R[p]~R[q],调整R[p]为堆，非递归算法int j;MPP,R[0]=R[p]; //R[0]作辅助量j=2*p; //j指向R[p]的左孩子while(j<=q){if(CPP,j<q && R[j].key<R[j+1].key) j++; //j指向R[p]的右孩子if(CPP,R[0].key>R[j].key) break; //结点键值大于孩子结点，已经是堆，调整结束！MPP,R[p]=R[j]; //将R[j]换到双亲位置上p=j; //修改当前被调整结点j=2*p; //j指向R[p]的左孩子}MPP,R[p]=R[0]; //原根结点放入正确位置}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,R[0]=R[1];R[1]=R[i];R[i]=R[0]; //R[1]到R[i-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,R[i].key<=R[j].key) MPP,R1[k++]=R[i++]; //取小者复制else MPP,R1[k++]=R[j++];while(i<=mid) MPP,R1[k++]=R[i++]; //复制左子表的剩余记录while(j<=high) MPP,R1[k++]=R[j++]; //复制右子表的剩余记录}//一趟归并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) //剩下两个子表，其中一个长度小于 lenMerge(R,R1,i,i+len-1,n);else for(j=i;j<=n;j++) MPP,R1[j]=R[j];}//二路归并void MergeSort(list R,list R1,int n) { //对R二路归并排序，结果在R中（非递归算法）int len;len=1;while(len<n) {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++)S[i].key=random1(n); //生成0-n之间的随机数disp(S,n); //输出0到n之间的随机数do {C=M=0;for(i=1;i<=n;i++) R[i].key=S[i].key; //取出初始数据用于排序cout<<"请选择排序方法(0: 退出): \n\1：直接插入(带监视哨) \n\2: 希尔排序 \n\3：冒泡(上升) \n\4：冒泡(下沉） \n\5：快速排序 (递归) \n\6：直接选择排序 \n\7：堆排序(非递归) \n\8：二路归并(非递归) \n";cin>>choice;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 de[maxsize];de[0]=int(n/2);for(i=1;i<ts-1;i++)de[i]=int(de[i-1]/2);de[ts-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: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_TCK<<endl;} while(choice!=0);delete R;delete S; //释放空间}演示：

请教一下关于c++程序代码

2回答