算法設(shè)計(jì)實(shí)驗(yàn)報(bào)告一-

算法設(shè)計(jì)實(shí)驗(yàn)報(bào)告一、實(shí)驗(yàn)內(nèi)容：題目：1、編程實(shí)現(xiàn)常見(jiàn)排序算法，如插入排序、歸并排序、快速排序、隨機(jī)化的快速排序等，并統(tǒng)計(jì)不同輸入規(guī)模下（1組從小到大排序，1組從大到小排序，其余8組隨機(jī)）的平均物理執(zhí)行時(shí)間。2、編程實(shí)現(xiàn)循環(huán)賽日程表設(shè)有n=2k個(gè)運(yùn)動(dòng)員要進(jìn)行網(wǎng)球循環(huán)賽，先要設(shè)計(jì)一個(gè)滿(mǎn)足一下要求的比賽日常表：（1）每個(gè)選手必須與其他n-1個(gè)選手各賽一次（2）每個(gè)選手一天只能賽一次（3）循環(huán)賽一共進(jìn)行n-1天二、核心代碼說(shuō)明：sort.htemplate<classtype>structSqList{ type*key; intlength;};template<classtype>voidCreateSqList(SqList<type>&sl)//type為int{ intn; cout<<"請(qǐng)輸入順序表的長(zhǎng)度"<<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;//插入低半?yún)^(qū) else low=m+1;//插入高半?yún)^(qū) } 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]復(fù)制到TR for(intb=j;b<=n;b++) TR[k++]=SR[b];}template<classtype>voidMSort(type*SR,type*TR1,ints,intt){ typeTR2[100000];//數(shù)組大小可以根據(jù)實(shí)際情況重新定義 intm; //將SR[s...t]歸并排序?yàn)門(mén)R[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]歸并為T(mén)R2[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){//對(duì)順序表L作歸并排序 MSort(L.key,L.key,1,L.length);}//快速排序template<classtype>intPartition(SqList<type>&L,intlow,inthigh){//交換順序表L中子表key[low]--key[high]中的記錄，樞軸記錄到位，并返回其所在位置，//此時(shí)在它之前（后）的記錄均不大（小）于它 typepivotkey; L.key[0]=L.key[low];//用子表的第一個(gè)記錄作樞軸記錄 pivotkey=L.key[low];//關(guān)鍵字 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);//對(duì)低子表進(jìn)行排序 QSort(L,mid+1,high);//對(duì)高子表進(jìn)行排序 }}template<classtype>voidQuitSort(SqList<type>&L)//對(duì)順序表進(jìn)行快速排序{ 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<<"插入排序平均物理執(zhí)行時(shí)間為"<<finish1-start1<<"ms"<<endl; CreateSqList(sl); start3=GetTickCount(); QuitSort(sl); finish3=GetTickCount(); deletesl.key; cout<<"快速排序平均物理執(zhí)行時(shí)間為"<<finish3-start3<<"ms"<<endl; CreateSqList(sl); start2=GetTickCount(); MergeSort(sl); finish2=GetTickCount(); deletesl.key; cout<<"歸并排序平均物理執(zhí)行時(shí)間為"<<finish2-start2<<"ms"<<endl;}richengbiao.cppintmain(void){ intk; cout<<"輸入k值，且運(yùn)動(dòng)員數(shù)為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;}三、測(cè)試結(jié)果：題目一先把每個(gè)算法的排序時(shí)間得到：再做成表格：算法10001000050000100000插入排序16ms78ms1797ms7484ms歸并排序0ms0ms20ms56ms快速排序0ms0ms16ms32ms題目二四、心得與體