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

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

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

3、(Ai,Asmall)j+結(jié)束NNNYYi+直接插入排序：一個(gè)元素插入到有序表中，首先將其存入臨時(shí)變量temp，然后從后往前查找插入位置。當(dāng)temp小于表中元素時(shí)，就將該元素后移一個(gè)位置，繼續(xù)比較、移動(dòng)，直到temp大于等于表中元素或者到了有序表的第一個(gè)元素結(jié)束，這時(shí)就可將temp存入剛后移的元素的位置了。程序流程圖：開始i<nint j=iT temp=Aij>0&&temp<Aj-1Aj=Aj-1;j-Aj=tempi+結(jié)束NYYN冒泡排序：第一趟在序列（A0An-1）中從前往后進(jìn)行兩個(gè)相鄰元素的比較，若后者小，則交換，比較n-1次；第一趟排序結(jié)束，最大元

4、素被交換到An-1中（即沉底）下一趟排序只需在子序列（A0An-2）中進(jìn)行；如果在某一趟排序中未進(jìn)行交換元素，說明子序列已經(jīng)有序，則不再進(jìn)行下一趟排序。程序流程圖：開始i=n-1i>0last=0;j=0j<iAj+1<AjSwap(Aj,Aj+1)Last=ji=last結(jié)束NNYY快速排序：取第一個(gè)元素作為分割元素，初始化i=left,j=right+1,i從左往右尋找第一個(gè)大于等于分割元素的元素，j從右往左找第一個(gè)小于等于分割元素的元素并交換，i和j繼續(xù)移動(dòng)，重復(fù)上述步驟，直到當(dāng)i>=j時(shí)將j與第一個(gè)元素交換。程序流程圖：開始left<righti=left

5、;j=righti+Ai<Aleftj-Aj>Alefti<jSwap(Ai,Aj)i<jSwap(Aleft,Aj)Qsort(A,left,j-1)Qsort(A,j+1,right)結(jié)束NYYNYNNYYN兩路合并排序：將有n 個(gè)元素的序列看成是n個(gè)長(zhǎng)度為1的有序子序列，然后兩兩合并子序列，得到n/2個(gè)長(zhǎng)度為2或1的有序子序列，再兩兩合并直到得到一個(gè)長(zhǎng)度為n的有序序列時(shí)結(jié)束。程序流程圖：開始int size=1Size<ni1=1i1+size<ni2=i1+sizej1=i2-1i2+size-1>n-1j2=n-1Merge(A,i1,j1,

6、i2,j2)i1=j2+1size*=2結(jié)束j2=i2+size-1NYYNNY四、程序代碼selectsort.h#include <iostream.h>/簡(jiǎn)單選擇排序template <class T>void SelectSort(T A, int n) int small;for (int i=0; i<n-1; i+) small=i;for(int j=i+1;j<n;j+)if(Aj<Asmall)small=j;Swap(Ai,Asmall);Insertsort.h#include <iostream.h>/直接插入排序

7、template <class T>void InsertSort(T A, int n) for(int i=1; i<n; i+) 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&

8、lt;i;j+) if(Aj+1<Aj) Swap(Aj,Aj+1); last=j; i=last; Quicksort.h#include <iostream.h>/改進(jìn)的快速排序template<class T>void quick(T A,int n)int *a; int top=0,right,left,j; a=new intn;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

9、); if(right-left<15)InsertSortExt(A,left,right); elseatop+=left; atop+=QuickSort(A,left,right)-1;atop+=atop-2+2;atop+=right; template<class T>int QuickSort(T A,int left,int right) 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

10、,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+) int j=i;T temp=Ai; while (j>0 && temp<Aj-1) Aj=Aj-1; j-; Aj=temp; Mergesort.h#include <iostream.h>/兩路合并的C+程序template <class T

11、>void Merge(T A,int i1,int j1,int i2,int j2) T *Temp=new Tj2-i1+1; int i=i1,j=i2,k=0; 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 Merge

12、Sort(T A, int n)int i1,j1,i2,j2; int size=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;Meau.h#include <iostream.h>#include <stdio.h>#include <stdlib.h>#include <time.h>#include

