數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告內(nèi)部排序算法比較

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告內(nèi)部排序算法比較08級(jí)計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)e10814131郭磊2010年06月13日【實(shí)驗(yàn)簡(jiǎn)介】1、 在教科書(shū)各種內(nèi)部排序算法的時(shí)間復(fù)雜度分析結(jié)果只給出了算法執(zhí)行的時(shí)間的階，或大概的執(zhí)行時(shí)間，如：直接插入排序即時(shí)間復(fù)雜度為o（n*n）2、 通過(guò)五組隨機(jī)數(shù)據(jù)、一組正序數(shù)據(jù)與一組逆序數(shù)據(jù)比較6種常用的內(nèi)部算法（起泡排序、直接插入排序、簡(jiǎn)單選擇排序、快速查找排序、希爾排序、堆排序）的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動(dòng)次數(shù)，以取得直觀感受；3、 用五組不同的長(zhǎng)度不小于100的數(shù)據(jù)進(jìn)行測(cè)試，并對(duì)測(cè)試結(jié)果作出簡(jiǎn)單的分析，對(duì)得出結(jié)果撥動(dòng)大小的進(jìn)行解釋?zhuān)弧驹O(shè)計(jì)模塊】調(diào)用調(diào)用調(diào)用heapadj

2、ust主函數(shù)生成隨機(jī)數(shù)switch函數(shù)菜單函數(shù)selectsortinsertsortbubblesortshellsortheapsortserchsortqsort根據(jù)菜單函數(shù)返回值調(diào)用相應(yīng)的操作函數(shù)【對(duì)應(yīng)模塊算法說(shuō)明】(1) 此算法程序中需要用到順序表數(shù)據(jù)類(lèi)型,數(shù)據(jù)元素的類(lèi)型定義如下:typedef structkeytype key; /關(guān)鍵字項(xiàng)redtype;typedef structredtype rmaxsize+1; /0號(hào)單元閑置或用作哨兵單元int length; /順序表長(zhǎng)度int info; /記錄關(guān)鍵字移動(dòng)次數(shù)int cmp; /關(guān)鍵字的比較次數(shù)sqlist;(2)

3、 本實(shí)驗(yàn)用到六種排序算法，一個(gè)主函數(shù)和菜單函數(shù),其中排序算法分別為起泡排序、直接插入排序、簡(jiǎn)單選擇排序、快速查找排序、希爾排序、堆排序；相應(yīng)時(shí)間復(fù)雜度分析如下：起泡排序：若待排序列為“正序”，則需進(jìn)行一趟排序在排序過(guò)程中關(guān)鍵字需進(jìn)行n-1次比較，無(wú)須移動(dòng)紀(jì)錄；若是“逆序”，則進(jìn)行n-1趟排序，需n(n-1)/2次比較，并坐等數(shù)量級(jí)的移動(dòng)，因此總的事件復(fù)雜度為o（n2）;直接插入排序 待排序紀(jì)錄是隨機(jī)的，關(guān)鍵字間的移動(dòng)次數(shù)和比較次數(shù)的平均值約為n*n/4,即時(shí)間復(fù)雜度為o（n2）;簡(jiǎn)單的選擇排序 雖然在排序過(guò)程中所需要的移動(dòng)次數(shù)較少，最小時(shí)為0，最大時(shí)為3（n-1）；但是關(guān)鍵字的比較次數(shù)總是相同

4、的，均為n(n-1)/2，因此，時(shí)間復(fù)雜度亦為o（n2）;快速排序 其平均時(shí)間是kn*n,其中n為待排序列中紀(jì)錄的個(gè)數(shù)，k為某個(gè)常數(shù)，其時(shí)間復(fù)雜度為o（n*n）；希爾排序 當(dāng)增序序列為dltak=2t-k+1-1時(shí)，時(shí)間復(fù)雜度為o（n3/2）,其中t為排序趟數(shù)，1kt2(n+1);堆排序 此排序?qū)τ诤琻個(gè)元素的序列排序時(shí)，總共進(jìn)行的關(guān)鍵字比較次數(shù)不超過(guò)4n，且在最壞的情況下，其時(shí)間復(fù)雜度為o（n*n）；算法分析如下： 冒泡排序 該算法的的思路是首先將第1個(gè)記錄的關(guān)鍵字負(fù)值給l.r0，然后用l.r0與第（i+1）個(gè)記錄的關(guān)鍵字比較,若為逆序,則交換第i與第i+1兩記錄的位置,然后讓i加1，重復(fù)以

