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

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

2、electsort.h#include <iostream.h>/簡單選擇排序template <class T>void SelectSort(T A, int n) int small;for (int i=0; i<n-1; i+) /執(zhí)行n-1趟small=i;for(int j=i+1;j<n;j+)if(Aj<Asmall)small=j;Swap(Ai,Asmall);Insertsort.h#include <iostream.h>/直接插入排序template <class T>void InsertSort(

3、T A, int n) for(int i=1; i<n; i+) /執(zhí)行n-1趟int j=i;T temp=Ai;while(j>0&&temp<Aj-1)Aj=Aj-1;j-;Aj=temp;/*ok!*/Bubblesort.h#include <iostream.h>template <class T>void BubbleSort(T A, int n) int i,j,last; i=n-1; while(i>0) last=0; for(j=0;j<i;j+) if(Aj+1<Aj) Swap(Aj,A

4、j+1); last=j; i=last; Quicksort.h#include <iostream.h>/改進(jìn)的快速排序template<class T>void quick(T A,int n)int *a; /用數(shù)組保存待排序的子序列的上、下界int top=0,right,left,j; /left和right為待排序a=new intn;if(a=NULL) return;atop+=0;atop+=n-1; /以初始序列為待排序序列開始改進(jìn)的快速排序/lcfor(j=0;aj!=NULL;j+) /循環(huán)到數(shù)組元素為空left=aj+;right=aj; /

5、每次按序從數(shù)組中取出兩個元素作為待排序序列的上、下界if(left>right)Swap(left,right); /如果下界大于上界，交換上、下界if(right-left<15)InsertSortExt(A,left,right); /若元素較少調(diào)用插入排序elseatop+=left; atop+=QuickSort(A,left,right)-1;atop+=atop-2+2;atop+=right; /否則將低、高端序列上、下界依次保存到數(shù)組中template<class T>int QuickSort(T A,int left,int right) /用于

6、改進(jìn)的快速排序的原始快速排序方法int i,j;if(left<right)i=left;j=right+1;dodo i+;while(Ai<Aleft);do j-;while(Aj>Aleft);if(i<j)Swap(Ai,Aj);while(i<j);Swap(Aleft,Aj);return j;return 0;template<class T>void InsertSortExt(T A,int left,int right)/用于快速排序的直接插入排序方法for(int i=left+1; i<right; i+) /執(zhí)行n-1

7、趟int j=i;T temp=Ai; /待插入元素存入臨時變量while (j>0 && temp<Aj-1) /從后往前查找插入位置Aj=Aj-1; j-; /Aj-1元素后移，j指針前移Aj=temp; /待插入元素存入找到的插入位置Mergesort.h#include <iostream.h>/兩路合并的C+程序template <class T>void Merge(T A,int i1,int j1,int i2,int j2) / i1,j1是子序列1的下、上界，i1,j2是子序列2的下、上界T *Temp=new Tj2-i

8、1+1; /分配能存放兩個子序列的臨時數(shù)組int i=i1,j=i2,k=0; /i,j是兩個子序列的游動指針，k是Temp的游動指針while(i<=j1&&j<=j2)if(Ai<=Aj)Tempk+=Ai+;else Tempk+=Aj+;while(i<=j1)Tempk+=Ai+;while(j<=j2)Tempk+=Aj+;for(i=0;i<k;i+)Ai1+=Tempi;delete Temp; /合并排序的C+程序template <class T>void MergeSort(T A, int n)int i1

9、,j1,i2,j2; /i1,j1是子序列1的下、上界，i2,j2是子序列2的下、上界int size=1; /子序列中元素個數(shù)，初始化為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;else j2=i2+size-1;Merge(A,i1,j1,i2,j2);i1=j2+1;size*=2;Heapsort.h#include <iostream.h>/AdjustDown函數(shù)template <class T>void AdjustDow

