《(完整word版)數(shù)據(jù)結(jié)構(gòu)各種排序算法的課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告(c語言版)(word文檔良心出品).doc》由會員分享，可在線閱讀，更多相關(guān)《(完整word版)數(shù)據(jù)結(jié)構(gòu)各種排序算法的課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告(c語言版)(word文檔良心出品).doc（33頁珍藏版）》請?jiān)趨R文網(wǎng)上搜索。

1、滁州學(xué)院課程設(shè)計(jì)報(bào)告課程名稱： 數(shù)據(jù)結(jié)構(gòu) 設(shè)計(jì)題目： 排序算法實(shí)現(xiàn)及比較 系 別： 計(jì)算機(jī)信息工程學(xué)院 專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) 組 別： 第*組 起止日期: 12 年 5 月 1 日 12 年 6月 1 日 指導(dǎo)教師: * 計(jì)算機(jī)與信息工程學(xué)院二一二年制課程設(shè)計(jì)任務(wù)書課程設(shè)計(jì)題目排序算法實(shí)現(xiàn)將比較組長*學(xué)號20*班級*系別計(jì)算機(jī)與信息工程學(xué)院專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)組員*指導(dǎo)教師*課程設(shè)計(jì)目的加深對常見排序算法理解通過程序比較常見算法優(yōu)越性熟悉加深對數(shù)據(jù)結(jié)構(gòu)的了解及認(rèn)識課程設(shè)計(jì)所需環(huán)境Windows xp；VC+6.0課程設(shè)計(jì)任務(wù)要求實(shí)現(xiàn)常見排序算法程序化測試程序比較算法優(yōu)越性了解常見算法的實(shí)

2、際應(yīng)用課程設(shè)計(jì)工作進(jìn)度計(jì)劃序號起止日期工 作 內(nèi) 容分工情況1分析實(shí)驗(yàn)類容2分工3算法改編成程序4將子程序合并及調(diào)試數(shù)據(jù)測試及記錄5編寫報(bào)告指導(dǎo)教師簽字： 年 月 日系（教研室）審核意見：系（教研室）主任簽字： 年 月 日目 錄1.引言42.需求分析43.詳細(xì)設(shè)計(jì)43.1 直接插入排序43.2折半排序53.3 希爾排序63.4簡單選擇排序63.5堆排序63.6歸并排序73.7冒泡排序94.調(diào)試105.調(diào)試及檢驗(yàn)115.1 直接插入排序115.2折半插入排序115.3 希爾排序125.4簡單選擇排序125.5堆排序135.6歸并排序145.7冒泡排序146.測試與比較156.1調(diào)試步驟156.2

3、結(jié)論167.實(shí)驗(yàn)心得與分析168.附錄178.1直接插入排序178.2折半插入排序188.3希爾排序208.4簡單選擇排序228.5堆排序238.6歸并排序268.7冒泡排序298.8主程序301.引言 伴隨著社會的發(fā)展，數(shù)據(jù)也變得越來越龐大。如何將龐大的數(shù)據(jù)進(jìn)行很好的排序，使用戶更加方便的查找資料，成了一件越來越重要的問題。對于程序員來說，這將是一個(gè)挑戰(zhàn)。 經(jīng)常查找資料的朋友都會知道，面對海量的資料，如果其查找的資料沒有進(jìn)行排序，那么其查找資料將會是一件非常痛苦的事情。針對這一問題，我們自此通過一個(gè)課程設(shè)計(jì)來解決它。 理論上排序算法有很多種，不過本課程設(shè)計(jì)只涉及到七種算法。這七種算法共包括：

4、直接插入排序，折半插入排序，希爾排序，簡單選擇排序，堆排序，歸并排序，冒泡排序。 本課程設(shè)計(jì)通過對這七種算法的運(yùn)行情況進(jìn)行對比，選擇最優(yōu)秀的算法來提供給用戶。希望通過我們的努力能給用戶解決一些問題，帶來一些方便。2.需求分析 本課程題目是排序算法的實(shí)現(xiàn)，由于各方面的原因，本課程設(shè)計(jì)一共要設(shè)計(jì)七種排序算法。這七種算法共包括：直接插入排序，折半插入排序，希爾排序，簡單選擇排序，堆排序，歸并排序，冒泡排序。七種排序各有獨(dú)到之處，因此我們要通過各種調(diào)試分析來比較其優(yōu)劣長短。 為了小組分工的方便，我們特意把子函數(shù)寫成Header File文件。這樣操作不僅可以使小組分工更加簡潔明了，還可以方便子函數(shù)的調(diào)