5、上操作，直至i=n-1為止;依次進(jìn)行第二趟、第三趟作同樣的操作，直至所有的記錄按正序排列（一般需要n-1趟比較，第i趟從l.r1到l.rn-i+1依次比較，1 i n-i，比較結(jié)果是讓其中最大的記錄放在l.rn-i+1的位置）void bubblesort(sqlist *l) /冒泡排序for(i=0;ilength;i+)l-r0=l-r1;for(j=1;jr0.key=l-rj+1.key)l-rjl-rj+1; /交換兩記錄的位置elsel-r0=l-rj+1; /保證l-r0始終為較大的記錄l-rj+1=l-r0; /把最大的記錄放到祠堂排序的最高位置printf(l-rmaxsi

6、ze);/輸出排序后數(shù)組和相關(guān)數(shù)據(jù)直接插入排序 本算法的思路是，把l-r0設(shè)置為哨兵，排序時(shí)把第i個(gè)記錄復(fù)制給哨兵，并于其前的i-1個(gè)記錄進(jìn)行比較，找到第一個(gè)比起大的記錄，利用循環(huán)讓記錄后移，把其放到第一個(gè)比起大的記錄前面。void insertsort(sqlist *l) /直接插入排序for(i=2;ilength;i+)if(l-ri.key ri-1.key)l-r0 = l-ri; /復(fù)制哨兵l-ri = l-ri-1;for(j=i-2;(l-r0.key rj.key);j-)l-rj+1 = l-rj; /紀(jì)錄后移l-rj+1 = l-r0; /插入到正確位置printf(l

7、-rmaxsize);/輸出排序后數(shù)組和相關(guān)數(shù)據(jù)簡(jiǎn)單選擇排序 基本思想是在第i趟選擇排序時(shí)：通過(guò)n-i次關(guān)鍵字之間的比較，從n-i+1個(gè)記錄中選出關(guān)鍵字最小的記錄，并和第i（1 i n）個(gè)記錄交換之void selectsort(sqlist *l) / 簡(jiǎn)單選擇排序 for (i=1; ilength; +i) / 選擇第i小的記錄，并交換到位 l-r0=l-ri;j=i; for(k=i+1;klength;k+)/從l.ri.l.length中選key最小的if(l-r0.keyl-rk.key) l-r0=l-rk; j=k; if (i!=j) l.ril.rj; /與第i個(gè)記錄交換

