各種排序算法時(shí)間性能的比較

1、實(shí)訓(xùn)報(bào)告實(shí)訓(xùn)題目：各種排序算法時(shí)間性能的比較學(xué) 院：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院專業(yè)：軟件工程班 級(jí)： 142學(xué)號(hào)：1400170269學(xué)生姓名： 莫磊指導(dǎo)教師：蔡麗2016年3月15日、實(shí)訓(xùn)目的及要求數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)課程的一門重要的基礎(chǔ)課，它的教學(xué)要求大致有三個(gè)重要方面:其一就是讓學(xué)生學(xué)會(huì)分析研究計(jì)算機(jī)加工的數(shù)據(jù)對(duì)象的特性，以便為數(shù)據(jù)選擇適當(dāng)?shù)?物理結(jié)構(gòu)和邏輯結(jié)構(gòu)；其二，根據(jù)結(jié)構(gòu)，選擇適當(dāng)?shù)乃惴?，并初步掌握算法的時(shí)間分 析和空間分析；其三，學(xué)習(xí)復(fù)雜的程序設(shè)計(jì)。本綜合實(shí)訓(xùn)利用Visual Studio 2008集成編程環(huán)境為實(shí)踐工具，通過上機(jī)實(shí)踐培養(yǎng)學(xué)生分析具體問題、解決實(shí)際問題的能力， 訓(xùn)練和培養(yǎng)學(xué)

2、生的數(shù)據(jù)抽象能力和程序設(shè)計(jì)的能力。數(shù)據(jù)結(jié)構(gòu)是一門實(shí)踐性較強(qiáng)的課程，以培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力和程序設(shè)計(jì)的能 力為目的。在實(shí)訓(xùn)時(shí)應(yīng)注重培養(yǎng)學(xué)生的實(shí)際操作能力。本綜合實(shí)訓(xùn)安排了18學(xué)時(shí)的實(shí)驗(yàn)課時(shí)，具體要求如下：學(xué)習(xí)和理解每個(gè)實(shí)訓(xùn)題目的基本理論和方法；掌握每個(gè)實(shí)驗(yàn)的實(shí)現(xiàn)步驟和關(guān)鍵技術(shù)；準(zhǔn)備好實(shí)驗(yàn)所需要的資源和文檔；上機(jī)實(shí)現(xiàn)程序，得到通過調(diào)試的正確程序。根據(jù)每個(gè)實(shí)驗(yàn)的不同要求，完成實(shí)驗(yàn)報(bào)告的word文檔。二、實(shí)訓(xùn)環(huán)境Win dows XPVisual Studio 2013三、實(shí)訓(xùn)內(nèi)容設(shè)計(jì)并實(shí)現(xiàn)上述各種排序算法；產(chǎn)生正序和逆序的初始排列分別調(diào)用上述排序算法，并比較時(shí)間性能；產(chǎn)生隨機(jī)的初始排列分別調(diào)用上述

3、排序算法，并比較時(shí)間性能。對(duì)各種排序方法(直接插入排序、希爾排序、起泡排序、直接選 擇排序)的時(shí)間性能進(jìn)行比較。四、算法描述及實(shí)訓(xùn)步驟上述各種排序方法都是基于比較的內(nèi)排序，其時(shí)間主要消耗在排序過 程中進(jìn)行的記錄的比較次數(shù)和移動(dòng)次數(shù)，因此，統(tǒng)計(jì)在相同數(shù)據(jù)狀態(tài)下不 同排序算法的比較次數(shù)和移動(dòng)次數(shù)，即可實(shí)現(xiàn)比較各種排序算法的目的。五、總結(jié)及心得體會(huì)直接選擇排序算法是對(duì)冒泡排序的改進(jìn)，這種方法是在參加排序數(shù)組 中找出最小（或最大）的數(shù)據(jù)元素，使它與第一個(gè)元素中的數(shù)據(jù)相互交換 位置然后再在余下的元素中找出最?。ɑ蜃畲螅┑臄?shù)據(jù)元素與第二個(gè)元素 中的元素交換位置，以此類推直到所有元素成為有序序列。六、實(shí)訓(xùn)結(jié)