5、用，更可以使寫主函數(shù)時(shí)一目了然。 為了運(yùn)行時(shí)的方便，我們將七種排序方法進(jìn)行編號，其中1為直接插入排序，2為折半插入排序，3為希爾排序，4為簡單選擇排序，5為堆排序，6為歸并排序，7為冒泡排序。通過這七種選項(xiàng)，可以讓用戶簡單明了的去選擇使用哪一種排序方法。 本課程就是通過對5組占用內(nèi)存大小不同的數(shù)據(jù)調(diào)試來測試這七種算法運(yùn)行的時(shí)間長短，從中選擇面對不同大小的文件時(shí)，哪一種算法更為快捷。 軟件環(huán)境本課程設(shè)計(jì)所用操作系統(tǒng)為Windows-XP操作系統(tǒng)，所使用的軟件為Microsoft Visual C+ 6.0；3.詳細(xì)設(shè)計(jì)3.1 直接插入排序算法思想：直接插入排序是一種最簡單的排序方法，它的基本操作

6、是將一個(gè)記錄插入到一個(gè)已排好序的有序表中，從而得到一個(gè)新的、記錄數(shù)增一的有序表。在自i-1起往前搜索的過程中，可以同時(shí)后移記錄。整個(gè)排序過程為進(jìn)行n-1趟插入，即：先將序列中的第一個(gè)記錄看成是一個(gè)有序的子序列，然后從第二個(gè)記錄起逐個(gè)進(jìn)行插入，直至整個(gè)序列變成按關(guān)鍵字非遞減有序序列為止。程序?qū)崿F(xiàn)及核心代碼的注釋：for (i = 1 ; i r.length ;+i )for(j=0;j i;+j)if(r.basei j; -i )r.basei = r.basei-1; /記錄后移r.basej = temp; /插入到正確的為位置r.baser.length =0;3.2折半排序算法思想：

7、由于折半插入排序的基本操作是在一個(gè)有序表中進(jìn)行查找和插入，這個(gè)“查找”操作可利用折半查找來實(shí)現(xiàn)，由此進(jìn)行的插入排序稱之為折半插入排序。折半插入排序所需附加存儲空間和直接插入排序相同，從時(shí)間上比較，這般插入排序僅減少了關(guān)鍵字間的比較次數(shù)，而記錄的移動次數(shù) 不變。因此，這般插入排序的時(shí)間復(fù)雜度仍為O（n2）。程序?qū)崿F(xiàn)及核心代碼的注釋：void zb(FILE *fp) /對順序表作折半插入排序for ( i = 1 ; i r.length ; i+ )temp=r.basei; /將r.basei寄存在temp中l(wèi)ow=0;high=i-1; while( low = high ) /在base

8、low到keyhigh中折 半查找有序插入的位置 m = (low+high)/2; /折半if ( temp =high+1; -j ) r.basej+1= r.basej; /記錄后移 r.basehigh+1=temp; /插入3.3 希爾排序算法思想：先將整個(gè)待排記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對全體記錄進(jìn)行一次直接插入排序。其中，子序列的構(gòu)成不是簡單的“逐段分割”，而是將分隔某個(gè)“增量”的記錄組成一個(gè)子序列。程序?qū)崿F(xiàn)及核心代碼的注釋：for(k = 0; k 10 ; k+)m = 10 - k;for( i = m ; i r.

9、length; i + )if(r.basei = 0 & temp r.basej; j -= m)r.base j + m = r.basej; /記錄后移，查找插入位置 r.base j + m = temp; /插入3.4簡單選擇排序算法思想：在要排序的一組數(shù)中，選出最小的一個(gè)數(shù)與第一個(gè)位置的數(shù)交換；然后在剩下的數(shù)當(dāng)中再找最小的與第二個(gè)位置的數(shù)交換，如此循環(huán)到倒數(shù)第二個(gè)數(shù)和最后一個(gè)數(shù)比較為止。程序?qū)崿F(xiàn)及核心代碼的注釋：for ( i = 0 ; i r.length ; i+ ) /i為排好序的數(shù)的下標(biāo)，依次往后存放排 /好序的數(shù) temp=r.basei; /將待放入排好序的數(shù)的下標(biāo)

