各種排序算法時間性能的比較.doc

《各種排序算法時間性能的比較.doc》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。

1、實訓報告實訓題目：各種排序算法時間性能的比較學院：計算機科學與技術(shù)學院專業(yè)：軟件工程班級：142學號：1400170269學生：莫磊指導教師：蔡麗2016年3月15日一、實訓目的及要求數(shù)據(jù)結(jié)構(gòu)是計算機課程的一門重要的基礎課，它的教學要求大致有三個重要方面：其一就是讓學生學會分析研究計算機加工的數(shù)據(jù)對象的特性，以便為數(shù)據(jù)選擇適當?shù)奈锢斫Y(jié)構(gòu)和邏輯結(jié)構(gòu)；其二，根據(jù)結(jié)構(gòu)，選擇適當?shù)乃惴ǎ⒊醪秸莆账惴ǖ臅r間分析和空間分析；其三，學習復雜的程序設計。本綜合實訓利用VisualStudio2008集成編程環(huán)境為

2、實踐工具，通過上機實踐培養(yǎng)學生分析具體問題、解決實際問題的能力，訓練和培養(yǎng)學生的數(shù)據(jù)抽象能力和程序設計的能力。數(shù)據(jù)結(jié)構(gòu)是一門實踐性較強的課程，以培養(yǎng)學生的數(shù)據(jù)抽象能力和程序設計的能力為目的。在實訓時應注重培養(yǎng)學生的實際操作能力。本綜合實訓安排了18學時的實驗課時，具體要求如下：1.學習和理解每個實訓題目的基本理論和方法；2.掌握每個實驗的實現(xiàn)步驟和關鍵技術(shù)；3.準備好實驗所需要的資源和文檔；4.上機實現(xiàn)程序，得到通過調(diào)試的正確程序。5.根據(jù)每個實驗的不同要求，完成實驗報告的word文檔。二、實訓環(huán)境

3、WindowsXPVisualStudio2013三、實訓容(1)設計并實現(xiàn)上述各種排序算法；(2)產(chǎn)生正序和逆序的初始排列分別調(diào)用上述排序算法，并比較時間性能；(3)產(chǎn)生隨機的初始排列分別調(diào)用上述排序算法，并比較時間性能。（4）對各種排序方法（直接插入排序、希爾排序、起泡排序、直接選擇排序）的時間性能進行比較。四、算法描述及實訓步驟上述各種排序方法都是基于比較的排序，其時間主要消耗在排序過程中進行的記錄的比較次數(shù)和移動次數(shù)，因此，統(tǒng)計在相同數(shù)據(jù)狀態(tài)下不同排序算法的比較次數(shù)和移動次數(shù)，即可實現(xiàn)比較各

4、種排序算法的目的。五、總結(jié)及心得體會直接選擇排序算法是對冒泡排序的改進，這種方法是在參加排序數(shù)組中找出最?。ɑ蜃畲螅┑臄?shù)據(jù)元素，使它與第一個元素中的數(shù)據(jù)相互交換位置然后再在余下的元素中找出最?。ɑ蜃畲螅┑臄?shù)據(jù)元素與第二個元素中的元素交換位置，以此類推直到所有元素成為有序序列。六、實訓結(jié)果七、源代碼：#include#include#include//正序希爾排序voidxiEr(intnum[],intn,int&no,int&r){intite

5、m;inti,j,d;for(d=n/2;d>=1;d=d/2){for(i=d;i=0)&&(item

6、no,int&r){intitem;inti,j,d;for(d=n/2;d>=1;d=d/2){for(i=d;i=0)&&(item>num[j])){num[j+d]=num[j];j=j-d;r=r+1;}num[j+d]=item;no=no+1;}}}//正序冒泡排序voidMaoPao(intnum[],intn,int&no,int&r){boolflag;inttest;for(inti=1;i

7、lag=true;for(intj=n-1;j>=i;j--){if(num[j]=i;j--){if(num

8、[j]>num[j-1]){test=num[j];num[j]=num[j-1];num[j-1]=test;flag=false;r++;}no++;}if(flag){return;}}}voidChaRu(intnum[],intn,int&no,int&r)//直接插入排序{//:比較次數(shù)，r:移動次數(shù)。inti,j,x;for(i=1;i=0)&&(x