10、n(T A, int r, int j) int child=2*r+1; T temp=Ar; while(child<=j)if(child<j)&&(Achild<Achild+1)child+;if(temp>=Achild)break;A(child-1)/2=Achild;child=2*child+1;A(child-1)/2=temp;/堆排序的C+程序template <class T>void HeapSort(T A, int n)for(int i=(n-2)/2; i>-1; i-) AdjustDown(A,

11、i,n-1); /構(gòu)造最大堆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>#include "selectsort.h"#include "insertsort.h"#include "bubblesort.h"#include "quicksort.h&q

12、uot;#include "mergesort.h"#include "heapsort.h"#define SIZE 400#define TIMES 1000template <class T>class Menupublic:void printmenu();void selectsort();/簡單選擇排序void insertSort();/直接插入排序void bubbleSort();/冒泡排序void quickSort();/快速排序void mergeSort();/兩路合并排序void heapSort();/堆排序vo

13、id childmenu();/子菜單1void childmenu2();/子菜單2void switcha();private:int a,b,c;template <class T>void Menu<T>:printmenu()cout<<"-"<<endl;cout<<" 內(nèi)排序測試系統(tǒng) "<<endl;cout<<"-"<<endl<<endl<<endl;cout<<"1.簡單選擇

14、排序"<<endl;/okcout<<"2.直接插入排序"<<endl;/okcout<<"3.冒泡排序"<<endl;/okcout<<"4.快速排序"<<endl;/okcout<<"5.兩路合并排序"<<endl;/okcout<<"6.堆排序"<<endl;/okcout<<"7.退出"<<endl;co

15、ut<<"PS：測試用的數(shù)組元素為"<<SIZE<<"時間為重復(fù)運(yùn)行"<<TIMES<<"次的時間（包括了產(chǎn)生數(shù)據(jù)與析構(gòu)的時間）"<<endl;this->switcha();template <class T>void Menu<T>:childmenu()cout<<"-"<<endl;cout<<"1.最好情況"<<endl;cout<

16、<"2.最壞情況"<<endl;cout<<"3.平均情況"<<endl;cout<<"4.返回主菜單"<<endl;cin>>b;if(b=4)this->printmenu();template<class T>void Menu<T>:childmenu2()cout<<"-"<<endl;cout<<"1.原始算法"<<endl;co

17、ut<<"2.改進(jìn)算法"<<endl;cout<<"3.返回主菜單"<<endl;cin>>c;if(c=3)this->printmenu();template <class T>void Menu<T>:switcha()/cout<<"ok"<<endl;cin>>a;switch(a)case 1:this->selectsort();break;/okcase 2:this->insert

18、Sort();break;/okcase 3:this->bubbleSort();break;/okcase 4:this->quickSort();break;/okcase 5:this->mergeSort();break;/okcase 6:this->heapSort();break;/okcase 7:exit(1);break;default:cout<<"error"<<endl;this->printmenu();break;template <class T>void printout(

19、T A,int n)/打印數(shù)組，測試時用for(int i=0;i<n;i+)cout<<Ai<<" "cout<<endl;template <class T>T *producedate(int x)/產(chǎn)生順序，逆序，隨機(jī)的數(shù)組int i;T *A=new TSIZE;switch(x)case 1:for(i=0;i<SIZE;i+)Ai=i;return A;/順序break;case 2:for(i=SIZE;i>0;i-)Ai-1=SIZE-i;return A;/逆序break;case 3:s

