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

1、實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱各種內(nèi)排序算法的實(shí)現(xiàn)及性能比較指導(dǎo)教師實(shí)驗(yàn)類型設(shè)計(jì)實(shí)驗(yàn)學(xué)時(shí)2實(shí)驗(yàn)時(shí)間一、實(shí)驗(yàn)?zāi)康暮鸵螅?1） 理解和掌握各種排序算法。（ 2） 學(xué)會比較排序方法的性能。二、 實(shí)驗(yàn)環(huán)境 (實(shí)驗(yàn)設(shè)備 )硬件：微型計(jì)算機(jī)軟件： Windows 操作系統(tǒng)、 Microsoft Visual Studio 2015三、實(shí)驗(yàn)原理及內(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、實(shí)驗(yàn)報(bào)告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個(gè)元素時(shí)改用直接插入排序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í)間計(jì)算函數(shù)template<class T>void Showtime (void (* Order)(T A , int n),T A )2實(shí)驗(yàn)報(bào)告do

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

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

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