數(shù)據(jù)結(jié)構(gòu)各種排序?qū)嶒?yàn)報(bào)告

1、目 錄1.引言42.需求分析43.詳細(xì)設(shè)計(jì)43.1 直接插入排序43.2折半排序53.3 希爾排序63.4簡(jiǎn)單選擇排序63.5堆排序63.6歸并排序73.7冒泡排序94.調(diào)試105.調(diào)試及檢驗(yàn)115.1 直接插入排序115.2折半插入排序115.3 希爾排序125.4簡(jiǎn)單選擇排序125.5堆排序135.6歸并排序145.7冒泡排序146.測(cè)試與比較156.1調(diào)試步驟156.2結(jié)論167.實(shí)驗(yàn)心得與分析168.附錄178.1直接插入排序178.2折半插入排序188.3希爾排序208.4簡(jiǎn)單選擇排序228.5堆排序238.6歸并排序268.7冒泡排序298.8主程序301.需求分析 課程題目是排序

2、算法的實(shí)現(xiàn)，課程設(shè)計(jì)一共要設(shè)計(jì)八種排序算法。這八種算法共包括：堆排序，歸并排序，希爾排序，冒泡排序， 快速排序，基數(shù)排序，折半插入排序，直接插入排序。 為了運(yùn)行時(shí)的方便，將八種排序方法進(jìn)行編號(hào)，其中1為堆排序，2為歸并排序，3為希爾排序，4為冒泡排序，5為快速排序，6為基數(shù)排序，7為折半插入排序8為直接插入排序。 軟件環(huán)境： windows-7操作系統(tǒng)，所使用的軟件為c-free；2.概要設(shè)計(jì) 2.1 直接插入排序算法思想：直接插入排序是一種最簡(jiǎn)單的排序方法，它的基本操作是將一個(gè)記錄插入到一個(gè)已排好序的有序表中，從而得到一個(gè)新的、記錄數(shù)增一的有序表。在自i-1起往前搜索的過(guò)程中，可以同時(shí)后移記

3、錄。整個(gè)排序過(guò)程為進(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 < r.basej)temp = r.basei; /保存待插入記錄for(i= i ;i > j; -i )r.basei = r.basei-1; /記錄后移r.basej = temp; /插入到正確的為位置r.baser.length ='0'2

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

5、 <= high ) /在baselow到keyhigh中折 半查找有序插入的位置 m = (low+high)/2; /折半if ( temp < r.basem )high = m-1; /插入低半?yún)^(qū)elselow = m+1; /插入高半?yún)^(qū)for( j=i-1; j>=high+1; -j ) r.basej+1= r.basej; /記錄后移 r.basehigh+1=temp; /插入2.3 希爾排序算法思想：先將整個(gè)待排記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。其中，子序列的構(gòu)成不是簡(jiǎn)單的“

6、逐段分割”，而是將分隔某個(gè)“增量”的記錄組成一個(gè)子序列。程序?qū)崿F(xiàn)及核心代碼的注釋：for(k = 0; k < 10 ; k+)m = 10 - k;for( i = m ; i < r.length; i + )if(r.basei < r.basei - m) temp = r.basei; /保存待插記錄 for(j = i - m ; j >= 0 && temp < r.basej; j -= m)r.base j + m = r.basej; /記錄后移，查找插入位置 r.base j + m = temp; /插入2.4簡(jiǎn)單選擇排序算

7、法思想：在要排序的一組數(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)的數(shù)保存 for( j = i,m = j +1 ; m < r.length ; m+) /找出未排序的數(shù)中最小的數(shù)的循環(huán)；if(r.basej > r.basem) j = m; r.basei = r.basej;

8、/把下標(biāo)為j的數(shù)與i數(shù)互換；r.basej = temp; 2.5堆排序算法思想：堆排序只需要一個(gè)記錄大小的輔助空間，每個(gè)待排序的記錄僅占有一個(gè)存儲(chǔ)空間。將序列所存儲(chǔ)的元素an看做是一棵完全二叉樹的存儲(chǔ)結(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 >= 1 ; -i) /把r.base1.r.length建成大頂堆heapadjust(r.base,i,r.length

9、); 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( (j<m) && (rj>rj+1) )j+;if(x>rj) /插入字符比當(dāng)前的大，

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

