數(shù)據(jù)結(jié)構(gòu)試驗(yàn)報(bào)告——各種內(nèi)排序算法的實(shí)現(xiàn)及性能比較

1、實(shí)驗(yàn)報(bào)告（2010/2011學(xué)年第2學(xué)期）課程名稱數(shù)據(jù)結(jié)構(gòu)一一使用C+畸言描述實(shí)驗(yàn)名稱各種內(nèi)排序算法的實(shí)現(xiàn)及性能比較實(shí)驗(yàn)時(shí)間2011年5月27日指導(dǎo)單位計(jì)算機(jī)科學(xué)與技術(shù)系指導(dǎo)教師學(xué)生姓名班級(jí)學(xué)號(hào)學(xué)院（系）專業(yè)實(shí)驗(yàn)名稱各種內(nèi)排序算法的實(shí)現(xiàn)及性能比較指導(dǎo)老師實(shí)驗(yàn)類型設(shè)計(jì)實(shí)驗(yàn)學(xué)時(shí)4實(shí)驗(yàn)時(shí)間2011.5.27一.實(shí)驗(yàn)?zāi)康暮鸵髢?nèi)容：驗(yàn)證教材的各種內(nèi)排序算法。分析各種排序算法的時(shí)間復(fù)雜度。要求：使用隨機(jī)數(shù)產(chǎn)生器產(chǎn)生大數(shù)據(jù)集合，運(yùn)行上述各種排序算法，使用系統(tǒng)時(shí)鐘測(cè)量各算法所需的實(shí)際時(shí)間，并進(jìn)行比較。二.實(shí)驗(yàn)環(huán)境(實(shí)驗(yàn)設(shè)備)VisualC+6.0三.實(shí)驗(yàn)原理及內(nèi)容/selectsort.h#include&

