各種內(nèi)排序算法的實現(xiàn)及性能的比較

1、博U點嗜2聲實驗報告（2015/2016學(xué)年第2學(xué)期）課程名稱數(shù)據(jù)結(jié)構(gòu)A實驗名稱各種內(nèi)排序算法的實現(xiàn)及性能的比較實驗時間2016年6月20日指導(dǎo)單位計算機科學(xué)與技術(shù)系學(xué)生姓名班級學(xué)號學(xué)院（系）管理學(xué)院專業(yè)信息管理與信息系統(tǒng)一、問題陳述(1)驗證教材的各種內(nèi)排序算法(2)分析各種內(nèi)排序算法的時間復(fù)雜度(3)改進教材中的快速排序法，使得當(dāng)子集和小于10個元素時改用直接插入排序(4)使用隨機數(shù)發(fā)生器產(chǎn)生大數(shù)據(jù)集合，運行上述各排序算法，使系統(tǒng)時鐘測量個算法所需的實際時間，并進行比較。系統(tǒng)時鐘包含在頭文件“time.h”中。二、概要設(shè)計Main.cpp調(diào)用Menu.h,為主程序。Menu.h主菜單Sel

2、ectsort.h簡單選擇排序Insertsort.h直接插入排序Bubblesort.h冒泡排序Quicksort.h快速排序Mergesort.h合并排序三、詳細(xì)設(shè)計簡單選擇排序：將初始序列(A0An-1)作為待排序序列，第一趟在待排序序列(A0An-1)中找最小元素，與該序列中第一個元素A0交換，這樣子序列(A0)有序，下一趟排序在帶牌子序列(A1An-1)中進行。第i趟排序子序列(Ai-1An-1)中進行經(jīng)過n-1趟排序后使得初始序列有序。程序流程圖:p一一,一一開始i=0Ni<n-1Small=ii+j=i+1Nj<nYNAj<AsmallSmall=YSwap(A

3、i,Asmallj+直接插入排序：一個元素插入到有序表中，首先將其存入臨時變量temp,然后從后往前查找插入位置。當(dāng)temp小于表中元素時，就將該元素后移一個位置，繼續(xù)比較、移動，直到temp大于等于表中元素或者到了有序表的第一個元素結(jié)束，這時就可將temp存入剛后移的元素的位置了程序流程圖:冒泡排序：第一趟在序列(A0An-1)中從前往后進行兩個相鄰元素的比較，若后者小，則交換，比較n-1次；第一趟排序結(jié)束，最大元素被交換到An-1中(即沉底)下一趟排序只需在子序列(A0An-2)中進行；如果在某一趟排序中未進行交換元素，說明子序列已經(jīng)有序，則不再進行下一趟排序?？焖倥判颍喝〉谝粋€元素作為分

4、割元素，初始化i=left,j=right+1,i從左往右尋找第一個大于等于分割元素的元素，j從右往左找第一個小于等于分割元素的元素并交換，i和j繼續(xù)移動，重復(fù)上述步驟,直到當(dāng)i>=j時將j與第一個元素交換。程序流程圖:兩路合并排序：將有n個元素的序列看成是n個長度為1的有序子序列，然后兩兩合并子序列，得到n/2個長度為2或1的有序子序列，再兩兩合并，直到得到一個長度為n的有序序列時結(jié)束。程序流程圖:開始i1=1i1+size<ni2+size-1>n-1j2=n-1j2=i2+size-1Merge(A,i1,j1,i2,j2)i1=j2+1size*=2四、程序代碼sel

5、ectsort.h#include<iostream.h>/簡單選擇排序template<classT>voidSelectSort(TA,intn)(intsmall;for(inti=0;i<n-1;i+)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)for(inti=1;i<n;i+

6、)intj=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>/改進的

7、快速排序template<classT>voidquick(TA,intn)(int*a;inttop=0,right,left,j;a=newintn;if(a=NULL)return;atop+=0;atop+=n-1;/lcfor(j=0;aj!=NULL;j+)(left=aj+;right=aj;if(left>right)Swap(left,right);if(right-left<15)InsertSortExt(A,left,right);else(atop+=left;atop+=QuickSort(A,left,right)-1;atop+=atop

8、-2+2;atop+=right;template<classT>intQuickSort(TA,intleft,intright)(inti,j;if(left<right)i=left;j=right+1;dodoi+;while(Ai<Aleft);doj-;while(Aj>Aleft);if(i<j)Swap(Ai,Aj);while(i<j);Swap(Aleft,Aj);returnj;return0;template<classT>voidInsertSortExt(TA,intleft,intright)(for(inti

9、=left+1;i<right;i+)intj=i;Ttemp=Ai;while(j>0&&temp<Aj-1)Aj=Aj-1;j-;Aj=temp;Mergesort.h#include<iostream.h>兩路合并的C+程序template<classT>voidMerge(TA,inti1,intj1,inti2,intj2)T*Temp=newTj2-i1+1;inti=i1,j=i2,k=0;while(i<=j1&&j<=j2)if(Ai<=Aj)Tempk+=Ai+;elseTempk+

10、=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;intsize=1;while(size<n)i1=0;while(i1+size<n)i2=i1+size;j1=i2-1;if(i2+size-1>n-1)j2=n-1;elsej2=i2+size-1;Merge(A,i1,j1,i2,j2);

11、i1=j2+1;)size*=2;)Meau.h#include<iostream.h>#include<stdio.h>#include<stdlib.h>#include<time.h>#include"selectsort.h"#include"insertsort.h"#include"bubblesort.h"#include"quicksort.h"#include"mergesort.h"#defineSIZE400#defineTI

12、MES1000template<classT>classMenupublic:voidprintmenu();voidselectsort();/簡單選擇排序voidinsertSort();/直接插入排序voidbubbleSort();/冒泡排序voidquickSort();/快速排序voidmergeSort();/兩路合并排序voidchildmenu();/子菜單1voidchildmenu2();/子菜單2voidswitcha();private:inta,b,c;);template<classT>voidMenu<T>:printmenu

13、()cout<<"內(nèi)排序測試系統(tǒng)"<<endl;cout<<""<<endl<<endl<<endl;cout<<"1.簡單選擇排序"<<endl;cout<<"2.直接插入排序"<<endl;cout<<"3.冒泡排序"<<endl;cout<<"4.快速排序"<<endl;cout<<"

14、;5.兩路合并排序"<<endl;cout<<"6.退出"<<endl;this->switcha();)template<classT>voidMenu<T>:childmenu()cout<<""<<endl;cout<<"1.最好情況"<<endl;cout<<"2.最壞情況"<<endl;cout<<"3.平均情況"<<

15、;endl;cout<<"4.返回主菜單"<<endl;cin>>b;if(b=4)this->printmenu();)template<classT>voidMenu<T>:childmenu2()cout<<""<<endl;cout<<"1.原始算法"<<endl;cout<<"2.改進算法"<<endl;cout<<"3.返回主菜單"&l

16、t;<endl;cin>>c;if(c=3)this->printmenu();)template<classT>voidMenu<T>:switcha()cout<<"ok"<<endl;cin>>a;switch(a)case1:this->selectsort();break;/okcase2:this->insertSort();break;/okcase3:this->bubbleSort();break;okcase4:this->quickSort();

