算法設(shè)計技能訓(xùn)練報告

1、淮陰工學(xué)院算法設(shè)計技能訓(xùn)練報告姓名:學(xué)號：班級：NIIT學(xué)院：計算機與軟件工程學(xué)院專業(yè)：計算機科學(xué)與技術(shù)題目：排序算法的比較指導(dǎo)教師:目錄課題任務(wù)描述3系統(tǒng)設(shè)計42.1 功能模塊設(shè)計42.2 數(shù)據(jù)結(jié)構(gòu)設(shè)計62.3 算法設(shè)計7詳細設(shè)計錯誤!未定義書簽。測試8結(jié)論10致謝12參考文獻13課題任務(wù)描述利用隨機函數(shù)產(chǎn)生N個隨機整數(shù)（20000以上），對這些數(shù)進行多種方法進行排序。1.1 要求:1.1.1 至少采用三種方法實現(xiàn)上述問題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結(jié)果保存在不同的文件中。1.1.2 統(tǒng)計每一種排序方法的性能（以

2、上機運行程序所花費的時間為準進行對比），找出其中兩種較快的方法。1.1.3 如果采用4種或4種以上的方法者，可適當加分。系統(tǒng)設(shè)計2.1 功能模塊設(shè)計世苓0o名俄革也告妙<一礫發(fā)豆菌卑世7"礙般£1-SJ_±JL上二送空笈出甑蛇R<、d2.2 數(shù)據(jù)結(jié)構(gòu)設(shè)計intAn;srand(time(0);for(inti=0;i<n;i+)Ai=rand()%n;利用數(shù)組A進行生成隨機數(shù)組然后進行排序structnodeintindex;node*next;；classMyLisprivate:node*head;intlength;利用鏈表進行排序2.3

3、算法設(shè)計1 .直接插入排序原理：將數(shù)組分為無序區(qū)和有序區(qū)兩個區(qū)，然后不斷將無序區(qū)的第一個元素按大小順序插入到有序區(qū)中去，最終將所有無序區(qū)元素都移動到有序區(qū)完成排序。2 .希爾排序原理：又稱增量縮小排序。先將序列按增量劃分為元素個數(shù)相同的若干組，使用直接插入排序法進行排序，然后不斷縮小增量直至為1,最后使用直接插入排序完成排序。要點：增量的選擇以及排序最終以1為增量進行排序結(jié)束。1 .冒泡排序原理：將序列劃分為無序和有序區(qū)，不斷通過交換較大元素至無序區(qū)尾完成排序。要點：設(shè)計交換判斷條件，提前結(jié)束以排好序的序列循環(huán)2 .快速排序原理：不斷尋找一個序列的中點，然后對中點左右的序列遞歸的進行排序，直至

4、全部序列排序完成，使用了分治的思想。1.直接選擇排序原理：將序列劃分為無序和有序區(qū)，尋找無序區(qū)中的最小值和無序區(qū)的首元素交換，有序區(qū)擴大一個，循環(huán)最終完成全部排序。.堆排序原理：利用大根堆或小根堆思想，首先建立堆，然后將堆首與堆尾交換，堆尾之后為有序區(qū)。歸并排序原理：將原序列劃分為有序的兩個序列，然后利用歸并算法進行合并，合并之后即為有序序列。測試gj C; 1,. W ri dm 3 2 me. ?wem 時 金 泡 ro_,.ll 一 !£二IF一 二 bJt, -二二»!ICLIFrFrIT用起快選推僧12345678序- brrrrrEi 入史梨 愿鎮(zhèn) 一，誓經(jīng)臬按