13、"selectsort.h"#include "insertsort.h"#include "bubblesort.h"#include "quicksort.h"#include "mergesort.h"#define SIZE 400#define TIMES 1000template <class T>class Menupublic:void printmenu();void selectsort();/簡(jiǎn)單選擇排序void insertSort();/直接插入排序void

14、 bubbleSort();/冒泡排序void quickSort();/快速排序void mergeSort();/兩路合并排序void childmenu();/子菜單1void childmenu2();/子菜單2void switcha();private:int a,b,c;template <class T>void Menu<T>:printmenu()cout<<"-內(nèi)排序測(cè)試系統(tǒng)-"<<endl;cout<<" "<<endl<<endl<<

15、endl;cout<<"1.簡(jiǎn)單選擇排序"<<endl;cout<<"2.直接插入排序"<<endl;cout<<"3.冒泡排序"<<endl;cout<<"4.快速排序"<<endl;cout<<"5.兩路合并排序"<<endl;cout<<"6.退出"<<endl;this->switcha();template <c

16、lass T>void Menu<T>:childmenu()cout<<"-"<<endl;cout<<"1.最好情況"<<endl;cout<<"2.最壞情況"<<endl;cout<<"3.平均情況"<<endl;cout<<"4.返回主菜單"<<endl;cin>>b;if(b=4)this->printmenu();template

17、<class T>void Menu<T>:childmenu2()cout<<"-"<<endl;cout<<"1.原始算法"<<endl;cout<<"2.改進(jìn)算法"<<endl;cout<<"3.返回主菜單"<<endl;cin>>c;if(c=3)this->printmenu();template <class T>void Menu<T>:sw

18、itcha()/cout<<"ok"<<endl;cin>>a;switch(a)case 1:this->selectsort();break;/okcase 2:this->insertSort();break;/okcase 3:this->bubbleSort();break;/okcase 4:this->quickSort();break;/okcase 5:this->mergeSort();break;/okcase 6:exit(1);break;default:cout<<&q

19、uot;error"<<endl;this->printmenu();break;template <class T>void printout(T A,int n)/打印數(shù)組，測(cè)試時(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

20、;i+)Ai=i;return A;/順序break;case 2:for(i=SIZE;i>0;i-)Ai-1=SIZE-i;return A;/逆序break;case 3:srand(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個(gè)元素T temp=a;a=

21、b;b=temp;template <class T>void Menu<T>:bubbleSort()cout<<"冒泡排序"<<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

22、;finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;/printout(A,SIZE);cout<<"用時(shí)： "<<duration<<endl;system("pause");/delete A;this->bubbleSort();/*ok*/template <class T>void Menu<T>:insertSort()cout<<"直接插入排序"<<endl;

23、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"<<endl;for(int i=0;i<TIMES;i+)A=producedate<T>(b);InsertSort(A,SIZ

24、E);delete A;finish=clock();duration=(double)(finish-start)/CLOCKS_PER_SEC;/printout(A,SIZE);cout<<"用時(shí)： "<<duration<<endl;system("pause");/delete A;this->insertSort();template <class T>void Menu<T>:mergeSort()/this->childmenu();cout<<"

25、;合并排序"<<endl;cout<<"直接用隨機(jī)數(shù)據(jù)測(cè)試"<<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);MergeSort(A,SIZE);delete A;finish=clock();duration=(double)(finish-start)/CLOCKS_PE

26、R_SEC;/printout(A,SIZE);cout<<"用時(shí)： "<<duration<<endl;system("pause");/delete A;this->printmenu();/*ok*/template<class T>void Menu<T>:quickSort()this->childmenu2();T *A;double duration;clock_t start,finish;if(c=1)cout<<"原始快速排序"&l

27、t;<endl;cout<<"直接用隨機(jī)數(shù)據(jù)測(cè)試"<<endl;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<<"用時(shí)： "<<duration<<e

28、ndl;system("pause");this->quickSort();else if(c=2)cout<<"改進(jìn)的快速排序"<<endl;cout<<"直接用隨機(jī)數(shù)據(jù)測(cè)試"<<endl;/*A=producedate<T>(3);printout(A,SIZE);quick(A,SIZE);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;cou