課程設(shè)計(jì)報(bào)告---排序算法的實(shí)現(xiàn)與比較

1、<p>　　《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告</p><p>　　題目：排序算法的實(shí)現(xiàn)與比較</p><p><b>　　目錄</b></p><p>　　設(shè)計(jì)內(nèi)容和要求----------------------------------2</p><p>　　算法思想-----------------------

2、--------------------2</p><p>　　程序結(jié)構(gòu)-------------------------------------------3</p><p>　　使用說(shuō)明-------------------------------------------4</p><p>　　測(cè)試結(jié)果------------------------------

3、-------------5</p><p>　　收獲與體會(huì)----------------------------------------6</p><p><b>　　設(shè)計(jì)內(nèi)容和要求</b></p><p>　　設(shè)計(jì)內(nèi)容：排序算法的實(shí)現(xiàn)與比較</p><p>　　要求：編程實(shí)現(xiàn)希爾、快速、堆排序、歸并排序算法，并利用

4、程序統(tǒng)計(jì)每種算法的執(zhí)行時(shí)間。要求隨機(jī)產(chǎn)生10000、50000、 100000、 200000個(gè)待排數(shù)據(jù)存入磁盤(pán)文件，從磁盤(pán)文件讀入待排數(shù)據(jù)進(jìn)行排序，并將排序結(jié)果寫(xiě)入另一個(gè)文件中。</p><p><b>　　算法思想</b></p><p>　　在本課題中，對(duì)常見(jiàn)的4 中排序算法希爾、快速、堆排序、歸并排序進(jìn)行實(shí)現(xiàn)，并根據(jù)待排數(shù)據(jù)個(gè)數(shù)的不同來(lái)對(duì)各種排序算法的執(zhí)行時(shí)間

5、進(jìn)行比較，從而比較出在不同的情況下各排序算法的性能。</p><p><b>　　希爾排序</b></p><p>　　希爾排序是對(duì)直接插入排序的一種改進(jìn)，它的基本思想是：</p><p>　　先將整個(gè)待排序記錄序列分割成若干個(gè)子序列，在子序列內(nèi)分別進(jìn)行直接插入排序，待整個(gè)序列基本有序時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。</p>

6、<p><b>　　快速排序</b></p><p>　　快速排序是對(duì)氣泡排序的一種改進(jìn)，其基本思想是：首先選</p><p>　　一個(gè)軸值（即比較的基準(zhǔn)），將待排序記錄分割成獨(dú)立的兩部分，左側(cè)記錄的關(guān)鍵碼均小于或等于軸值，右側(cè)記錄的關(guān)鍵碼均大于或等于軸值，然后分別對(duì)這兩部分重復(fù)上述過(guò)程，直到整個(gè)序列有序。</p><p><

7、b>　　堆排序</b></p><p>　　堆排序是簡(jiǎn)單選擇排序的一種改進(jìn)，其基本思想是：首先將待</p><p>　　排序的記錄序列構(gòu)造成一個(gè)堆，此時(shí)，選出了堆中所有記錄的最大值即堆頂記錄，然后將它從堆中移走（通常將堆頂記錄和堆中最后一個(gè)記錄交換），并將剩余的記錄再調(diào)整成堆，這樣又找出了次大的記錄，依此類(lèi)推，直到堆中只有一個(gè)記錄。</p><p>

8、;<b>　　歸并排序</b></p><p>　　歸并排序是一種借助“歸并”進(jìn)行排序的方法，其主要思想是：將若干有序序列逐步歸并，最終歸并為一個(gè)有序序列。</p><p><b>　　計(jì)時(shí)函數(shù)</b></p><p>　　計(jì)時(shí)函數(shù)使用了Windows API 函數(shù)QueryPerformanceFrequency 和Qu

