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

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

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

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

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)線性對數階(O(nlgn)排序如快速、堆和歸并排序；(3)O(n1+b階排序£是介于0和1之間的常數，即0<£<1,如希爾排序；(4)線性階(O(n)排序如桶、箱和基數排序。各種排序方法比較簡單排序中直接插入最好，快速排序最快，當文件為正序時，直接插入和冒泡均最佳。

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

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

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

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

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

11、是基礎知識的應用，包括第1章到第3章；第二部分為高級知識的應用，包括第4章到第7章；第三部分是綜合應用，包括第8章。各章基本知識與典型例題及上機實訓緊密結合,每章后面提供了大量的習題。為了滿足國家計算機等級考辿的要求，C語言程序設計實用教程介紹了VisualC+6.0的開發環境，教材內容涵蓋了全國計算機等級考試考試大綱（C語言程序設計部分）。C語言程序設計實用教程可以作為高職高專各專業學生的教材，也可以作為普通高等院校各專業學生的教材，還可以作為全國計算機等級考試（二級C語言程序設計）的輔導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/創建一個新的節點node*newnode=newnode();newnode->index=user_index;newnode->next=NULL;/將節點添加到鏈表的最末端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)/已至鏈表尾，可以結束輸出了。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指針用來進行指向要交換的兩個節點的左邊一個node*temp=head;while(temp&&temp->next)if(temp->index>temp->next->index)exchangeNode(temp,temp->next);/尾指針總是指向已經排好的元素的首地址，這里我們先移到鏈表尾部等待

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

17、)/如果left是頭結點if(left=head)left->next=right->next;right->next=left;head=right;return;/找到左節點的前一個節點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)/插入排序函數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的數j-;if(i<j)si+=sj;while(i<j&&si<x)從左向右找第一個大于等于x的數i+;if(i<j)sj-=si;si=x;quickSort(s,l,i-1);/遞歸調用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);/創建最大堆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+)/對左數組賦值lefti=datap+i;for(j=0;j<n2;j+)/對右數組賦值rightj=dataq+1+j;i=j=0;k=p;while(i<n1&&j<n2)/將數組元素值兩兩比較，并合并到data數組if(lefti<=rightj)datak+=lefti+;elsedatak+=rightj+;for(;i<n1;i+)/如果左數組有元素剩余，則將剩余元素合并到d

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

25、uot;,ios_base:out);output<<"數組元素如下："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<<"已經進行插入排序"<&

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