8、 printf(l-rmaxsize);/輸出排序后數(shù)組和相關(guān)數(shù)據(jù)快速查找排序 其基本思想為，通過(guò)一趟排序?qū)判蛴涗浄指畛蓛刹糠?，其中一部分記錄的關(guān)鍵字均小于另一部分的關(guān)鍵字，再利用遞歸分別對(duì)分割所得到的子序列進(jìn)行快速排序。其中一趟快速排序的算法為：int serchsort(sqlist *l,int low,int high) /快速排序單次排序pivotkey=l-rlow.key; /樞軸紀(jì)錄關(guān)鍵字while(lowhigh) while(lowrhigh.key=pivotkey) high-;l-rlow l-rhigh; /將比樞軸紀(jì)錄小的紀(jì)錄移到底端while(lowrlow

9、.keyrhigh l-rlow; /將比樞軸紀(jì)錄大的紀(jì)錄移到高端return high; /返回樞軸所在位置遞歸算法為：void qsort(sqlist *l, int low, int high) / 快速排序 if (low high) / 長(zhǎng)度大于1 pivotloc = serchsort(l, low, high); /調(diào)用serchsort（）將l.rlow.high一分為二 qsort(l, low, pivotloc-1); /對(duì)低子表遞歸排序，pivotloc是樞軸位置 qsort(l, pivotloc+1, high); / 對(duì)高子表遞歸排序 希爾排序 基本思路是先將

10、整個(gè)待排序的記錄分割成若干個(gè)子序列進(jìn)行直接排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次全體直接插入排序void shellsort(sqlist *l,int dlta,int t) /希爾排序for(k=1;k=t;k+)dltak=(int)pow( 2, t-k+1 )-1;/double pow( double base, double exp );函數(shù)返回以參數(shù)base 為底的exp 次冪for(i=dltak+1;ilength;i+)if(l-ri.key ri-dltak.key)l-r0 = l-ri;for(j=i-dltak;j0 & (l-r0.key

11、rj.key);j-=dltak)l-rj+dltak = l-rj;l-rj+dltak = l-r0;printf(l-rmaxsize);/輸出排序后數(shù)組和相關(guān)數(shù)據(jù)堆排序 基本思想是使記錄序列按關(guān)鍵字非遞減有序排列，則再對(duì)排序的算法中先建立一個(gè)“大頂堆”，即先選得一個(gè)關(guān)鍵字為最大的記錄與序列中最后一個(gè)記錄交換，然后再對(duì)序列中前n-1記錄進(jìn)行篩選，重新將它調(diào)整為“大頂堆“，如此反復(fù)直至排序結(jié)束。void heapadjust(sqlist *l, int s, int m) / 已知l.rs.m中記錄的關(guān)鍵字除l.rs.key之外均滿足堆的定義，本函數(shù)調(diào)整l.rs的關(guān)鍵字，使l.rs.m成

12、為一個(gè)大頂堆（對(duì)其中記錄的關(guān)鍵字而言） rc = l-rs; for (j=2*s; j=m; j*=2) / 沿key較大的孩子結(jié)點(diǎn)向下篩選 if (jrj.keyrj+1.key) +j;/j為key較大記錄的下標(biāo) if (rc.key = l-rj.key) break; / rc應(yīng)插入在位置s上 l-rs = l-rj; s = j; l-rs = rc; / 插入void heapsort(sqlist *l) /堆排序for(i=l-length/2;i0;i-) /把h-r建成大頂堆 heapadjust ( l, i, l-length );for(i=l-length;i1;

13、i-)l-ri l-r1; /將堆頂記錄和當(dāng)前未經(jīng)排序子序列l(wèi).r1i中/最后一個(gè)記錄相互交換heapadjust(l, 1, i-1); / 將h.r1.i-1 重新調(diào)整為大頂堆printf(l-rmaxsize);/輸出排序后數(shù)組和相關(guān)數(shù)據(jù)菜單程序 利用do while 循環(huán)實(shí)現(xiàn)對(duì)菜單的正確選擇，并返回選擇的操作代碼int menu_select() /菜單目錄int nu;char s;printf(*n);printf(*菜單*n);printf(1.bubblesortn); /冒泡排序printf(2.insertsortn); /直接插入排序printf(3.selectsort

14、n); / 簡(jiǎn)單選擇排序printf(4.qsortn); /查找排序printf(5.shellsortn); /希爾排序printf(6.heapsortn); /堆排序printf(7.退出程序n);printf(*n);printf(請(qǐng)輸入數(shù)字：1-7 選擇相應(yīng)的排序方式或操作：n); dos=getchar();nu=(int)s-48;while(nu55);return (nu);主函數(shù) 是程序的入口，包括兩個(gè)for循環(huán)，一個(gè)用來(lái)實(shí)現(xiàn)隨機(jī)數(shù)產(chǎn)生與輸出；另一個(gè)用來(lái)實(shí)現(xiàn)菜單的選擇的連續(xù)；第二個(gè)for循環(huán)中包含一個(gè)switch循環(huán)，作用是根據(jù)菜單程序的返回值選擇相應(yīng)的操作，隨后作相應(yīng)的

15、修改使待排序數(shù)據(jù)分別為正序和逆序，以實(shí)現(xiàn)本設(shè)計(jì)的目的。void main() printf(輸出待排序的數(shù)據(jù):);for(;)switch(menu_select() /選擇相應(yīng)的排序操作case 1: bubblesort(&a);break;case 2: insertsort(&b);break;case 3: selectsort(&c);break;case 4:qsort(&l,1,l.length); break;case 5: shellsort(&d,dlta,t);break;case 6: heapsort(&e);break;case 7: exit(0);運(yùn)行結(jié)果：第

16、一組隨機(jī)數(shù)據(jù)及其運(yùn)行結(jié)果如下：第二組隨機(jī)數(shù)據(jù)及其運(yùn)行結(jié)果如下：第三組隨機(jī)數(shù)據(jù)及其運(yùn)行結(jié)果如下：第四組隨機(jī)數(shù)據(jù)及其運(yùn)行結(jié)果如下：第五組隨機(jī)數(shù)據(jù)及其運(yùn)行結(jié)果如下：第六組正序數(shù)據(jù)及其運(yùn)行結(jié)果如下： 第七組逆序數(shù)據(jù)及其運(yùn)行結(jié)果如下： 【小結(jié)與討論】表中數(shù)據(jù)為關(guān)鍵字移動(dòng)次數(shù)：bubblesortinsertsortselectsortqsortshellsortheapsort第一組697426906053937231082第二組706624735863827421081第三組707227335924087241075第四組706825875833687881087第五組6963278762040275

17、41085第六組99000029701136第七組4950514826502975401012下表中數(shù)據(jù)為關(guān)鍵字比較次數(shù)：bubblesortinsertsortselectsortqsortshellsortheapsort第一組495025044950638785749第二組495022934950635790752第三組495025504950600796752第四組495024044950625824748第五組495026074950621804745第六組49509949504950480811第七組4950495049504950672662有數(shù)據(jù)分析可知：無(wú)論待排序列排序如何，

18、bubblesort與selectsort兩種算法的關(guān)鍵字比較次數(shù)均為4950，即n(n-1)/2次；待排序列為隨機(jī)序列時(shí)直接插入排序的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動(dòng)平均值約為n2/4,正序時(shí)比較次數(shù)為(n-1),移動(dòng)次數(shù)為0，逆序時(shí)為n(n-1)/2次；整體看來(lái)六種排序中qsort、shellsort 、heapsort三種排序比較和移動(dòng)次數(shù)相對(duì)較少；但bubblesort、 insertsort兩種排序?qū)儆诜€(wěn)定性排序（每交換一次紀(jì)錄，關(guān)鍵字就有三次移動(dòng)紀(jì)錄）。在測(cè)試過(guò)程中，當(dāng)連續(xù)選擇一個(gè)操作時(shí)，發(fā)現(xiàn)有的排序方式的關(guān)鍵字移動(dòng)次數(shù)會(huì)隨之增加，例如bubblesort，qsort，heapsort；

19、仔細(xì)分析后得知，無(wú)論待排序列是否排好，它每次運(yùn)行都會(huì)有關(guān)鍵字的移動(dòng)；每次運(yùn)行程序，六種排序方式的關(guān)鍵字比較次數(shù)也會(huì)隨著操作次數(shù)的增加而增加，原因與上一個(gè)問(wèn)題先同?！境绦蚯鍐巍?include#include#include#include #include#define maxsize 100typedef int keytype; /定義關(guān)鍵字的整數(shù)類(lèi)型typedef structkeytype key; /關(guān)鍵字項(xiàng)redtype;typedef structredtype rmaxsize+1; /0號(hào)單元閑置或用作哨兵單元int length; /順序表長(zhǎng)度int info; /記錄關(guān)鍵

20、字移動(dòng)次數(shù)int cmp; /關(guān)鍵字的比較次數(shù)sqlist;/*/void bubblesort(sqlist *l) /冒泡排序int i,j;int n=l-length;for(i=0;ilength;i+)l-r0=l-r1;for(j=1;jr0.key=l-rj+1.key)l-rj=l-rj+1;l-info+;elsel-rj=l-r0;l-r0=l-rj+1;l-info+=2;l-cmp+;l-rj+1=l-r0;printf(以下數(shù)據(jù)的排列順序?yàn)閎ubblesort排序后的排列順序：n);for(i=1;iri);/輸出排序后數(shù)組和相關(guān)數(shù)據(jù)printf(關(guān)鍵字移動(dòng)次數(shù)為：

21、%dn,l-info);printf(關(guān)鍵字比較次數(shù)為：%dn,l-cmp);/*/void insertsort(sqlist *l) /直接插入排序int i,j;for(i=2;ilength;i+)l-cmp+;if(l-ri.key ri-1.key)l-r0 = l-ri; /復(fù)制哨兵l-ri = l-ri-1;l-info+=2;for(j=i-2;(l-r0.key rj.key);j-)l-rj+1 = l-rj; /紀(jì)錄后移l-info+;l-cmp+;l-rj+1 = l-r0; /插入到正確位置l-info+;printf(以下數(shù)據(jù)的排列順序?yàn)閕nsertsort排序后

22、的排列順序：n);for(i=1;ilength;i+)printf(%dt,l-ri);/輸出排序后數(shù)組和相關(guān)數(shù)據(jù)printf(關(guān)鍵字移動(dòng)次數(shù)為：%dn,l-info);printf(關(guān)鍵字比較次數(shù)為：%dn,l-cmp);/*/void selectsort(sqlist *l) / 簡(jiǎn)單選擇排序 int i,j,k; for (i=1; ilength; +i) / 選擇第i小的記錄，并交換到位 l-r0=l-ri;j=i; for(k=i+1;klength;k+) / 在l.ri.l.length中選key最小者 l-cmp+; if(l-r0.keyl-rk.key) l-r0=l

23、-rk; j=k; l-info+; if (i!=j) / l.ril.rj; 與第i個(gè)記錄交換 redtype temp; temp=l-ri; l-ri=l-rj; l-rj=temp; l-info+=3; printf(以下數(shù)據(jù)的排列順序?yàn)閟electsort排序后的排列順序：n);for(i=1;ilength;i+)printf(%dt,l-ri);/輸出排序后數(shù)組和相關(guān)數(shù)據(jù)printf(關(guān)鍵字移動(dòng)次數(shù)為：%dn,l-info);printf(關(guān)鍵字比較次數(shù)為：%dn,l-cmp);/*/int serchsort(sqlist *l,int low,int high) /查找排