11、的數(shù)的位置；while(i <= m)&&(j <= w) /依次排列兩組數(shù)據(jù)k+; if(r.basei <= r.basej) /將第一組數(shù)據(jù)與第二組數(shù)據(jù)分別比較；t.basek = r.basei+;elset.basek = r.basej+; if(i > 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) /對(duì)數(shù)據(jù)進(jìn)行每組s個(gè)數(shù)的歸并

12、排序；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為要合并的第一組元素的最后一/數(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)行組/合，并對(duì)其進(jìn)行排序； merge(r,i,i+s-1,n,t);else /如果余下的數(shù)少于s，則余下的數(shù)進(jìn)行組/合，并進(jìn)行排序；while(i<=n) t.bas

13、ei=r.basei+;void gb(file *fp) / 歸并主函數(shù)； n = r.length; sqlist6 t;t.base=(char *) malloc(r.stacksize*sizeof(char); /給待排序的數(shù)組t申請(qǐng)內(nèi)存； while(s<n) /每組元素不斷增加循環(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(s<n) tgb(s,n,t,r); s *= 2; /當(dāng)元

14、素個(gè)數(shù)小于n時(shí)，對(duì)其進(jìn)行合并排序；else /當(dāng)元素個(gè)數(shù)大于n時(shí)，對(duì)剩下的數(shù)排序； i=0;while(i<=n) r.basei=t.basei+1;i+; 2.7冒泡排序算法思想：1、先將一組未排序的數(shù)組的最后一個(gè)數(shù)與倒數(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 &

15、lt; r.length ;i+ ) / i為排好序的數(shù)的下標(biāo)，依次往后存放排好序的數(shù)； for( j = r.length-2;j >= i;j - ) /從后往前依次兩兩比較，較小的被調(diào)換到前面 ； if(r.basej+1 < r.basej) /比較相鄰兩個(gè)數(shù)，如果后面的小于前面的，向下執(zhí)行； temp = r.basej+1; /將后面的較小的數(shù)保存起來(lái)；r.basej+1 = r.basej; /將前面的較大的數(shù)放在后面較小的數(shù)的位置；r.basej = temp; /將較小的數(shù)放在前面的較大的數(shù)的位置； 3.調(diào)試檢測(cè)主函數(shù)是否能夠穩(wěn)定運(yùn)行(如圖4-1)：圖4-15.調(diào)

16、試及檢驗(yàn)5.1 直接插入排序輸入字符并保存（如圖5-1.1）：調(diào)用算法【1】處理文件（如圖5-1.2）：處理結(jié)果（如圖5-1.3）：圖5-1.1 圖5-1.2圖5-1.35.2折半插入排序輸入字符并保存（如圖5-2.1）：調(diào)用算法【2】處理文件（如圖5-2.2）：處理結(jié)果（如圖5-2.3）：圖5-2.1 圖5-2.2圖5-2.35.3 希爾排序輸入字符并保存（如圖5-3.1）：調(diào)用算法【3】處理文件（如圖5-3.2）：處理結(jié)果（如圖5-3.3）：圖5-3.1 圖5-3.2圖5-3.35.4簡(jiǎn)單選擇排序輸入字符并保存（如圖5-4.1）：調(diào)用算法【4】處理文件（如圖5-4.2）：處理結(jié)果（如圖5-

17、4.3）：圖5-4.1 圖5-4.2圖5-4.35.5堆排序輸入字符并保存（如圖5-5.1）：調(diào)用算法【5】處理文件（如圖5-5.2）：處理結(jié)果（如圖5-5.3）：圖5-5.1 圖5-5.2圖5-5.35.6歸并排序輸入字符并保存（如圖5-6.1）：調(diào)用算法【6】處理文件（如圖5-6.2）：處理結(jié)果（如圖5-6.3）：圖5-6.1 圖5-6.2圖5-6.35.7冒泡排序輸入字符并保存（如圖5-7.1）：調(diào)用算法【7】處理文件（如圖5-7.2）：處理結(jié)果（如圖5-7.3）：圖5-7.1 圖5-7.2圖5-7.36.2結(jié)論 通過(guò)實(shí)驗(yàn)結(jié)果的比較與分析我們發(fā)現(xiàn)：直接插入排序、冒泡排序、簡(jiǎn)單選擇排序及折

18、半插入排序是低效率的排序方式；所以我們實(shí)際編程重要盡可能的避免他們的出現(xiàn)；我們應(yīng)該用較先進(jìn)的歸并排序及堆排序。7.實(shí)驗(yàn)心得與分析 通過(guò)本次課程設(shè)計(jì)，我們小組的每個(gè)成員都學(xué)到了很多東西。首先要說(shuō)的是我們的編程能力，在這一次的課程設(shè)計(jì)中我們的編程能力均得到了一定程度的提升。并且通過(guò)這次課程設(shè)計(jì)，我們更加熟悉了如何使用header file文件。本次課程設(shè)計(jì)，讓我們對(duì)于直接插入排序，折半插入排序，希爾排序，簡(jiǎn)單選擇排序，堆排序，歸并排序，冒泡排序等七種排序算法的思想有了進(jìn)一步的認(rèn)識(shí)，同時(shí)對(duì)七種算法的應(yīng)用有了更進(jìn)一步的掌握。通過(guò)這次課程設(shè)計(jì)，我們對(duì)于解決實(shí)際問(wèn)題的能力有了進(jìn)一步提高。最重要的是，這次課

19、程設(shè)計(jì)大大的訓(xùn)練了我們的小組團(tuán)隊(duì)協(xié)作能力。通過(guò)這次課程設(shè)計(jì)我們小組各成員的團(tuán)隊(duì)協(xié)作能力都有了很大的提升。這種團(tuán)隊(duì)協(xié)作能力對(duì)于我們學(xué)編程的來(lái)說(shuō)是極其重要的，同時(shí)也是必不可少的。 當(dāng)然，我們寫程序的時(shí)候遇到了很多困難。而且在程序調(diào)試過(guò)程中出現(xiàn)了很多錯(cuò)誤與警告，不過(guò)在隊(duì)員及老師的幫助下均得到了解決。當(dāng)程序可以運(yùn)行后，程序的運(yùn)行過(guò)程中同樣也也出現(xiàn)了很多錯(cuò)誤，甚至出現(xiàn)了不兼容的情況。不過(guò)，后來(lái)在隊(duì)員及老師的幫助下也均得到了解決。然而，我們的程序還有一點(diǎn)瑕疵讓我們感到美中不足。那就是在歸并算法運(yùn)行過(guò)程中，當(dāng)輸入為9個(gè)字符時(shí)，排序結(jié)果會(huì)出現(xiàn)偶然誤差。經(jīng)過(guò)分析，我們認(rèn)為這點(diǎn)是系統(tǒng)的問(wèn)題。不過(guò)，這仍然是一點(diǎn)讓我

20、們感到遺憾的地方。8.附錄8.1直接插入排序#include<stdio.h>#include<stdlib.h>#define q 1000typedef struct char *base ; int stacksize ; int length;sqlist1; void zj(file *fp) sqlist1 r;int i,j;char temp,*p; r.base=(char *) malloc(q*sizeof(char);r.stacksize = q;r.length = 0; while(!feof(fp)fscanf(fp,"%c&q

21、uot;,r.base); r.base+;r.length+;if(r.length = r.stacksize )r.base= r.base - r.length;r.base=(char *) realloc(r.base,(r.stacksize + q) * sizeof(char);if(!r.base)printf("error");return ; r.base = r.base + r.stacksize;r.stacksize += q; r.length -;r.base -;r.base= r.base - r.length;for (i = 1

22、; i < r.length ;+i )for(j=0;j < i;+j)if(r.basei < r.basej)temp = r.basei;for(i= i ;i > j; -i )r.basei = r.basei-1;r.basej = temp;r.baser.length ='0'rewind(fp);fprintf(fp,"%s",r.base); fclose(fp);free(r.base);8.2折半插入排序#include<stdio.h>#include<stdlib.h>#defin

23、e q 1000typedef struct char *base ; int stacksize ;int length;sqlist2; void zb(file *fp) sqlist2 r;int i,j ,m, low, high;char temp; r.base=(char *) malloc(1000*sizeof(char);r.stacksize = 1000;r.length = 0; while(!feof(fp)fscanf(fp,"%c",r.base);r.base+;r.length+;if(r.length = r.stacksize )r

24、.base= r.base - r.length;r.base=(char *) realloc(r.base,(r.stacksize + q) * sizeof(char);if(!r.base)printf("error");return ; r.base = r.base + r.stacksize;r.stacksize += q; r.length -;r.base -;r.base= r.base - r.length;for ( i = 1 ; i < r.length ; i+ )temp=r.basei; low=0;high=i-1;while(

25、 low <= high ) m = (low+high)/2; if ( temp < r.basem )high = m-1; elselow = m+1; for( j=i-1; j>=high+1; -j )r.basej+1= r.basej; r.basehigh+1=temp; r.baser.length ='0'rewind(fp);fprintf(fp,"%s",r.base);fclose(fp);free(r.base);8.3希爾排序#include<stdio.h>#include<stdlib

26、.h>#define q 1000typedef struct char *base ; int stacksize ;int length;sqlist3; void xe(file *fp) sqlist3 r;int i,j,k,m;char temp;r.length = 0; r.base=(char *) malloc(1000*sizeof(char);r.stacksize = 1000; while(!feof(fp)fscanf(fp,"%c",r.base);r.base+;r.length+;if(r.length = r.stacksize

27、)r.base= r.base - r.length;r.base=(char *) realloc(r.base,(r.stacksize + q) * sizeof(char);if(!r.base)printf("error");return ; r.base = r.base + r.stacksize;r.stacksize += q; r.length -;r.base -;r.base= r.base - r.length;for(k = 0; k < 10 ; k+)m = 10 - k;for( i = m ; i < r.length; i

28、+ )if(r.basei < r.basei - m) temp = r.basei; for(j = i - m ; j >= 0 && temp < r.basej; j -= m)r.base j + m = r.basej; r.base j + m = temp; rewind(fp);fprintf(fp,"%s",r.base);fclose(fp);free(r.base);8.4直接選擇排序#include<stdio.h>#include<stdlib.h>#define q 1000typed

29、ef struct char *base ; int stacksize ;int length;sqlist4; void jd(file *fp) sqlist4 r;int i,j ,m;char temp; r.base=(char *) malloc(1000*sizeof(char);r.stacksize = 1000;r.length = 0; while(!feof(fp)fscanf(fp,"%c",r.base);r.base+;r.length+;if(r.length = r.stacksize )r.base= r.base - r.length

30、;r.base=(char *) realloc(r.base,(r.stacksize + q) * sizeof(char);if(!r.base)printf("error");return ; r.base = r.base + r.stacksize;r.stacksize += q; r.length -;r.base -;r.base= r.base - r.length;for ( i = 0 ; i < r.length ; i+ )temp=r.basei; for( j = i,m = j +1 ; m < r.length ; m+)if

31、(r.basej > r.basem)j = m;r.basei = r.basej;r.basej = temp;r.baser.length ='0'rewind(fp);fprintf(fp,"%s",r.base); fclose(fp);free(r.base);8.5堆排序#include<stdio.h>#include<stdlib.h>#define q 1000typedef struct char *base ; int stacksize ; int length;sqlist5; void heapad

32、just(char *r,int s,int m);void dp(file *fp) sqlist5 r;int i,j;char temp,*k;r.length = 0; r.base=(char *) malloc(1000*sizeof(char);r.stacksize = 1000;r.base += 1; while(!feof(fp)fscanf(fp,"%c",r.base);r.base+;r.length+;if(r.length = (r.stacksize - 1) )r.base= r.base - r.length - 1;r.base=(c

33、har *) realloc(r.base,(r.stacksize + q) * sizeof(char);if(!r.base)printf("error");return ; r.base = r.base + r.stacksize;r.stacksize += q; r.length -;r.base -;r.base= r.base - r.length - 1;for(i = r.length / 2;i >= 1 ; -i)heapadjust(r.base,i,r.length); for(i = r.length ;i >= 2 ; -i)t

34、emp = r.base1; r.base1 = r.basei;r.basei = temp;heapadjust(r.base,1,i-1);k = (char *) malloc(r.length+1)*sizeof(char); for(i = r.length,j = 0; i >= 1; i-,j+)kj = r.basei;kj='0'rewind(fp); fprintf(fp,"%s",k); fclose(fp);free(k);free(r.base);void heapadjust(char *r,int k,int m)int

35、 i,j;char x;i=k; x=ri; j=2*i;while(j<=m) if( (j<m) && (rj>rj+1) )j+;if(x>rj) ri =rj;i = j;j *= 2;else j = m + 1;ri = x;8.6歸并排序#include<stdio.h>#include<stdlib.h>#define q 1000typedef struct char *base ; int stacksize ; int length;sqlist6; void merge(sqlist6 r,int h,in

36、t m,int w,sqlist6 t) int i,j,k;i = h; j = m + 1; k = h - 1;while(i <= m)&&(j <= w) k+;if(r.basei <= r.basej)t.basek = r.basei+;elset.basek = r.basej+;if(i > m)while(j <= w) t.base+k=r.basej+;elsewhile(i <= m) t.base+k=r.basei+;void tgb(int s,int n,sqlist6 r,sqlist6 t) int i

37、=1;while(i<=(n-2*s+1) merge(r,i,i+s-1,i+2*s-1,t);i=i+2*s;if(i<(n-s+1) merge(r,i,i+s-1,n,t);else while(i<=n) t.basei=r.basei+;void gb(file *fp) sqlist6 r;r.length = 0; r.base=(char *) malloc(1000*sizeof(char);r.stacksize = 1000;r.base += 1;while(!feof(fp)fscanf(fp,"%c",r.base);r.ba

38、se+;r.length+;if(r.length = (r.stacksize - 1) )r.base= r.base - r.length - 1;r.base=(char *) realloc(r.base,(r.stacksize + q) * sizeof(char);if(!r.base)printf("error");return ; r.base = r.base + r.stacksize;r.stacksize += q; r.length -;r.base= r.base - r.length - 2; int i,j,n,s=1;n = r.len

39、gth; sqlist6 t; t.base=(char *) malloc(r.stacksize*sizeof(char); while(s<n) tgb(s,n,r,t);s*=2;if(s<n) tgb(s,n,t,r); s *= 2; else i=0;while(i<=n) r.basei=t.basei+1;i+; r.baser.length ='0'rewind(fp); fprintf(fp,"%s",r.base); fclose(fp);free(t.base);free(r.base);8.7冒泡排序#inclu

40、de<stdio.h>#include<stdlib.h>#define q 1000typedef struct char *base ; int stacksize ;int length;sqlist7; void mp(file *fp) sqlist7 r;int i,j ,m;char temp;r.length = 0; r.base = (char *) malloc(1000*sizeof(char);r.stacksize = 1000;while(!feof(fp)fscanf(fp,"%c",r.base);r.base+;r.length+;if(r.length = r.stacksize )r.base= r.base - r.length;r.base=(char *) realloc(r.base,(r.stacksize + q) * sizeof(char);if(!r.base)printf("error");return ; r.bas