2、lt;iostream.h>/iW單選擇排序template<classT>voidSelectSort(TA,intn)(intsmall;for(inti=0;i<n-1;i+)執(zhí)行n-1趟small=i;for(intj=i+1;j<n;j+)if(Aj<Asmall)small=j;Swap(Ai,Asmall);Insertsort.h#include<iostream.h>/直接插入排序template<classT>voidInsertSort(TA,intn)/執(zhí)行n-1趟for(inti=1;i<n;i+)in

3、tj=i;Ttemp=Ai;while(j>0&&temp<Aj-1)Aj=Aj-1;j-;Aj=temp;/*ok!*/Bubblesort.h#include<iostream.h>template<classT>voidBubbleSort(TA,intn)inti,j,last;i=n-1;while(i>0)last=0;for(j=0;j<i;j+)if(Aj+1<Aj)Swap(Aj,Aj+1);last=j;i=last;Quicksort.h#include<iostream.h>/改進(jìn)的快速排

4、序template<classT>voidquick(TA,intn)int*a;/用數(shù)組保存待排序的子序列的上、下界inttop=0,right,left,j;/left和right為待排序a=newintn;if(a=NULL)return;atop+=0;atop+=n-1;/以初始序列為待排序序列開始改進(jìn)的快速排序/lcfor(j=0;aj!=NULL;j+)/循環(huán)到數(shù)組元素為空left=aj+;right=aj;每次按序從數(shù)組中取出兩個(gè)元素作為待排序序列的上、下界if(left>right)Swap(left,right);/如果下界大于上界，交換上、下界if(ri

5、ght-left<15)InsertSortExt(A,left,right);若元素較少調(diào)用插入排序elseatop+=left;atop+=QuickSort(A,left,right)-1;atop+=atop-2+2;atop+=right;/否則將低、高端序列上、下界依次保存到數(shù)組中template<classT>intQuickSort(TA口,intleft,intright)/用于改進(jìn)的快速排序的原始快速排序方法inti,j;if(left<right)i=left;j=right+1;dodoi+;while(Ai<Aleft);doj-;whi

6、le(Aj>Aleft);if(i<j)Swap(Ai,Aj);while(i<j);Swap(Aleft,Aj);returnj;return0;template<classT>voidInsertSortExt(TA口,intleft,intright)/用于快速排序的直接插入排序方法for(inti=left+1;i<right;i+)intj=i;Ttemp=Ai;while(j>0&&temp<Aj-1)Aj=Aj-1;j-;Aj=temp;/執(zhí)行n-1趟/待插入元素存入臨時(shí)變量/從后往前查找插入位置/Aj-1元素后移，

7、j指針前移/待插入元素存入找到的插入位置Mergesort.h#include<iostream.h>/兩路合并的C+程序template<classT>voidMerge(TA,inti1,intj1,inti2,intj2)/i1,j1是子序列1的下、上界，i1,j2是子序列2的下、上界T*Temp=newTj2-i1+1;/分配能存放兩個(gè)子序列的臨時(shí)數(shù)組inti=i1,j=i2,k=0;/i,j是兩個(gè)子序列的游動(dòng)指針，k是Temp的游動(dòng)指針while(i<=j1&&j<=j2)if(Ai<=Aj)Tempk+=Ai+;elseTe

8、mpk+=Aj+;while(i<=j1)Tempk+=Ai+;while(j<=j2)Tempk+=Aj+;for(i=0;i<k;i+)Ai1+=Tempi;deleteTemp;/合并排序的C+程序template<classT>voidMergeSort(TA,intn)inti1,j1,i2,j2;/i1,j1是子序列1的下、上界，i2,j2是子序列2的下、上界intsize=1;/子序列中元素個(gè)數(shù)，初始化為1。while(size<n)i1=0;while(i1+size<n)i2=i1+size;j1=i2-1;if(i2+size-1&

9、gt;n-1)j2=n-1;elsej2=i2+size-1;Merge(A,i1,j1,i2,j2);i1=j2+1;size*=2;Heapsort.h#include<iostream.h>/AdjustDown函數(shù)template<classT>voidAdjustDown(TA,intr,intj)intchild=2*r+1;Ttemp=Ar;while(child<=j)if(child<j)&&(Achild<Achild+1)child+;if(temp>=Achild)break;A(child-1)/2=Ac

10、hild;child=2*child+1;A(child-1)/2=temp;/堆排序的C+程序template<classT>voidHeapSort(TA,intn)/構(gòu)造最大堆for(inti=(n-2)/2;i>-1;i-)AdjustDown(A,i,n-1);for(i=n-1;i>0;i-)Swap(A0,Ai);AdjustDown(A,0,i-1);Meau.h#include<iostream.h>#include<stdio.h>#include<stdlib.h>#include<time.h>#i

11、nclude"selectsort.h"#include"insertsort.h"#include"bubblesort.h"#include"quicksort.h"#include"mergesort.h"#include"heapsort.h"#defineSIZE400#defineTIMES1000template<classT>classMenupublic:voidprintmenu();voidselectsort();/簡單選擇排序voidin

12、sertSort();/直接插入排序voidbubbleSort();/冒泡排序voidquickSort();快速排序voidmergeSort();/兩路合并排序voidheapSort();/雌排序voidchildmenu();/子菜單1voidchildmenu2();/子菜單2voidswitcha();private:inta,b,c;template<classT>voidMenu<T>:printmenu()cout<<""<<endl;cout<<"內(nèi)排序測(cè)試系統(tǒng)"<&

13、lt;endl;cout<<""<<endl<<endl<<endl;cout<<”1.簡單選擇排序"<<endl;/okcout<<"2.直接插入排序"<<endl;/okcout<<"3.冒泡排序"<<endl;/okcout<<"4.快速排序"<<endl;/okcout<<”5.兩路合并排序"<<endl;/okcout&

14、lt;<"6.堆排序"<<endl;/okcout<<"7.退出"<<endl;cout<<"PS:測(cè)試用的數(shù)組元素為"<<SIZE<<"時(shí)間為重復(fù)運(yùn)行"<<TIMES<<"次的時(shí)間(包括了產(chǎn)生數(shù)據(jù)與析構(gòu)的時(shí)間)"<<endl;this->switcha();template<classT>voidMenu<T>:childmenu()cout<&

15、lt;""<<endl;cout<<"1.最好情況"<<endl;cout<<”2.最壞情況"<<endl;cout<<"3.平均情況"<<endl;cout<<"4.返回主菜單"<<endl;cin>>b;if(b=4)this->printmenu();template<classT>voidMenu<T>:childmenu2()cout<<

16、;""<<endl;cout<<"1.原始算法"<<endl;cout<<"2.改進(jìn)算法"<<endl;cout<<"3.返回主菜單"<<endl;cin>>c;if(c=3)this->printmenu();)template<classT>voidMenu<T>:switcha()cout<<"ok"<<endl;cin>>a;s

17、witch(a)case1:this->selectsort();break;/okcase2:this->insertSort();break;/okcase3:this->bubbleSort();break;/okcase4:this->quickSort();break;okcase5:this->mergeSort();break;okcase6:this->heapSort();break;okcase7:exit(1);break;default:cout<<"error"<<endl;this-&g

18、t;printmenu();break;);template<classT>voidprintout(TA口,intn)/打印數(shù)組，測(cè)試時(shí)用for(inti=0;i<n;i+)cout<<Ai<<""cout<<endl;)template<classT>T*producedate(intx)/產(chǎn)生順序，逆序，隨機(jī)的數(shù)組inti;T*A=newTSIZE;switch(x)case1:for(i=0;i<SIZE;i+)Ai=i;returnA;/順序break;case2:for(i=SIZE;i&g

19、t;0;i-)Ai-1=SIZE-i;returnA;/逆序break;case3:srand(time(NULL);for(i=0;i<SIZE;i+)Ai=rand()%1000+1;returnA;/隨機(jī)break;default:cout<<"error"<<endl;returnA;break;)template<classT>voidSwap(T&a,T&b)/交換2個(gè)元素(Ttemp=a;a=b;b=temp;)template<classT>voidMenu<T>:bubble