9、eryPerformanceCounter 來(lái)實(shí)現(xiàn)毫秒級(jí)的計(jì)時(shí)功能。該函數(shù)接受一個(gè)指向函數(shù)的指針參數(shù)，用于在兩次查詢(xún)機(jī)器內(nèi)部計(jì)時(shí)器的計(jì)插入所需要被計(jì)時(shí)的代碼，再降兩次查詢(xún)之差除以CPU 時(shí)鐘頻率即可得到事件執(zhí)行的精確時(shí)間。</p><p><b>　　程序結(jié)構(gòu)</b></p><p>　　說(shuō)明：本程序由main.cpp,sort.h和operate.h三部分組成。so

10、rt.h頭文件中實(shí)現(xiàn)了希爾，快速，堆排序，歸并排序；operate.h頭文件中有隨機(jī)產(chǎn)生待排數(shù)據(jù)，將數(shù)據(jù)寫(xiě)入文件，從文件讀數(shù)據(jù)，計(jì)時(shí)，輸出執(zhí)行時(shí)間的函數(shù)；main.cpp主函數(shù)調(diào)用頭文件里的函數(shù)。 </p><p><b>　　文件函數(shù)關(guān)系表</b></p><p><b>　　使用說(shuō)明</b></p><p>　　運(yùn)

11、行程序，可以看到如下：</p><p>　　瀏覽完說(shuō)明之后，會(huì)出現(xiàn)：</p><p>　　按照步驟，依次執(zhí)行程序，在按下了1之后，會(huì)出現(xiàn)：</p><p>　　程序?qū)Σ煌瑐€(gè)數(shù)的待排數(shù)據(jù)進(jìn)行排序。</p><p>　　在前幾步程序執(zhí)行完了之后，按下3，會(huì)出現(xiàn)：</p><p>　　程序顯示出每種排序算法的執(zhí)行時(shí)間。<

12、;/p><p>　　一次程序執(zhí)行完之后，可循環(huán)執(zhí)行這個(gè)程序。</p><p><b>　　測(cè)試結(jié)果</b></p><p>　　基本符合題目要求，程序能夠?qū)崿F(xiàn)希爾 快速 堆排序 歸并排序四中排序算法，并能夠統(tǒng)計(jì)每種排序算法的執(zhí)行時(shí)間。此外，能夠隨機(jī)產(chǎn)生待排數(shù)據(jù)，存入文件，從磁盤(pán)文件讀入待排數(shù)據(jù)進(jìn)行排序，并能將排序結(jié)果存入另一個(gè)文件中。</p&

13、gt;<p>　　在隨機(jī)產(chǎn)生的待排數(shù)據(jù)為10000時(shí)，算法的執(zhí)行時(shí)間分別如下：</p><p>　　在隨機(jī)產(chǎn)生的待排數(shù)據(jù)個(gè)數(shù)為50000個(gè)時(shí)：</p><p>　　在隨機(jī)產(chǎn)生的待排數(shù)據(jù)個(gè)數(shù)為100000個(gè)時(shí)：</p><p>　　在隨機(jī)產(chǎn)生的待排數(shù)據(jù)個(gè)數(shù)為200000個(gè)時(shí)：</p><p>　　下面是排序算法執(zhí)行時(shí)間與待排數(shù)據(jù)關(guān)

14、系表：</p><p>　　不同個(gè)數(shù)的隨機(jī)產(chǎn)生的待排數(shù)據(jù)的4種排序算法的執(zhí)行時(shí)間相差不是很大，在待排數(shù)據(jù)的個(gè)數(shù)是10000的時(shí)候，排序的執(zhí)行時(shí)間不是很長(zhǎng)，都是在5ms左右，在待排數(shù)據(jù)個(gè)數(shù)變多時(shí)，很明顯，希爾，堆排序比快速和歸并排序的執(zhí)行時(shí)間稍微長(zhǎng)一點(diǎn)，但是，希爾和堆排序的執(zhí)行時(shí)間相差不大。</p><p><b>　　收獲與體會(huì)</b></p><