實驗課程算法分析與設(shè)計

1、實驗課程：算法分析與設(shè)計 實驗名稱：幾種排序算法的平均性能比較 （驗證型實驗）實驗?zāi)繕耍海?） 幾種排序算法在平均情況下哪一個更快。（2） 加深對時間復(fù)雜度概念的理解。實驗任務(wù)：（1）實現(xiàn)幾種排序算法（selectionsort, insertionsort,bottomupsort,quicksort, 堆排序）。對于快速分類，SPLIT中的劃分元素采用三者A(low)，A(high)，A(low+high)/2)中其值居中者。（2）隨機產(chǎn)生20組數(shù)據(jù)（比如n=5000i，1i20）。數(shù)據(jù)均屬于范圍（0，105）內(nèi)的整數(shù)。對于同一組數(shù)據(jù)，運行以上幾種排序算法，并記錄各自的運行時間（以毫秒為單

2、位）。（3）根據(jù)實驗數(shù)據(jù)及其結(jié)果來比較這幾種分類算法的平均時間和比較次數(shù)，并得出結(jié)論。實驗設(shè)備及環(huán)境：PC；C/C+等編程語言。實驗主要步驟：(1) 明確實驗?zāi)繕撕途唧w任務(wù)；(2) 理解實驗所涉及的幾個分類算法；(3) 編寫程序?qū)崿F(xiàn)上述分類算法；(4) 設(shè)計實驗數(shù)據(jù)并運行程序、記錄運行的結(jié)果；(5) 根據(jù)實驗數(shù)據(jù)及其結(jié)果得出結(jié)論；(6) 實驗后的心得體會。問題分析（包括問題描述、建模、算法的基本思想及程序?qū)崿F(xiàn)的技巧等）：本實驗采用Microsoft Visual Studio 2008實現(xiàn)（由于采用CString的MakeReverse()函數(shù)將最后的周游路徑輸出是格式及數(shù)據(jù)發(fā)生了變化，所以請

3、原諒，我沒將其從頭到尾輸入，而是從尾到頭輸出，我知道要實現(xiàn)從頭到尾輸入是比較容易實現(xiàn)的，鑒于某些原因，我就沒實現(xiàn)了，在此請老師諒解）本算法，采用遞歸的方式，同時運用到STL的stack來實現(xiàn)回溯?；局苡嗡悸肥欠?個方向進行，如果可以，最終找到解，輸出。本實驗棋盤大小采用宏定義，可由用戶進行修改其大小。#define N 5#define M 5框架設(shè)計如下圖：開始是否合法起點？ 周游成功否？否是 輸出退出？ 結(jié)束是輸入？否是 是是重輸？是否8種周游方式進行遞歸選擇實驗數(shù)據(jù)及其結(jié)果（可用圖表形式給出）：N*M=5*5時N*M=6*6時當N*M=8*8時實驗結(jié)果分析及結(jié)論：當為奇數(shù)矩陣時出現(xiàn)可能沒有通路的結(jié)果。其他的正常實驗自我評價及心得體會：此算法好像效率不高，當為8*8時，就出現(xiàn)耗時很長，不知是否我的邏輯錯誤，又很難找，請老師給予指點，