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

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

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

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

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

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

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

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

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

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

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

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

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

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

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