4、果;輸出冒泡正序排序后數(shù)據(jù)如下01234556681111121616181821222323232426262727292929293133343535363737383S394040414141414242424444生54647474848505353545657585961622646464&667676869697071737678788182S284839090919293949595朋比較的次數(shù)為:4797移動(dòng)的次數(shù)為:g狗也曰很肚丿予徘丿予后軟瑪劉,9995949392919190908084S28281787876737170G9勺6867676b64646462626159

5、58575654535350484847474645444442424241414141404039333S37373635353433312929292927272626242323232221181816161211118665513210比較的次數(shù)為:4947移動(dòng)的枕數(shù)為汐2朋o12345566B1111121616131221222323232426262727292929293L333435353h3737383SS9404041414141424242444444647474948SO53saE4S6E7S3旳6162624B464&hH7G76HK427071737t7S7S呂1

6、22S2S4S3909091919293945595弓9比較的次數(shù)芮:gg移動(dòng)的次數(shù)漁:260Q_枱 dj 古七基燈 i 世riE-H卜rte占nR-稠出且摟曲人送廳羽F丿予后飲于劉h-gqgw32til 1DED88S432823173787&737170g208S7e?60e4G4C462626159S2S7S654S3535048484747464544414242424141414140403922383737363535343331292929曲27272626242323232221ie181616121111s6E543210比轉(zhuǎn)的次敵対：99移功的次數(shù)溝：2297:輸出肓接插.

7、人庁序排序后故抵如下輸出宜按選扌牽止序排仔后數(shù)扌居如卜Is42424248bQ-44u-3G 4 4 4 n 3 4 2 7-544321217 9a4 4 5 &8 7 5 17 呂了 135 1 3 4 4 5 6 s Q6651677 S24 12 3 4 4 5 6 7 96640566813 1 ni 3 4 4- 5 6 7 _y2 430444 6 12 1 ny- nd 4 4 5 6 7 91319434 3 01 1 ni oo 3 4 5 & 7 945411.62：4950移動(dòng)的次皴均：?jiǎn)栞敵鲋苯舆x埠逆序排序后數(shù)堀如下46474718278T-JD4：950移動(dòng)的次數(shù)為

8、：淚422Q-8OO28139823410f有排序的比較次數(shù)利移動(dòng)次數(shù)如下序序序序入入擇擇 正正z逆插插選選 爾爾泡泡接接接接 希希冒冒直直苣苣比較挨數(shù)為 比較次數(shù)為 比較次數(shù)為 比較次藪為 比較次數(shù)為 比較次數(shù)為 比較也為 比較次數(shù)為503移動(dòng)次敎為：457 503移動(dòng)次數(shù)為：457 479?移動(dòng)次數(shù)為:2旳9 4947移動(dòng)次數(shù)為恣折 99移祈次敗 :出09 99移動(dòng)次數(shù)為：2297 4950移動(dòng)次數(shù)為：94 4950移動(dòng)次數(shù)為:97七、源代碼：#i nclude #i nclude #in elude /正序希爾排序void xiEr(i nt n um, int n, int &no,

9、int &r)int item;int i, j, d;for (d = n / 2; d = 1; d = d / 2)for (i = d; i= 0) & (itemnumj) n umj + d = n umj;j = j - d;r = r + 1;n umj + d = item;no = no + 1;/prin tf(n);/for(i nt x=0;x = 1; d = d / 2)for (i = d; i= 0) & (itemnumj) n umj + d = n umj;j = j - d;r = r + 1;n umj + d = item;no = no + 1;