5、JW8圖4.1SBC：,Wrdow?7/7：em52me.ewe杳序ILL-Ji ;£pi一 二; IJI- I-J I d ，1 I I I - 隼起居 1.2.3.4.5.6.7.8.主圖4.2圖4.3(1)平方階(O(n2)排序一般稱為簡單排序，例如直接插入、直接選擇和冒泡排序；(2)線性對數(shù)階(O(nlgn)排序如快速、堆和歸并排序；(3)O(n1+b階排序£是介于0和1之間的常數(shù)，即0<£<1,如希爾排序；(4)線性階(O(n)排序如桶、箱和基數(shù)排序。各種排序方法比較簡單排序中直接插入最好，快速排序最快，當文件為正序時，直接插入和冒泡均最佳。

6、影響排序效果的因素因為不同的排序方法適應(yīng)不同的應(yīng)用環(huán)境和要求，所以選擇合適的排序方法應(yīng)綜合考慮下列因素：待排序的記錄數(shù)目n；記錄的大小(規(guī)模)；關(guān)鍵字的結(jié)構(gòu)及其初始狀態(tài)；對穩(wěn)定性的要求；語言工具的條件；存儲結(jié)構(gòu)；時間和輔助空間復(fù)雜度等。不同條件下，排序方法的選擇(1)若n較小(如n&50),可采用直接插入或直接選擇排序。當記錄規(guī)模較小時，直接插入排序較好；否則因為直接選擇移動的記錄數(shù)少于直接插人，應(yīng)選直接選擇排序為宜。(2)若文件初始狀態(tài)基本有序(指正序)，則應(yīng)選用直接插人、冒泡或隨機的快速排序為宜；(3)若n較大，則應(yīng)采用時間復(fù)雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排

7、序。快速排序是目前基于比較的內(nèi)部排序中被認為是最好的方法，當待排序的關(guān)鍵字是隨機分布時，快速排序的平均時間最短；堆排序所需的輔助空間少于快速排序，并且不會出現(xiàn)快速排序可能出現(xiàn)的最壞情況。這兩種排序都是不穩(wěn)定的。若要求排序穩(wěn)定，則可選用歸并排序。但本章介紹的從單個記錄起進行兩兩歸并的排序算法并不值得提倡，通常可以將它和直接插入排序結(jié)合在一起使用。先利用直接插入排序求得較長的有序子文件，然后再兩兩歸并之。因為直接插入排序是穩(wěn)定的，所以改進后的歸并排序仍是穩(wěn)定的。排序算法的穩(wěn)定性1)穩(wěn)定的：如果存在多個具有相同排序碼的記錄，經(jīng)過排序后，這些記錄的相對次序仍然保持不變，則這種排序算法稱為穩(wěn)定的。插入排

8、序、冒泡排序、歸并排序、分配排序(桶式、基數(shù))都是穩(wěn)定的排序算法。2)不穩(wěn)定的：否則稱為不穩(wěn)定的。直接選擇排序、堆排序、shell排序、快速排序都是不穩(wěn)定的排序算法謝我的老師，他們嚴謹細致、一絲不茍的作風(fēng)一直是我工作、學(xué)習(xí)中的榜樣；他們循循善誘的教導(dǎo)和不拘一格的思路給予我無盡的啟迪。這片論文的每個實驗細節(jié)和每個數(shù)據(jù)，都離不開你的細心指導(dǎo)。而你開朗的個性和寬容的態(tài)度，幫助我能夠很快的融入我們這個新的實驗室感謝我的同門，謝謝你們給予我的幫助！感謝我的朋友，感謝你們在我失意時給我鼓勵，在失落時給我支持，感謝你們和我一路走來，讓我在此過程中倍感溫暖！感謝我的家人我的父母、姐姐和弟弟。沒有你們，就不會有

9、今天的我！我一直感恩，感恩于我可以擁有一個如此溫馨的家庭，讓我所有的一切都可以在你們這里得到理解與支持，得到諒解和分擔。我愛你們，愛我們的家！一個人的成長絕不是一件孤立的事，沒有別人的支持與幫助絕不可能辦到。我感謝可以有這樣一個空間，讓我對所有給予我關(guān)心、幫助的人說聲謝謝”！今后，我會繼續(xù)努力，好好工作！好好學(xué)習(xí)！好好生活！參考文獻1劉國鈞，陳紹業(yè)，王鳳翥.圖書館目錄.第1版.北京：高等教育出版社，19572傅承義，陳運泰，祁貴中.地球物理學(xué)基礎(chǔ).北京：科學(xué)出版社，1985,4473華羅庚，王元.論一致分布與近似分析.中國科學(xué)，1973（4）:3393574張筑生.微分半動力系統(tǒng)的不變集研究：

10、學(xué)位論文，北京：數(shù)學(xué)系統(tǒng)學(xué)研究所，19835BorkoH,BernierCL.Indexingconceptsandmethods.NewYork:AcademicPr,19786機程序設(shè)計藝術(shù)英文名稱：TheArtofComputerProgramming作者：Donald.E.Knuth7.計算機導(dǎo)論名稱：IntroductiontoAlgorithms作者：ThomasH.Cormen,CharlesE.Leiserson,RonaldL.Rivest,CliffordSteinC語言程序設(shè)計實用教程全面介紹了C語言的基礎(chǔ)知識和程序設(shè)計方法，共分為三部分,由淺到深，再到綜合應(yīng)用。第一部分

11、是基礎(chǔ)知識的應(yīng)用，包括第1章到第3章；第二部分為高級知識的應(yīng)用，包括第4章到第7章；第三部分是綜合應(yīng)用，包括第8章。各章基本知識與典型例題及上機實訓(xùn)緊密結(jié)合,每章后面提供了大量的習(xí)題。為了滿足國家計算機等級考辿的要求，C語言程序設(shè)計實用教程介紹了VisualC+6.0的開發(fā)環(huán)境，教材內(nèi)容涵蓋了全國計算機等級考試考試大綱（C語言程序設(shè)計部分）。C語言程序設(shè)計實用教程可以作為高職高專各專業(yè)學(xué)生的教材，也可以作為普通高等院校各專業(yè)學(xué)生的教材，還可以作為全國計算機等級考試（二級C語言程序設(shè)計）的輔導(dǎo)werbyYOZOSOFT代碼#include<iostream>#include<f

12、stream>usingnamespacestd;#include<time.h>#include<stdlib.h>#definen2000#definelj20structnodeintindex;node*next;classMyListprivate:node*head;intlength;public:MyList()head=NULL;頭指針為空length=0;長度為0MyList()node*left=head;node*right=NULL;while(left!=NULL)right=left;left=left->next;delete

13、right;voidaddNode(intuser_index)if(isEmpty()head=newnode();head->next=NULL;head->index=user_index;else/創(chuàng)建一個新的節(jié)點node*newnode=newnode();newnode->index=user_index;newnode->next=NULL;/將節(jié)點添加到鏈表的最末端node*t=head;while(t->next!=NULL)t=t->next;t->next=newnode;length+;intljcode;intgetLengt

14、h()returnlength;voiddisplay()if(isEmpty()cout<<"Thelistisempty!"return;node*temp=head;while(temp)cout<<temp->index;if(!temp->next)/已至鏈表尾，可以結(jié)束輸出了。break;cout<<"->"temp=temp->next;cout<<endl;charljcode1;voidlhInput()for(inti=12;i>0;i-)addNode(i

15、);boolisEmpty()if(head=NULL)returntrue;elseintljcode=0;returnfalse;voidbubbleSort()if(isEmpty()intljcode=1;return;/temp指針用來進行指向要交換的兩個節(jié)點的左邊一個node*temp=head;while(temp&&temp->next)if(temp->index>temp->next->index)exchangeNode(temp,temp->next);/尾指針總是指向已經(jīng)排好的元素的首地址，這里我們先移到鏈表尾部等待

16、node*tail=head;while(tail->next)tail=tail->next;/外層還是數(shù)組的思想，內(nèi)層就是鏈表的思想了，/為什么外層要用數(shù)組的思想呢？因為這樣比較簡潔，不易搞錯for(inti=0;i<length;i+)temp=head;while(temp->next!=tail)if(temp->index>temp->next->index)exchangeNode(temp,temp->next);tail=temp;/交換相鄰兩個節(jié)點voidexchangeNode(node*left,node*right

17、)/如果left是頭結(jié)點if(left=head)left->next=right->next;right->next=left;head=right;return;/找到左節(jié)點的前一個節(jié)點node*before_left=head;while(before_left->next!=left)before_left=before_left->next;before_left->next=right;left->next=right->next;right->next=left;/堆的冒泡排序intljcode2=0;voidpaixu()M

18、yListhengbao;hengbao.lhInput();hengbao.display();hengbao.bubbleSort();hengbao.display();intljcode=0;voidInsertionSort(int*a,intlen)/插入排序函數(shù)for(intj=1;j<len;j+)intkey=aj;inti=j-1;intljcode=0;while(i>=0&&ai>key)ai+1=ai;i-;ai+1=key;voidShellSort(int*a,intlen)/希爾排序代碼inth=1;while(h<len

19、)h=3*h+1;while(h>0)for(intj=h;j<len;j+)intkey=aj;inti=j-h;while(i>=0&&ai>key)ai+h=ai;i=i-h;intljcode=0;ai+h=key;h=h/3;/冒泡排序voidbubblesort(int*a,intlen)inti,j;for(i=0;i<len-1;i+)for(j=i+1;j<=len-1;j+)if(ai<aj)intt=ai;aj=ai;ai=t;/快速排序voidquickSort(ints,intl,intr)if(l<r)

20、inti=l,j=r,x=sl;while(i<j)while(i<j&&sj>=x)/從右向左找第一個小于x的數(shù)j-;if(i<j)si+=sj;while(i<j&&si<x)從左向右找第一個大于等于x的數(shù)i+;if(i<j)sj-=si;si=x;quickSort(s,l,i-1);/遞歸調(diào)用quickSort(s,i+1,r);/選擇排序voidSelectSort(int*a,intlen)for(inti=0;i<len-1;i+)intk=i;intkey=ai;for(intj=i+1;j<

21、len;j+)if(aj<key)k=j;key=aj;if(k!=i)swap(ai,ak);voidMaxHeapify(int*a,inti,intheapSize)intl=(i+1)*2-1;intr=(i+1)*2;intlargest;if(l<=heapSize&&al>ai)largest=l;elselargest=i;if(r<=heapSize&&ar>alargest)largest=r;if(largest!=i)swap(ai,alargest);MaxHeapify(a,largest,heapSiz

22、e);/創(chuàng)建最大堆voidBuildMaxHeap(int*a,intlen)for(inti=len/2-1;i>=0;i-)MaxHeapify(a,i,len-1);/堆排序voidHeapSort(int*a,intlen)BuildMaxHeap(a,len);for(inti=len-1;i>0;i-)swap(a0,ai);MaxHeapify(a,0,i-1);/歸并排序voidmerge(int*data,intp,intq,intr)intn1,n2,i,j,k;int*left=NULL,*right=NULL;n1=q-p+1;n2=r-q;left=(in

23、t*)malloc(sizeof(int)*(n1);right=(int*)malloc(sizeof(int)*(n2);for(i=0;i<n1;i+)/對左數(shù)組賦值lefti=datap+i;for(j=0;j<n2;j+)/對右數(shù)組賦值rightj=dataq+1+j;i=j=0;k=p;while(i<n1&&j<n2)/將數(shù)組元素值兩兩比較，并合并到data數(shù)組if(lefti<=rightj)datak+=lefti+;elsedatak+=rightj+;for(;i<n1;i+)/如果左數(shù)組有元素剩余，則將剩余元素合并到d

24、ata數(shù)組datak+=lefti;for(;j<n2;j+)/如果右數(shù)組有元素剩余，則將剩余元素合并到data數(shù)組datak+=rightj;voidmergeSort(int*data,intp,intr)intq;if(p<r)/只有一個或無記錄時不須排序q=(int)(p+r)/2);/將data數(shù)組分成兩半mergeSort(data,p,q);/遞歸拆分左數(shù)組mergeSort(data,q+1,r);/遞歸拆分右數(shù)組merge(data,p,q,r);/合并數(shù)組voidoutput(int*A)ofstreamoutput("c:textcode.txt&q

25、uot;,ios_base:out);output<<"數(shù)組元素如下："for(inti=0;i<n;i+)output<<Ai<<','output.close();ofstreamoutput1("c:bincode.bin",ios:binary);for(inti=0;i<n;i+)output1<<Ai<<","output1.close();intmain()intAn;srand(time(0);for(inti=0;i<n;i

26、+)Ai=rand()%n;cout<<"cout<<"cout<<"cout<<"cout<<"cout<<"cout<<"cout<<"cout<<"cout<<"請輸入選擇:intm;cin>>m;switch(m)case 1:InsertionSort(A,n);output(A);cout<<"已經(jīng)進行插入排序"<&

27、lt;endl;cout<<"結(jié)果已存入文件"<<endl;break;case 2:ShellSort(A,n);output(A);cout<<"已經(jīng)進行希爾排序"<<endl;cout<<"結(jié)果已存入文件"<<endl;break;排序算法的性能"<<endl;1 .插入排序"<<endl;2 .希爾排序"<<endl;3 .起泡排序"<<endl;4 .快速排序"<<endl;5 .選擇排序"<<endl;6 .堆排序"<<endl;7 .歸并排序"