20、Sort()(cout<<"冒泡排序"<<endl;this->childmenu();T*A;doubleduration;clock_tstart,finish;start=clock();cout<<"ok"<<endl;for(inti=0;i<TIMES;i+)(A=producedate<T>(b);BubbleSort(A,SIZE);deleteA;)finish=clock();duration=(double)(finish-start)/CLOCKS_PER_S

21、EC;/printout(A,SIZE);cout<<"用時(shí)："<<duration<<endl;system("pause");/deleteA;this->bubbleSort();/*ok*/template<classT>voidMenu<T>:heapSort()(cout<<"堆排序"<<endl;cout<<"直接用隨機(jī)數(shù)據(jù)測(cè)試"<<endl;T*A;doubleduration;cloc

22、k_tstart,finish;start=clock();cout<<"ok"<<endl;for(inti=0;i<TIMES;i+)(A=producedate<T>(3);HeapSort(A,SIZE);deleteA;finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;cout<<"用時(shí)："<<duration<<endl;system("pause");this->p

23、rintmenu();template<classT>voidMenu<T>:insertSort()(cout<<"直接插入排序"<<endl;this->childmenu();T*A;doubleduration;/A=producedate<T>(b);if(A=NULL)cout<<"error”;deleteA;this->insertSort();/printout(A,SIZE);clock_tstart,finish;start=clock();cout<&

24、lt;"ok"<<endl;for(inti=0;i<TIMES;i+)A=producedate<T>(b);InsertSort(A,SIZE);deleteA;finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;/printout(A,SIZE);cout<<"用時(shí)："<<duration<<endl;system("pause");/deleteA;this->insertSort()

25、;template<classT>voidMenu<T>:mergeSort()/this->childmenu();cout<<"合并排序"<<endl;cout<<"直接用隨機(jī)數(shù)據(jù)測(cè)試"<<endl;T*A;doubleduration;clock_tstart,finish;start=clock();cout<<"ok"<<endl;for(inti=0;i<TIMES;i+)A=producedate<T>

26、(3);MergeSort(A,SIZE);deleteA;finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;/printout(A,SIZE);cout<<"用時(shí)："<<duration<<endl;system("pause");/deleteA;this->printmenu();/*ok*/template<classT>voidMenu<T>:quickSort()this->childmenu2()

27、;T*A;doubleduration;clock_tstart,finish;if(c=1)cout<<"原始快速排序"<<endl;cout<<"直接用隨機(jī)數(shù)據(jù)測(cè)試"<<endl;start=clock();cout<<"ok"<<endl;for(inti=0;i<TIMES;i+)A=producedate<T>(3);QuickSort2(A,SIZE);deleteA;finish=clock();duration=(double)(

28、finish-start)/CLOCKS_PER_SEC;cout<<"用時(shí)："<<duration<<endl;system("pause");this->quickSort();)elseif(c=2)cout<<”改進(jìn)的快速排序"<<endl;cout<<"直接用隨機(jī)數(shù)據(jù)測(cè)試"<<endl;/*A=producedate<T>(3);printout(A,SIZE);quick(A,SIZE);printout(A,S

29、IZE);deleteA;this->printmenu();*/T*A;start=clock();cout<<"ok"<<endl;for(inti=0;i<TIMES;i+)A=producedate<T>(3);quick(A,SIZE);deleteA;)finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;cout<<"用時(shí)："<<duration<<endl;system("pa

30、use");this->quickSort();)elsecout<<"error”<<endl;this->printmenu();)template<classT>voidMenu<T>:selectsort()/this->childmenu();cout<<"簡單選擇排序"<<endl;cout<<"直接用隨機(jī)數(shù)據(jù)測(cè)試"<<endl;T*A;doubleduration;clock_tstart,finish;st

31、art=clock();cout<<"ok"<<endl;for(inti=0;i<TIMES;i+)(A=producedate<T>(3);SelectSort(A,SIZE);deleteA;finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;/printout(A,SIZE);cout<<"用時(shí)："<<duration<<endl;system("pause");/deleteA;this->printmenu();/*ok!*/Mymain.cpp#include"Menu.h"intmain()(Menu<int>MenuObj;MenuObj.printmenu();cout<<"okend."<<endl;return0;/*ok內(nèi)排序測(cè)試系統(tǒng)1 .簡單選擇排序2 .直接插入排序3 .冒泡排序4 .快速排序5 .兩路合并排序6 .堆排序7退出PS:測(cè)試用的數(shù)組元