10、/正序冒泡排序void MaoPao(i nt n um, int n, int &no, int &r)bool flag;int test;for (i nt i = 1; i= i; j-)if (n umj numj - 1)test = n umj;n umj = n umj - 1;n umj - 1 = test;flag = false;葉+;n o+;if (flag)return;void MaoPaoUp(int num, int n, int &no, int &r) bool flag;int test;for (i nt i = 1; i= i; j-)if (n

11、umj numj - 1) test = n umj;n umj = n umj - 1; n umj - 1 = test; flag = false;葉+;n o+;if (flag)return; void ChaRu(i nt num, i nt n, i nt &n o, i nt & r) / :比較次數(shù)，r :移動(dòng)次數(shù)。int i, j, x;for (i = 1; i= 0) & (xvnumj)葉+;n umj + 1 = n umj;j-; /順序比較和移動(dòng)n umj + 1 = x; void ChaRuUp(i nt num, i nt n, i nt &n o, i

12、nt & r) /:比較次數(shù)，r :移動(dòng)次數(shù)。int i, j, x;for (i = 1; i= 0) & (x numj)直接選擇排序/:比較次數(shù),r:移動(dòng)次數(shù)直接選擇排序/:比較次數(shù),r:移動(dòng)次數(shù)葉+;n umj + 1 = n umj;j-；/順序比較和移動(dòng)n umj + 1 = x;void Xua nZe(i nt n um, int n, int &no, int &r)int x; int i, j, k;for (i = 1; i = n - 1; i+)k = i - 1;for (j = i; j = n -1; j+)n o+; if (n umj n umk) k =

13、 j;if (k != i - 1)葉+;x = n umi - 1;n umi - 1 = n umk;n umk = x;void Xua nZeUp(i nt n um, int n, int &no, int &r)/ int x; int i, j, k;for (i = 1; i = n - 1; i+)k = i - 1;for (j = i; j n umk) k = j;if (k != i - 1)葉+;x = n umi - 1;n umi - 1 = n umk;n umk = x;void ShuChu(i nt n um, int n, int no, int r,

14、 char n ame)prin tf(=輸岀 甜卡序后數(shù)據(jù)如下=nn, n ame);for (i nt x = 0; xn; x+)printf(%dt, numx);printf(n 比較的次數(shù)為:%dt移動(dòng)的次數(shù)為：d, no, r);prin tf(n=nn “); int mai n()int num100;int n = 100;int n o1, no2, no3, no4;int r1, r2, r3, r4;int no11, no22, no33, no44;int r11, r22, r33, r44;char n ame1= char n ame11= char n

15、ame2= char name22= char n ame3= char n ame33= char n ame4= char n ame44= int item1100; int item2100; int item3100; int item4100; int item22100; int item33100; int item44100;希爾正序;希爾逆序;冒泡正序;冒泡逆序;直接插入正序;直接插入逆序 直接選擇正序;直接選擇逆序no4 = no3 = no2 = no1=0;r4 = r3 = r2 = r1 = 0;no44 = no33 = no22 = no11 = 0;r44

16、= r33 = r22 = r11 = 0;prin tf(”=初始的隨機(jī)數(shù)據(jù)如下= nn); for (i nt i = 0; in; i+)numi = ran d() %100;prin tf(%dt, numi);for (i nt x = 0; xn; x+)item1x = n umx;item2x = n umx;item3x = n umx;item4x = n umx;item22 x = numx;item33x = n umx;item44x = n umx;xiEr (n um, n, n o1, r1);ShuChu( num, n, n o1, r1, n ame1

17、);xiEr(item1, n,n o11,r11);ShuChu(item1, n,n o11,r11, name11);MaoPao(item2,n, no2, r2);ShuChu(item2, n, no2, r2, name2);MaoPaoUp(item22, n, no22, r22);ShuChu(item22, n, no22, r22, name22);ChaRu(item3 ,n,n o3,r3);ShuChu(item3, n, no3, r3, name3);ChaRuUp(item33, n, no33, r33);ShuChu(item33, n, no33, r

18、33, name33);Xua nZe(item4, n, no 4, r4);ShuChu(item4, n, no4, r4, name4);XuanZeUp(item44, n, no44, r44);ShuChu(item44, n, no44, r44, name44);prin tf(=n);prin tf(=n);printf( 所有排序的比較次數(shù)和移動(dòng)次數(shù)如下：nn);printf(%s:t比較次數(shù)為：d 移動(dòng)次數(shù)為：dn, name1, no1, r1);printf(%s:t比較次數(shù)為：%d 移動(dòng)次數(shù)為：dn, name1, no11,r11);printf(%s:t比較次數(shù)為：%d 移動(dòng)次數(shù)為：dn,