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

1、實驗報告實驗名稱各種內(nèi)排序算法的實現(xiàn)及性能比較指導(dǎo)教師實驗類型設(shè)計實驗學(xué)時2實驗時間一、實驗?zāi)康暮鸵螅?1） 理解和掌握各種排序算法。（ 2） 學(xué)會比較排序方法的性能。二、 實驗環(huán)境 (實驗設(shè)備 )硬件：微型計算機(jī)軟件： Windows 操作系統(tǒng)、 Microsoft Visual Studio 2015三、實驗原理及內(nèi)容QSortQuickSortA,j-1A,0,n-1A,nA,left,rightInsertSortQSort/改進(jìn)的快速排序template <class T>void QuickSort (T A , int n)QSort(A , 0, n - 1);1

2、實驗報告template <class T>void QSort(T A ,int left ,int right )int i, j;if (left < right )i = left ; j = right + 1;if (j-i < 10 )/ 如果子集合小于10個元素時改用直接插入排序InsertSort( A, j-i );else do do i+; while (A i < A left );do j-; while (A j > A left );if (i < j ) Swap(A i, A j) ; while (i < j

3、 ); Swap(A left , A j); QSort(A , left , j - 1); QSort(A , j + 1, right);/隨機(jī)數(shù)發(fā)生器const int N = 1000;template<class T>void randomizer(T* a)srand(time(NULL );for (int i = 0; i < N; i+ )ai = rand() % 10000;/各內(nèi)排序時間計算函數(shù)template<class T>void Showtime (void (* Order)(T A , int n),T A )2實驗報告do

4、uble time;clock_t start, end;cout << "Total time-consuming:"start = clock ();/ 開始計時for (int i = 0; i < 1000; i+ )Order(A , N );randomizer (A );end = clock() ;/結(jié)束計時time = ( double)(end - start) / CLOCKS_PER_SEC ;/ 耗時為兩者差值除以clock 中每秒的值cout << time << endl;/main 函數(shù)中各內(nèi)排序算法

5、調(diào)用函數(shù)計算時間的語句段/ 簡單選擇排序時間計算cout << "nSelectSort:" << endl;Showtime (SelectSort, a);/ 直接插入排序時間計算cout << "nInsertSort:" << endl;Showtime (InsertSort, a);/ 冒泡排序時間計算cout << "nBubbleSort:"<< endl;Showtime (BubbleSort, a );/ 快速排序時間計算cout <&

6、lt; "nQuickSort:"<< endl;Showtime (QuickSort, a );/ 兩路合并排序時間計算cout << "nMergeSort:"<< endl;Showtime (MergeSort, a) ;3實驗報告測試結(jié)果如圖：結(jié)果表明：速度：改進(jìn)的快速排序>兩路合并排序>直接插入排序 >簡單選擇排序>冒泡排序。4實驗報告四、實驗小結(jié) （包括問題和解決方法、心得體會、意見與建議等）( 一 ) 實驗中遇到的主要問題及解決方法問題： InsertSort函數(shù)模版已被定義的錯誤。解決方法：百度錯誤類型得知，應(yīng)該是在main.cpp文件中調(diào)用頭文件QuickSort.h與InsertSort.h，而 QuickSort.h中已經(jīng)包含了InserSort.h文件。問題：快速排序的時間反而比冒泡排序的時間長。解決方法：手工運(yùn)算代碼中的兩個排序計算語句段，發(fā)現(xiàn)每次調(diào)用排序算法函數(shù)后沒有將隨機(jī)數(shù)組重新隨機(jī)生成， 而冒泡排序