17、break;/okcase5:this->mergeSort();break;/okcase6:exit(1);break;default:cout<<"error"<<endl;this->printmenu();break;);template<classT>voidprintout(TA,intn)/打印數(shù)組，測試時用(for(inti=0;i<n;i+)cout<<Ai<<""cout<<endl;)template<classT>T*produ

18、cedate(intx)/產(chǎn)生順序，逆序，隨機的數(shù)組(inti;T*A=newTSIZE;switch(x)(case1:for(i=0;i<SIZE;i+)Ai=i;returnA;/順序break;case2:for(i=SIZE;i>0;i-)Ai-1=SIZE-i;returnA;/逆序break;case3:srand(time(NULL);for(i=0;i<SIZE;i+)Ai=rand()%1000+1;returnA;/隨機break;default:cout<<"error"<<endl;returnA;brea

19、k;template<classT>voidSwap(T&a,T&b)/交換2個元素Ttemp=a;a=b;b=temp;template<classT>voidMenu<T>:bubbleSort()cout<<"冒泡排序"<<endl;this->childmenu();T*A;doubleduration;clock_tstart,finish;start=clock();cout<<"ok"<<endl;for(inti=0;i<TIM

20、ES;i+)A=producedate<T>(b);BubbleSort(A,SIZE);deleteA;finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;/printout(A,SIZE);cout<<"用時："<<duration<<endl;system("pause");/deleteA;this->bubbleSort();/*ok*/template<classT>voidMenu<T>:in

21、sertSort()cout<<"直接插入排序"<<endl;this->childmenu();T*A;doubleduration;A=producedate<T>(b);if(A=NULL)cout<<"error"delete口A;this->insertSort();/printout(A,SIZE);clock_tstart,finish;start=clock();cout<<"ok"<<endl;for(inti=0;i<TIME

22、S;i+)A=producedate<T>(b);InsertSort(A,SIZE);deleteA;finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;/printout(A,SIZE);cout<<"用時："<<duration<<endl;system("pause");/deleteA;this->insertSort();template<classT>voidMenu<T>:mergeSort

23、()/this->childmenu();cout<<"合并排序"<<endl;cout<<"直接用隨機數(shù)據(jù)測試"<<endl;T*A;doubleduration;clock_tstart,finish;start=clock();cout<<"ok"<<endl;for(inti=0;i<TIMES;i+)A=producedate<T>(3);MergeSort(A,SIZE);deleteA;finish=clock();durat

24、ion=(double)(finish-start)/CLOCKS_PER_SEC;/printout(A,SIZE);cout<<"用時："<<duration<<endl;system("pause");/deleteA;this->printmenu();/*ok*/template<classT>voidMenu<T>:quickSort()this->childmenu2();T*A;doubleduration;clock_tstart,finish;if(c=1)cou

25、t<<"原始快速排序"<<endl;cout<<"直接用隨機數(shù)據(jù)測試"<<endl;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<<"用時："

26、;<<duration<<endl;system("pause");this->quickSort();)elseif(c=2)cout<<"改進的快速排序"<<endl;cout<<"直接用隨機數(shù)據(jù)測試"<<endl;/*A=producedate<T>(3);printout(A,SIZE);quick(A,SIZE);printout(A,SIZE);deleteA;this->printmenu();*/T*A;start=cloc

27、k();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<<"用時："<<duration<<endl;system("pause");this->quickSort();)elsecout<<&

28、quot;error"<<endl;this->printmenu();)template<classT>voidMenu<T>:selectsort()/this->childmenu();cout<<"簡單選擇排序"<<endl;cout<<"直接用隨機數(shù)據(jù)測試"<<endl;T*A;doubleduration;clock_tstart,finish;start=clock();cout<<"ok"<<endl;for(inti=0;i<TIMES;i+)(A=producedate<T>(3);SelectSort(A,SIZE);deleteA;finish=clock();duration=(double)(finish