算法设计实验报告一-

算法设计实验报告一、实验内容：题目：1、编程实现常见排序算法，如插入排序、归并排序、快速排序、随机化的快速排序等，并统计不同输入规模下（1组从小到大排序，1组从大到小排序，其余8组随机）的平均物理执行时间。2、编程实现循环赛日程表设有n=2k个运动员要进行网球循环赛，先要设计一个满足一下要求的比赛日常表：（1）每个选手必须与其他n-1个选手各赛一次（2）每个选手一天只能赛一次（3）循环赛一共进行n-1天二、核心代码说明：sort.htemplate<classtype>structSqList{ type*key; intlength;};template<classtype>voidCreateSqList(SqList<type>&sl)//type为int{ intn; cout<<"请输入顺序表的长度"<<endl; cin>>n; sl.length=n; sl.key=newint[sl.length+1]; assert(sl.key); srand(time(0)); for(inti=1;i<=sl.length;i++) { sl.key[i]=rand(); }}template<classtype>voidOutPut(SqList<type>&L){ for(intj=1;j<=L.length;++j) cout<<L.key[j]<<"\t"; cout<<endl;}//折半插入排序template<classtype>voidBInsertSort(SqList<type>&L){ inthigh,low,m; for(inti=2;i<=L.length;i++) { L.key[0]=L.key[i];//将L.key[i]暂存到L.key[0] low=1; high=i-1; while(low<=high)//在key[low]到key[high]中折半查找有序插入的位置 { m=(low+high)/2;//折半 if(L.key[0]<=L.key[m]) high=m-1;//插入低半区 else low=m+1;//插入高半区 } for(intj=i-1;j>=high+1;--j) L.key[j+1]=L.key[j];//记录后移 L.key[high+1]=L.key[0];//插入 }}//归并排序template<classtype>voidMerge(type*SR,type*TR,inti,intm,intn){//将有序的SR[i...m]和SR[m+1...n]归并为有序的TR[i...n] intj,k; for(j=m+1,k=i;i<=m&&j<=n;k++)//将SR中的记录由大到小并入TR { if(SR[i]<=SR[j]) TR[k]=SR[i++]; else TR[k]=SR[j++]; } if(i<=m)//将剩余的SR[i...m]赋值到TR for(inta=i;a<=m;a++) TR[k++]=SR[a]; elseif(j<=n)//将剩余的SR[j...n]复制到TR for(intb=j;b<=n;b++) TR[k++]=SR[b];}template<classtype>voidMSort(type*SR,type*TR1,ints,intt){ typeTR2[100000];//数组大小可以根据实际情况重新定义 intm; //将SR[s...t]归并排序为TR[s...t] if(s==t) TR1[s]=SR[s]; else { m=(s+t)/2;//将SR[s...t]平分为SR[s...m]和SR[m+1...t] MSort(SR,TR2,s,m);//递归地将SR[s...m]归并为有序的TR2[s...m] MSort(SR,TR2,m+1,t);//递归地将SR[m+1...t]归并为TR2[m+1...t] Merge(TR2,TR1,s,m,t);//将TR2[s...m]和TR2[m+1...t]归并到TR1[s...t] }}template<classtype>voidMergeSort(SqList<type>&L){//对顺序表L作归并排序 MSort(L.key,L.key,1,L.length);}//快速排序template<classtype>intPartition(SqList<type>&L,intlow,inthigh){//交换顺序表L中子表key[low]--key[high]中的记录，枢轴记录到位，并返回其所在位置，//此时在它之前（后）的记录均不大（小）于它 typepivotkey; L.key[0]=L.key[low];//用子表的第一个记录作枢轴记录 pivotkey=L.key[low];//关键字 while(low<high)//从表的两端交替向中间扫描 { while(low<high&&L.key[high]>=pivotkey)--high; L.key[low]=L.key[high];//将比枢轴小的记录移至低端 while(low<high&&L.key[low]<=pivotkey)++low; L.key[high]=L.key[low];//将比枢轴大的记录移至高端 } L.key[low]=L.key[0];//枢轴记录到位 returnlow;//返回枢轴位置}template<classtype>voidQSort(SqList<type>&L,intlow,inthigh){ intmid;//接收枢轴位置 if(low<high) { mid=Partition(L,low,high); QSort(L,low,mid-1);//对低子表进行排序 QSort(L,mid+1,high);//对高子表进行排序 }}template<classtype>voidQuitSort(SqList<type>&L)//对顺序表进行快速排序{ QSort(L,1,L.length);}Sort.cppvoidmain(){ SqList<int>sl; LONGLONGstart1,finish1,start2,finish2,start3,finish3; CreateSqList(sl); start1=GetTickCount(); BInsertSort(sl); finish1=GetTickCount(); deletesl.key; cout<<"插入排序平均物理执行时间为"<<finish1-start1<<"ms"<<endl; CreateSqList(sl); start3=GetTickCount(); QuitSort(sl); finish3=GetTickCount(); deletesl.key; cout<<"快速排序平均物理执行时间为"<<finish3-start3<<"ms"<<endl; CreateSqList(sl); start2=GetTickCount(); MergeSort(sl); finish2=GetTickCount(); deletesl.key; cout<<"归并排序平均物理执行时间为"<<finish2-start2<<"ms"<<endl;}richengbiao.cppintmain(void){ intk; cout<<"输入k值，且运动员数为2^k："<<endl; cin>>k; intn=1; for(inti=1;i<=k;i++) n*=2; intplayers=n; inta[100][100]; for(inti=1;i<=n;i++) { a[1][i]=i; } intm=1; for(ints=1;s<=k;s++) { n/=2; for(intt=1;t<=n;t++) for(inti=m+1;i<=2*m;i++) for(intj=m+1;j<=2*m;j++) { a[i][j+(t-1)*m*2]=a[i-m][j+(t-1)*m*2-m]; a[i][j+(t-1)*m*2-m]=a[i-m][j+(t-1)*m*2]; } m*=2; } for(inti=1;i<=players;i++) { for(intj=1;j<=players;j++) cout<<a[i][j]<<""; cout<<endl; } return0;}三、测试结果：题目一先把每个算法的排序时间得到：再做成表格：算法10001000050000100000插入排序16ms78ms1797ms7484ms归并排序0ms0ms20ms56ms快速排序0ms0ms16ms32ms题目二四、心得与体