10、的數(shù)保存 for( j = i,m = j +1 ; m r.basem) j = m; r.basei = r.basej; /把下標(biāo)為j的數(shù)與i數(shù)互換；r.basej = temp; 3.5堆排序算法思想：堆排序只需要一個(gè)記錄大小的輔助空間，每個(gè)待排序的記錄僅占有一個(gè)存儲空間。將序列所存儲的元素AN看做是一棵完全二叉樹的存儲結(jié)構(gòu)，則堆實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉結(jié)點(diǎn)的元素均不大于(或不小于)其左右孩子(若存在)結(jié)點(diǎn)的元素。算法的平均時(shí)間復(fù)雜度為O(N log N)。程序?qū)崿F(xiàn)及核心代碼的注釋：void dp(FILE *fp)for(i = r.length / 2;i =

11、 1 ; -i) /把r.base1.r.length建成大頂堆HeapAdjust(r.base,i,r.length); for(i = r.length ;i = 2 ; -i) temp = r.base1; r.base1 = r.basei; r.basei = temp;HeapAdjust(r.base,1,i-1); /將r.base1.i-1重新調(diào)整為大頂堆void HeapAdjust(char *r,int k,int m) i=k; x=ri; j=2*i; /沿key 較大的孩子節(jié)點(diǎn)向下篩選while(j=m) /j為key較大的記錄的下標(biāo) if( (jrj+1)

12、)j+;if(xrj) /插入字符比當(dāng)前的大，交換ri =rj;i = j;j *= 2;else /否則比較停止。j = m + 1;ri = x; /把字符x插入到該位置，元素插入實(shí)現(xiàn)3.6歸并排序 算法思想：先將相鄰的個(gè)數(shù)為1的每兩組數(shù)據(jù)進(jìn)行排序合并；然后對上次歸并所得到的大小為2的組進(jìn)行相鄰歸并；如此反復(fù)，直到最后并成一組，即排好序的一組數(shù)據(jù)。程序?qū)崿F(xiàn)及核心代碼的注釋：void merge(SqList6 r,int h ,int m ,int w ,SqList6 t) /對相鄰兩組數(shù)據(jù)進(jìn)行組合排序；int i,j,k;i = h ; j = m + 1; /j為合并的第二組元素的第

13、一個(gè)數(shù)位置 k =h-1； / k為存入t中的數(shù)的位置；while(i = m)&(j = w) /依次排列兩組數(shù)據(jù)k+; if(r.basei m) /第一組數(shù)據(jù)先排完的情況while(j = w) t.base+k=r.basej+;else while(i = m) t.base+k=r.basei+;void tgb(int s,int n,SqList6 r,SqList6 t) /對數(shù)據(jù)進(jìn)行每組s個(gè)數(shù)的歸并排序；int i=1; /i為要合并兩組元素的第一個(gè)數(shù)位置；while(i=(n-2*s+1) merge(r,i,i+s-1,i+2*s-1,t); /i+s-1為要合并的第一

14、組元素的最后一/數(shù)位置、i+2*s-1 為要合并的兩組元素/最后一個(gè)數(shù)位置；i=i+2*s;if(i(n-s+1) /考慮n不能被s整除，如果余下的數(shù)少于/2*s 但大于s，也就是余下的數(shù)不能湊成/兩組，湊一組有余,則把余下的數(shù)進(jìn)行組/合，并對其進(jìn)行排序； merge(r,i,i+s-1,n,t);else /如果余下的數(shù)少于s，則余下的數(shù)進(jìn)行組/合，并進(jìn)行排序；while(i=n) t.basei=r.basei+;void gb(FILE *fp) / 歸并主函數(shù)； n = r.length; SqList6 t;t.base=(char *) malloc(r.stacksize*siz

15、eof(char); /給待排序的數(shù)組t申請內(nèi)存； while(sn) /每組元素不斷增加循環(huán)進(jìn)行合并排序； tgb(s,n,r,t); / s為每組元素的個(gè)數(shù)、n為元素總個(gè)數(shù)、r /為原數(shù)組，t為待排序的數(shù)組，進(jìn)行歸并排s*=2; /序；把元素個(gè)數(shù)相同的兩組合并 并進(jìn)行重新 /定義成新的一組，此組元素個(gè)數(shù)為2*s；if(sn) tgb(s,n,t,r); s *= 2; /當(dāng)元素個(gè)數(shù)小于n時(shí)，對其進(jìn)行合并排序；else /當(dāng)元素個(gè)數(shù)大于n時(shí)，對剩下的數(shù)排序； i=0;while(i=n) r.basei=t.basei+1;i+; 3.7冒泡排序算法思想：1、先將一組未排序的數(shù)組的最后一個(gè)數(shù)

16、與倒數(shù)第二個(gè)數(shù)進(jìn)行比較，并將較小的數(shù)放于兩個(gè)數(shù)中較前的位置，然后將比較后的較小的數(shù)與倒數(shù)第三個(gè)進(jìn)行比較，依次比較到第一個(gè)數(shù)，即可得到第一個(gè)數(shù)是所有數(shù)中最小的數(shù)；2、然后再將數(shù)組的最后一個(gè)數(shù)與倒數(shù)第二個(gè)數(shù)進(jìn)行比較，并將較小的數(shù)放于兩個(gè)數(shù)中較前的位置，依次比較到第二個(gè)數(shù)，3、如此循環(huán)到只剩最后兩個(gè)比較，即得到排好序的一組數(shù)。程序?qū)崿F(xiàn)及核心代碼的注釋：for( i=0; i = i;j - ) /從后往前依次兩兩比較，較小的被調(diào)換到前面 ； if(r.basej+1 1m1.5s0.2s6.0s0.1s3m5.5s1.1s23s0.1s0.1s24s200KB-20s3.8s-0.1s1m512KB-1m14s-