排序算法性能分析報告

1、 . . . 1 / 15*實踐教學(xué)實踐教學(xué)*理工大學(xué)理工大學(xué)計算機(jī)與通信學(xué)院2011 年春季學(xué)期數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計課程設(shè)計題目：專業(yè)班級：姓名：學(xué) 號：指導(dǎo)教師：成績：_目目 錄錄摘要.3 . . . 2 / 15前言.4正文.51.1. 采用類采用類C C語言定義相關(guān)的數(shù)據(jù)類型語言定義相關(guān)的數(shù)據(jù)類型 .5 52.2. 各模塊的偽碼算法各模塊的偽碼算法 .5 53.3. 函數(shù)的調(diào)用關(guān)系圖函數(shù)的調(diào)用關(guān)系圖 .6 64.4. 調(diào)試分析調(diào)試分析 .7 7a a、 調(diào)試中遇到的問題與對問題的解決方法調(diào)試中遇到的問題與對問題的解決方法.7 7b b、 算法的時間復(fù)雜度和空間復(fù)雜度算法的時間復(fù)雜度

2、和空間復(fù)雜度.7 75.5. 源程序源程序 .8 8總結(jié).13參考文獻(xiàn).14致 .15摘要摘要 排序是計算機(jī)程序設(shè)計中的一種重要操作。各種部排序算法的時間復(fù)雜度分析結(jié)果只給出了算法執(zhí)行時間的階，或大概執(zhí)行時間。 . . . 3 / 15 關(guān)鍵字：排序，性能分析。前言前言排序是計算機(jī)程序設(shè)計中的一種重要操作。它的功能是將一個數(shù)據(jù)元素的任 . . . 4 / 15意序列，重新排列成一個按關(guān)鍵字有序的序列。部排序的方法很多，但是就其全面性能而言，很難 提出一種被認(rèn)為是最好的方法，每一種方法都有各自的優(yōu)缺點，適合在不同的環(huán)境下使用。如果按排序過程中依據(jù)的不同原則對部排序方法進(jìn)行分類，則大致可分為插入排

3、序，交換排序，選擇排序，歸并排序和記數(shù)排序等五類。 這幾種排序算法是在順序存儲結(jié)構(gòu)上實現(xiàn)的，因此在排序過程中需要進(jìn)行大量記錄的移動。當(dāng)記錄很大時，時間耗費很大，此時可采用靜態(tài)鏈表作存儲結(jié)構(gòu)。但是有的排序方法，無法實現(xiàn)表排序。在這種情況下可以進(jìn)行地址排序，即另設(shè)一個地址向量指示相應(yīng)記錄。正文 . . . 5 / 151.1. 采用類采用類 c c 語言定義相關(guān)的數(shù)據(jù)類型語言定義相關(guān)的數(shù)據(jù)類型int 整型， char 字符型，2.2. 各模塊的偽碼算法各模塊的偽碼算法（1）插入排序偽碼算法：void InsertSort(Splist&L) for(i=2;i=L.length;+i) i

4、f(LT(L.ri.key,L.ri-1.key)“” ，須將.ri插入有序子表 L.r0= L.ri;復(fù)制為哨兵L.ri= L.ri-1;For(j)i-2;LT(L.r0.key,L.rj.key);-j)L.rj+1= L.rj;記錄后移L.rj+1= L.r0; 插入到正確位置/InsertSort(2) 希爾排序void shllInsert(Splist & L,int dk) for(i=dk+1;i0&LT(L.r0.key,L.rj.key);j-=dk)L.rj+dk=L.rj;記錄后移L.rj+dk=L.r0; 插入/shellsortvoid shlls

5、ort (Splist & L,int data,int t) for(k=0;kt;+k)shllInsert(L,datak);/shellsort（3）快速排序int part(sqlist&L,int low, int high) 交換順序表中子表。Rlow.high的記錄，使樞軸記錄到位，并返回其所在位此時在它之前（后）的記錄均不大（?。┯谒?。pivotkey=L.Low.key;while(loehigh)While(low=pivotkey) -high; L.rlow L.rhigh;while(low=pivotkey) +low;L.rlow L.rhigh