24、序單次排序int pivotkey;l-r0 = l-rlow;pivotkey=l-rlow.key; /樞軸紀(jì)錄關(guān)鍵字while(lowhigh) while(lowrhigh.key=pivotkey)high-;l-cmp+;l-rlow = l-rhigh; /將比樞軸紀(jì)錄小的紀(jì)錄移到底端l-info+;while(lowrlow.keycmp+;l-rhigh = l-rlow; /將比樞軸紀(jì)錄大的紀(jì)錄移到高端l-info+;l-rlow = l-r0;l-info+;return high;void qsort(sqlist *l, int low, int high) / 快速

25、排序 int pivotloc; if (low high) / 長(zhǎng)度大于1 pivotloc = serchsort(l, low, high); / 將l.rlow.high一分為二 qsort(l, low, pivotloc-1); / 對(duì)低子表遞歸排序，pivotloc是樞軸位置 qsort(l, pivotloc+1, high); / 對(duì)高子表遞歸排序 /*/void shellsort(sqlist *l,int dlta,int t) /希爾排序int i,k,j;for(k=1;k=t;k+)dltak=(int)pow( 2, t-k+1 )-1;/double pow(

26、 double base, double exp );函數(shù)返回以參數(shù)base 為底的exp 次冪for(i=dltak+1;ilength;i+)l-cmp+;if(l-ri.key ri-dltak.key)l-r0 = l-ri;l-info+;for(j=i-dltak;j0 & (l-r0.keyrj.key);j-=dltak)l-cmp+;l-rj+dltak = l-rj;l-info+;l-rj+dltak = l-r0;l-info+;printf(以下數(shù)據(jù)的排列順序?yàn)閟hellsort排序后的排列順序：n);for(i=1;ilength;i+)printf(%dt,l-r

27、i);/輸出排序后數(shù)組和相關(guān)數(shù)據(jù)printf(關(guān)鍵字移動(dòng)次數(shù)為：%dn,l-info);printf(關(guān)鍵字比較次數(shù)為：%dn,l-cmp);/*/void heapadjust(sqlist *l, int s, int m) / 已知l.rs.m中記錄的關(guān)鍵字除l.rs.key之外均滿足堆的定義，本函數(shù)調(diào)整l.rs的關(guān)鍵字，使l.rs.m成為一個(gè)大頂堆（對(duì)其中記錄的關(guān)鍵字而言） int j; redtype rc; rc = l-rs; l-info+; for (j=2*s; jcmp+; if (jrj.keyrj+1.key) +j; / j為key較大的記錄的下標(biāo) l-cmp+;

28、if (rc.key = l-rj.key) break; / rc應(yīng)插入在位置s上 l-rs = l-rj; l-info+; s = j; l-rs = rc; / 插入 l-info+;void heapsort(sqlist *l) /堆排序int i;redtype rc;for(i=l-length/2;i0;i-) /把h-r建成大頂堆 heapadjust ( l, i, l-length );for(i=l-length;i1;i-)rc = l-ri;l-ri = l-r1;l-r1 = rc;l-info+=3;heapadjust(l, 1, i-1); / 將h.r1

29、.i-1 重新調(diào)整為大頂堆printf(以下數(shù)據(jù)的排列順序?yàn)閔eapsort排序后的排列順序：n);for(i=1;ilength;i+)printf(%dt,l-ri);/輸出排序后數(shù)組和相關(guān)數(shù)據(jù)printf(關(guān)鍵字移動(dòng)次數(shù)為：%dn,l-info);printf(關(guān)鍵字比較次數(shù)為：%dn,l-cmp);/*/int menu_select() /菜單目錄int nu;char s;printf(*n);printf(*菜單*n);printf(1.bubblesortn); /冒泡排序printf(2.insertsortn); /直接插入排序printf(3.selectsortn); / 簡(jiǎn)單選擇排序printf(4.qsorttn); /快速查找排序printf(5.shellsortn); /希爾排序printf(6.heapsortn); /堆排序printf(7.退出程序n);printf(*n);printf(請(qǐng)輸入數(shù)字：1-7 選擇相應(yīng)的排序方式或操作：n); dos=getchar();nu=(int)s-48;while(nu55);return (nu);/*/void main()sqlist l,a,b,c,d,e; int i,dltamaxsize;int t=(int)(log(maxsize+1)/