算法設(shè)計(jì)技能訓(xùn)練報(bào)告

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

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

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

4、全部序列排序完成，使用了分治的思想。1.直接選擇排序原理：將序列劃分為無(wú)序和有序區(qū)，尋找無(wú)序區(qū)中的最小值和無(wú)序區(qū)的首元素交換，有序區(qū)擴(kuò)大一個(gè)，循環(huán)最終完成全部排序。.堆排序原理：利用大根堆或小根堆思想，首先建立堆，然后將堆首與堆尾交換，堆尾之后為有序區(qū)。歸并排序原理：將原序列劃分為有序的兩個(gè)序列，然后利用歸并算法進(jìn)行合并，合并之后即為有序序列。測(cè)試gj C; 1,. W ri dm 3 2 me. ?wem 時(shí) 金 泡 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)排序一般稱為簡(jiǎn)單排序，例如直接插入、直接選擇和冒泡排序；(2)線性對(duì)數(shù)階(O(nlgn)排序如快速、堆和歸并排序；(3)O(n1+b階排序£是介于0和1之間的常數(shù)，即0<£<1,如希爾排序；(4)線性階(O(n)排序如桶、箱和基數(shù)排序。各種排序方法比較簡(jiǎn)單排序中直接插入最好，快速排序最快，當(dāng)文件為正序時(shí)，直接插入和冒泡均最佳。

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

7、序?？焖倥判蚴悄壳盎诒容^的內(nèi)部排序中被認(rèn)為是最好的方法，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時(shí)，快速排序的平均時(shí)間最短；堆排序所需的輔助空間少于快速排序，并且不會(huì)出現(xiàn)快速排序可能出現(xiàn)的最壞情況。這兩種排序都是不穩(wěn)定的。若要求排序穩(wěn)定，則可選用歸并排序。但本章介紹的從單個(gè)記錄起進(jìn)行兩兩歸并的排序算法并不值得提倡，通?？梢詫⑺椭苯硬迦肱判蚪Y(jié)合在一起使用。先利用直接插入排序求得較長(zhǎng)的有序子文件，然后再兩兩歸并之。因?yàn)橹苯硬迦肱判蚴欠€(wěn)定的，所以改進(jìn)后的歸并排序仍是穩(wěn)定的。排序算法的穩(wěn)定性1)穩(wěn)定的：如果存在多個(gè)具有相同排序碼的記錄，經(jīng)過(guò)排序后，這些記錄的相對(duì)次序仍然保持不變，則這種排序算法稱為穩(wěn)定的。插入排

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

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

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

11、是基礎(chǔ)知識(shí)的應(yīng)用，包括第1章到第3章；第二部分為高級(jí)知識(shí)的應(yīng)用，包括第4章到第7章；第三部分是綜合應(yīng)用，包括第8章。各章基本知識(shí)與典型例題及上機(jī)實(shí)訓(xùn)緊密結(jié)合,每章后面提供了大量的習(xí)題。為了滿足國(guó)家計(jì)算機(jī)等級(jí)考辿的要求，C語(yǔ)言程序設(shè)計(jì)實(shí)用教程介紹了VisualC+6.0的開(kāi)發(fā)環(huán)境，教材內(nèi)容涵蓋了全國(guó)計(jì)算機(jī)等級(jí)考試考試大綱（C語(yǔ)言程序設(shè)計(jì)部分）。C語(yǔ)言程序設(shè)計(jì)實(shí)用教程可以作為高職高專各專業(yè)學(xué)生的教材，也可以作為普通高等院校各專業(yè)學(xué)生的教材，還可以作為全國(guó)計(jì)算機(jī)等級(jí)考試（二級(jí)C語(yǔ)言程序設(shè)計(jì)）的輔導(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;頭指針為空l(shuí)ength=0;長(zhǎng)度為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)建一個(gè)新的節(jié)點(diǎn)node*newnode=newnode();newnode->index=user_index;newnode->next=NULL;/將節(jié)點(diǎn)添加到鏈表的最末端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指針用來(lái)進(jìn)行指向要交換的兩個(gè)節(jié)點(diǎn)的左邊一個(gè)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ù)組的思想呢？因?yàn)檫@樣比較簡(jiǎn)潔，不易搞錯(cuò)for(inti=0;i<length;i+)temp=head;while(temp->next!=tail)if(temp->index>temp->next->index)exchangeNode(temp,temp->next);tail=temp;/交換相鄰兩個(gè)節(jié)點(diǎn)voidexchangeNode(node*left,node*right

17、)/如果left是頭結(jié)點(diǎn)if(left=head)left->next=right->next;right->next=left;head=right;return;/找到左節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)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)/從右向左找第一個(gè)小于x的數(shù)j-;if(i<j)si+=sj;while(i<j&&si<x)從左向右找第一個(gè)大于等于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+)/對(duì)左數(shù)組賦值lefti=datap+i;for(j=0;j<n2;j+)/對(duì)右數(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)/只有一個(gè)或無(wú)記錄時(shí)不須排序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<<"請(qǐng)輸入選擇:intm;cin>>m;switch(m)case 1:InsertionSort(A,n);output(A);cout<<"已經(jīng)進(jìn)行插入排序"<&

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