6、; . . . 6 / 15return low/partition(4) 選擇排序void selectsort(splist&L)for(i=1;iL.length;+i)j=selectMinKey(L,i);if(i!=j) L.ri L.rj;/selectsort（5）其泡排序void bubblesort(sqlist r,int n)int I,j,w;for (i=1;i=i+1;j-)if(rj.keyrj-1.key) 比較W=rj;Rj=rj-1;Rj-1=w;3.3. 函數(shù)的調(diào)用關(guān)系圖函數(shù)的調(diào)用關(guān)系圖MainInsertion sortquick sortbu

7、bble sortselection sortshell sortOutputquick . . . 7 / 154.4. 調(diào)試分析調(diào)試分析a、 調(diào)試中遇到的問題與對問題的解決方法 剛開始進(jìn)行輸入時，對有些排序不能實現(xiàn)，我就對不能實現(xiàn)的排序進(jìn)行分析，對產(chǎn)生的語法錯誤進(jìn)行了與時的改正，以至所有的排序算法能夠順利的實現(xiàn)。b、 算法的時間復(fù)雜度和空間復(fù)雜度 算法的時間復(fù)雜度分別是O(n2)，O(nlog2n)，O(log2n)，測試結(jié)果：23 45 6 13 8132 12 45 3 9 46 37 100 20 0 . . . 8 / 155.5. 源程序源程序#include #include

8、#define N 100/定義數(shù)組最大為 100const int t=3;/定義希爾排序次數(shù)int d3=4,3,1;/定義希爾排序比較量int qmt;/快速排序的移動次數(shù)int qct;/快速排序的比較次數(shù) void output(int n,int a,int ct,int mt)/部排序中調(diào)用的輸出函數(shù) int i; printf(n 排序結(jié)果:); for( i=0;in;i+) printf(%d ,ai);/輸出各排序完成的數(shù)組 printf(n 比較次數(shù):%dn,ct);/輸出各排序比較次數(shù) printf(移動次數(shù):%dnn,mt);/輸出各排序移動次數(shù) . . . 9 /

9、 15 void bubble_sort(int n,int A)/冒泡排序 int mt=0;/移動次數(shù) mt=movetime int ct=0;/比較次數(shù) ct=cmdtime int i,j,temp; int aN; for(i=0;in;i+) ai=Ai;/使數(shù)組 a與數(shù)組 A完全一樣,對數(shù)組 a進(jìn)行操作(不改動 A,可以使 A被其他函數(shù)調(diào)用) for(i=0;in-1;i+) for(j=0;jn-1-i;j+,ct+) if(aj+1aj)/前后比較 temp=aj, aj=aj+1, aj+1=temp, mt+=3;/關(guān)鍵字交換計為 3 次移動 printf(冒泡排序);

10、 output(n,a,ct,mt); void selection_sort(int n,int A)/選擇排序 int mt=0;/移動次數(shù) movetime int ct=0;/比較次數(shù) cmdtime int i,j,temp,k; int aN; for(i=0;in;i+) ai=Ai;/使數(shù)組 a與數(shù)組 A完全一樣,對數(shù)組 a進(jìn)行操作(不改動 A,可以使 A被其他函數(shù)調(diào)用) for(i=0;in-1;i+) k=i; for(j=i+1;jaj) k=j; temp=ai, ai=ak, ak=temp, . . . 10 / 15 mt+=3;/關(guān)鍵字交換計為 3 次移動 pr