20、rand(time(NULL);for(i=0;i<SIZE;i+)Ai=rand()%1000+1;return A;/隨機(jī)break;default:cout<<"error"<<endl;return A;break;template <class T>void Swap(T &a,T &b)/交換2個元素T temp=a;a=b;b=temp;template <class T>void Menu<T>:bubbleSort()cout<<"冒泡排序"&

21、lt;<endl;this->childmenu();T *A;double duration;clock_t start,finish;start=clock();cout<<"ok"<<endl;for(int i=0;i<TIMES;i+)A=producedate<T>(b);BubbleSort(A,SIZE);delete A;finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;/printout(A,SIZE);cout<<

22、"用時： "<<duration<<endl;system("pause");/delete A;this->bubbleSort();/*ok*/template <class T>void Menu<T>:heapSort()cout<<"堆排序"<<endl;cout<<"直接用隨機(jī)數(shù)據(jù)測試"<<endl;T *A;double duration;clock_t start,finish;start=cloc

23、k();cout<<"ok"<<endl;for(int i=0;i<TIMES;i+)A=producedate<T>(3);HeapSort(A,SIZE);delete A;finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;cout<<"用時： "<<duration<<endl;system("pause");this->printmenu();template <

24、class T>void Menu<T>:insertSort()cout<<"直接插入排序"<<endl;this->childmenu();T *A;double duration;/A=producedate<T>(b);/if(A=NULL)cout<<"error"delete A;this->insertSort();/printout(A,SIZE);clock_t start,finish;start=clock();cout<<"ok&q

25、uot;<<endl;for(int i=0;i<TIMES;i+)A=producedate<T>(b);InsertSort(A,SIZE);delete A;finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;/printout(A,SIZE);cout<<"用時： "<<duration<<endl;system("pause");/delete A;this->insertSort();template

26、 <class T>void Menu<T>:mergeSort()/this->childmenu();cout<<"合并排序"<<endl;cout<<"直接用隨機(jī)數(shù)據(jù)測試"<<endl;T *A;double duration;clock_t start,finish;start=clock();cout<<"ok"<<endl;for(int i=0;i<TIMES;i+)A=producedate<T>(3

27、);MergeSort(A,SIZE);delete A;finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;/printout(A,SIZE);cout<<"用時： "<<duration<<endl;system("pause");/delete A;this->printmenu();/*ok*/template<class T>void Menu<T>:quickSort()this->childmenu

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

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

30、);printout(A,SIZE);delete A;this->printmenu();*/T *A;start=clock();cout<<"ok"<<endl;for(int i=0;i<TIMES;i+)A=producedate<T>(3);quick(A,SIZE);delete A;finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;cout<<"用時： "<<duration<<en

31、dl;system("pause");this->quickSort();elsecout<<"error"<<endl;this->printmenu();template <class T>void Menu<T>:selectsort()/this->childmenu();cout<<"簡單選擇排序"<<endl;cout<<"直接用隨機(jī)數(shù)據(jù)測試"<<endl;T *A;double durat

32、ion;clock_t start,finish;start=clock();cout<<"ok"<<endl;for(int i=0;i<TIMES;i+)A=producedate<T>(3);SelectSort(A,SIZE);delete A;finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;/printout(A,SIZE);cout<<"用時： "<<duration<<endl;syste

33、m("pause");/delete A;this->printmenu();/*ok!*/Mymain.cpp#include "Menu.h"int main()Menu<int> MenuObj;MenuObj.printmenu();cout<<"ok end."<<endl;return 0;/*ok- 內(nèi)排序測試系統(tǒng)-1.簡單選擇排序2.直接插入排序3.冒泡排序4.快速排序5.兩路合并排序6.堆排序7.退出PS：測試用的數(shù)組元素為400時間為重復(fù)運(yùn)行1000次的時間（包括了產(chǎn)生數(shù)據(jù)與析構(gòu)的時間）ok1簡單選擇排序直接用隨機(jī)數(shù)據(jù)測試ok用時： 0.593請按任意鍵繼續(xù). . .- 內(nèi)排序測試系統(tǒng)-1.簡單選擇排序2.直接插入排序3.冒泡排序4.快速排序5.兩路合并排序6.堆排序7.退出PS：測試用的數(shù)組元素為400時間為重復(fù)運(yùn)行1000次的時間（包括了產(chǎn)生數(shù)據(jù)與析構(gòu)的時間）ok2直接插入排序-1.最好情況2.最壞情況3.平均情況4.返回主菜單1ok用時： 0請按任意鍵繼續(xù). . .直接插入排序-1.最好情況2.最壞情況3.平均情況4.返回主菜單2ok用時： 0.703請按任意鍵繼續(xù). . .直接插入排序-1.最好情況2.最壞情況3