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

1、實驗名稱實驗報告各種內(nèi)排序算法的實現(xiàn)及性能比較指導(dǎo)教師實驗類型設(shè)計實驗學(xué)時2實驗時間一、實驗?zāi)康暮鸵?1) 理解和掌握各種排序算法。(2) 學(xué)會比較排序方法的性能。、實驗環(huán)境(實驗設(shè)備)硬件：微型計算機軟件：Windows操作系統(tǒng)、MicrosoftVisualStudio2015三、實驗原理及內(nèi)容QSortQuickSort1A,j-1JA,0,n-1A,nA,left,rightInsertSortQSort改進的快速排序template<classT>voidQuickSort(TA,intn)IQSort(A,0,n-1);實驗報告template<classT&g

2、t;voidQSort(TA,intleft,intright)(inti,j;if(left<right)(i=left;j=right+1;if(j-i<10)如果子集合小于10個元素時改用直接插入排序InsertSort(A,j-i);elsedodoi+;while(Ai<Aleft);doj-;while(Aj>Aleft);if(i<j)Swap(Ai,Aj);while(i<j);Swap(Aleft,Aj);QSort(A,left,j-1);QSort(A,j+1,right);隨機數(shù)發(fā)生器constintN=1000;template&l

3、t;classT>voidrandomizer(T*a)Isrand(time(NULL);for(inti=0;i<N;i+)ai=rand()%10000;各內(nèi)排序時間計算函數(shù)template<classT>voidShowtime(void(*Order)(TA,intn),TA)實驗報告(doubletime;clock_tstart,end;cout<<"Totaltime-consuming:"start=clock();開始計時for(inti=0;i<1000;i+)(Order(A,N);|randomizer(A

4、);)end=clock();結(jié)束計時time=(double)(end-start)/CLOCKSPERSEC;耗時為兩者差值除以clock中每秒的值cout<<time<<endl;)/main函數(shù)中各內(nèi)排序算法調(diào)用函數(shù)計算時間的語句段簡單選擇排序時間計算cout<<"nSelectSort:"<<endl;Showtime(SelectSort,a);直接插入排序時間計算cout<<"nInsertSort:"<<endl;Showtime(InsertSort,a);冒泡排序

5、時間計算cout<<"nBubbleSort:"<<endl;Showtime(BubbleSort,a);快速排序時間計算cout<<"nQuickSort:"<<endl;Showtime(QuickSort,a);兩路合并排序時間計算cout<<"nMergeSort:"<<endl;Showtime(MergeSort,a);實驗報告測試結(jié)果如圖:HBC:WINDOW5system32cmd.exeX以下所有排序算法所用時間均是排序"0。次一個長

6、度力10Q0的隨機數(shù)組的總時間,SelectSort：Totaltime-consuming：L865InsertSort：Totaltime-consuming：04944BubbleSort:Totaltime-consuming：10.0039uickSort:Totaltime-consuming:04233MergeSort:Totaltime-consiuning：0*6S8請按任意撞繼續(xù).鮑C:WlNDOWSXsy5tem32cmd.&xeCX結(jié)果表明：速度：改進的快速排序兩路合并排序直接插入排序簡單選擇排序冒泡排序。實驗報告四、實驗小結(jié)（包括問題和解決方法、心得體會、意見與建議等）（一）實驗中遇到的主要問題及解決方法問題：InsertSort函數(shù)模版已被定義的錯誤。解決方法：百度錯誤類型得知，應(yīng)該是在main.cpp文件中調(diào)用頭文件QuickSort.h與InsertSort.h,而QuickSort.h中已經(jīng)包含了InserSort.h文件。問題：快速排序的時間反而比冒泡排序的時間長。解決方法：手工運算代碼中的兩個排序計算語句段，發(fā)現(xiàn)每次調(diào)用排序算法函數(shù)后沒有將隨機數(shù)組重新隨機生成，而冒