11、intf(選擇排序); output(n,a,ct,mt); void quick(int a,int low,int up)/快速排序遞歸算法 int i,j,temp; if(lowup) i=low; j=up; temp=alow, qmt+; while(i!=j) qct+; while(itemp) j-, qct+; if(ij) ai+=aj, qct+; qmt+; while(ij&ai=temp) i+, qct+; if(ij) aj-=ai, qct+, qmt+; ai=temp, qmt+; quick(a,low,j-1); quick(a,i+1,u

12、p); void quick_sort(int n,int A)/快速排序(通過調(diào)用快速排序遞歸算法完成) int i; int aN; . . . 11 / 15 for(i=0;in;i+) ai=Ai;/使數(shù)組 a與數(shù)組 A完全一樣,對數(shù)組 a進(jìn)行操作(不改動 A,可以使 A被其他函數(shù)調(diào)用) quick(a,0,n-1);/調(diào)用快速排序遞歸算法 printf(快速排序); output(n,a,qct,qmt); void insertion_sort(int n,int A)/插入排序 int mt=0;/移動次數(shù) movetime int ct=0;/比較次數(shù) cmdtime int

13、 i,j,temp; int aN; for(i=0;in;i+) ai=Ai;/使數(shù)組 a與數(shù)組 A完全一樣,對數(shù)組 a進(jìn)行操作(不改動 A,可以使 A被其他函數(shù)調(diào)用) for(i=1;i=0&tempaj;j-,ct+) aj+1=aj, mt+; aj+1=temp, mt+; printf(插入排序); output(n,a,ct,mt); void shell_sort(int n,int A)/希爾排序 int mt=0;/移動次數(shù) movetime int ct=0;/比較次數(shù) cmdtime int i,j,k,h,y; int aN; for(i=0;in;i+) a

14、i=Ai;/使數(shù)組 a與數(shù)組 A完全一樣,對數(shù)組 a進(jìn)行操作(不改動 A,可以使 A被其他函數(shù)調(diào)用) for(i=0;it;i+) h=di; for(j=h;j=0&yak;k-=h) ak+h=ak; ak+h=y; printf(希爾排序); output(n,a,ct,mt); void main() int n; int i; int AN; printf(請輸入數(shù)組大小(小于 100)：); scanf(%d,&n);/輸入所需排序數(shù)組大小 for(i=0;in;i+) printf(請輸入數(shù)組 a%d：,i); scanf(%d,&Ai);/依次輸入數(shù)組

15、A0An bubble_sort(n,A);/冒泡排序 insertion_sort(n,A);/插入排序 selection_sort(n,A);/選擇排序 quick_sort(n,A);/快速排序 shell_sort(n,A);/希爾排序 . . . 13 / 15總結(jié)總結(jié)在這三周的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計中,我的題目是:排序算法性能分析,這三周課程設(shè)計中,通過該題目的設(shè)計過程,我加深了對排序算法的理解,對排序算法上基本運算的實現(xiàn)有所掌握,對課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)進(jìn)一步理解和掌握,學(xué)會了如何把學(xué)到的知識用于解決實際問題,鍛煉了自己動手的能力。一個人要完成所有的工作是非常困難和耗時的。在以后的

16、學(xué)習(xí)中我會更加注意各個方面的能力的協(xié)調(diào)發(fā)展。在課程設(shè)計時遇到了很多的問題，在老師的幫助，和對各種資料的查閱中，將問題解決，培養(yǎng)了我自主動手，獨立研究的能力，為今后在學(xué)習(xí)工作中能更好的發(fā)展打下了堅實的基礎(chǔ)。三周的課程設(shè)計很短暫，但其間的容是很充實的，在其中我學(xué)習(xí)到了很多平時書本中無法學(xué)到的東西，積累了經(jīng)驗，鍛煉了自己分析問題，解決問題的能力，并學(xué)會了如何將所學(xué)的各課知識融會，組織，來配合學(xué)習(xí)，三周中我收益很大，學(xué)到很多。 . . . 14 / 15參考文獻(xiàn)參考文獻(xiàn)1. 嚴(yán)蔚敏，吳偉民， 數(shù)據(jù)結(jié)構(gòu)（C 語言版） ，清華大學(xué)。2. 嚴(yán)蔚敏，吳偉民， 數(shù)據(jù)結(jié)構(gòu)題集（C 語言版） ，清華大學(xué)。3. DATA STRUCTURE WITH C+ ，Willi