算法設(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ì)52.3算法設(shè)計(jì)5詳細(xì)設(shè)計(jì)6測試7結(jié) 論8致 謝9參 考 文 獻(xiàn)10課題任務(wù)描述利用隨機(jī)函數(shù)產(chǎn)生N個(gè)隨機(jī)整數(shù)（20000以上），對(duì)這些數(shù)進(jìn)行多種方法進(jìn)行排序。1.1 要求：1.1.1 至少采用三種方法實(shí)現(xià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ì)2.2數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) int An; srand(time(0); for(int i=0;in;i+) Ai=rand()%n;利用數(shù)組A進(jìn)行生成隨機(jī)數(shù)組然后進(jìn)行排序struct nodeint index; node* next;class MyLisprivate:node* head; int length;利用鏈表進(jìn)行排序2.3算法設(shè)計(jì)1.直接插入排序原理：將數(shù)組分為無序區(qū)和有序區(qū)兩個(gè)區(qū)，然后不斷將無序區(qū)的第一個(gè)元素按大小順序插入到

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

4、首元素交換，有序區(qū)擴(kuò)大一個(gè)，循環(huán)最終完成全部排序。.堆排序原理：利用大根堆或小根堆思想，首先建立堆，然后將堆首與堆尾交換，堆尾之后為有序區(qū)。歸并排序原理：將原序列劃分為有序的兩個(gè)序列，然后利用歸并算法進(jìn)行合并，合并之后即為有序序列。測試圖 4.1圖 4.2圖4.3結(jié) 論（1）平方階(O(n2)排序 一般稱為簡單排序，例如直接插入、直接選擇和冒泡排序；（2）線性對(duì)數(shù)階(O(nlgn)排序 如快速、堆和歸并排序；（3）O(n1+)階排序 是介于0和1之間的常數(shù)，即01，如希爾排序；（4）線性階(O(n)排序 如桶、箱和基數(shù)排序。各種排序方法比較 簡單排序中直接插入最好，快速排序最快，當(dāng)文件為正序時(shí)

5、，直接插入和冒泡均最佳。影響排序效果的因素 因?yàn)椴煌呐判蚍椒ㄟm應(yīng)不同的應(yīng)用環(huán)境和要求，所以選擇合適的排序方法應(yīng)綜合考慮下列因素：待排序的記錄數(shù)目n；記錄的大小(規(guī)模)；關(guān)鍵字的結(jié)構(gòu)及其初始狀態(tài)；對(duì)穩(wěn)定性的要求；語言工具的條件；存儲(chǔ)結(jié)構(gòu)；時(shí)間和輔助空間復(fù)雜度等。不同條件下，排序方法的選擇(1)若n較小(如n50)，可采用直接插入或直接選擇排序。 當(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)的排序方法：快速排

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

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

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

9、4）：3393574 張筑生.微分半動(dòng)力系統(tǒng)的不變集研究：學(xué)位論文，北京：數(shù)學(xué)系統(tǒng)學(xué)研究所，19835 Borko H，Bernier C LIndexing concepts and methods . New York: Academic Pr,19786機(jī)程序設(shè)計(jì)藝術(shù)英文名稱：The Art of Computer Programming作者：Donald.E.Knuth7.計(jì)算機(jī)導(dǎo)論名稱：Introduction to Algorithms作者：Thomas H. Cormen ，Charles E. Leiserson ，Ronald L. Rivest ，Clifford Stei

10、nC語言程序設(shè)計(jì)實(shí)用教程全面介紹了C語言的基礎(chǔ)知識(shí)和程序設(shè)計(jì)方法，共分為三部分，由淺到深，再到綜合應(yīng)用。第一部分是基礎(chǔ)知識(shí)的應(yīng)用，包括第1章到第3章；第二部分為高級(jí)知識(shí)的應(yīng)用，包括第4章到第7章；第三部分是綜合應(yīng)用，包括第8章。各章基本知識(shí)與典型例題及上機(jī)實(shí)訓(xùn)緊密結(jié)合，每章后面提供了大量的習(xí)題。為了滿足國家計(jì)算機(jī)等級(jí)考試的要求，C語言程序設(shè)計(jì)實(shí)用教程介紹了Visual C+ 6.0的開發(fā)環(huán)境，教材內(nèi)容涵蓋了全國計(jì)算機(jī)等級(jí)考試考試大綱(C語言程序設(shè)計(jì)部分)。 C語言程序設(shè)計(jì)實(shí)用教程可以作為高職高專各專業(yè)學(xué)生的教材，也可以作為普通高等院校各專業(yè)學(xué)生的教材，還可以作為全國計(jì)算機(jī)等級(jí)考試(二級(jí)C語言程

11、序設(shè)計(jì))的輔導(dǎo)wer by YOZOSOFT代碼#include#includeusing namespace std;#include#include# define n 2000#define lj 20struct node int index; node* next;class MyListprivate: node* head; int length;public: MyList() head = NULL;/頭指針為空 length = 0;/長度為0 MyList() node* left = head; node* right = NULL; while (left != NU

12、LL) right = left; left = left-next; delete right; void addNode(int user_index) if (isEmpty() head = new node(); head-next = NULL; head-index = user_index; else /創(chuàng)建一個(gè)新的節(jié)點(diǎn) node* newnode = new node(); newnode-index = user_index; newnode-next = NULL; /將節(jié)點(diǎn)添加到鏈表的最末端 node* t = head; while (t-next!=NULL) t

13、= t-next; t-next = newnode; length+; int ljcode; int getLength() return length; void display() if (isEmpty() cout The list is empty!; return; node* temp = head; while (temp) cout index; if (!temp-next)/已至鏈表尾，可以結(jié)束輸出了。 break; cout ; temp = temp-next; cout 0; i-) addNode(i); bool isEmpty() if (head=NUL

14、L) return true; else int ljcode=0; return false; void bubbleSort() if (isEmpty() int ljcode=1; return; /temp指針用來進(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)排好的元素的首地址，這里我們先移到鏈表尾部等待 node* tail = head; while (tai

15、l-next) tail = tail-next; /外層還是數(shù)組的思想，內(nèi)層就是鏈表的思想了，/為什么外層要用數(shù)組的思想呢？因?yàn)檫@樣比較簡潔，不易搞錯(cuò) for (int i = 0; i next != tail) if (temp-index temp-next-index) exchangeNode(temp, temp-next); tail = temp; /交換相鄰兩個(gè)節(jié)點(diǎn) void exchangeNode(node* left, node* right) /如果left是頭結(jié)點(diǎn) if (left=head) left-next = right-next; right-next

16、= 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; ;/堆的冒泡排序int ljcode2=0;void paixu() MyList hengbao; hengbao.lhInput(); hengbao.display(); hengbao.bu

17、bbleSort(); hengbao.display(); int ljcode=0;void InsertionSort(int *a, int len) /插入排序函數(shù)for (int j=1; j=0 & aikey)ai+1 = ai;i-;ai+1 = key;void ShellSort(int *a, int len) /希爾排序代碼int h = 1;while( h0 )for (int j=h; j=0 & aikey )ai+h = ai;i = i-h;int ljcode=0;ai+h = key;h = h/3;/冒泡排序void bubblesort(int *

18、a,int len)int i,j;for( i=0;ilen-1;i+)for( j=i+1;j=len-1;j+)if(aiaj)int t=ai; aj=ai; ai=t;/快速排序void quickSort(int s, int l, int r ) if (lr) int i = l, j = r, x = sl;while (i j)while(i = 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,

19、 i - 1); / 遞歸調(diào)用quickSort(s, i + 1, r);/選擇排序void SelectSort(int *a, int len) for (int i=0; ilen-1; i+)int k = i;int key = ai;for (int j=i+1; jlen; j+)if (ajkey)k = j;key = aj;if (k!=i)swap(ai, ak);void MaxHeapify(int *a, int i, int heapSize)int l = (i+1)*2-1;int r = (i+1)*2;int largest;if (lai)larges

20、t = l;elselargest = i;if (ralargest)largest = r;if (largest!=i)swap(ai, alargest);MaxHeapify(a, largest, heapSize);/ 創(chuàng)建最大堆void BuildMaxHeap(int *a, int len)for (int i=len/2-1; i=0; i-)MaxHeapify(a, i, len-1);/ 堆排序void HeapSort(int *a, int len)BuildMaxHeap(a, len);for (int i=len-1; i0; i-)swap(a0, ai

21、);MaxHeapify(a, 0, i-1);/歸并排序void merge(int *data, int p, int q, int r) int n1, n2, i, j, k; int *left=NULL, *right=NULL; n1 = q-p+1; n2 = r-q; left = (int *)malloc(sizeof(int)*(n1); right = (int *)malloc(sizeof(int)*(n2); for(i=0; in1; i+) /對(duì)左數(shù)組賦值 lefti = datap+i; for(j=0; jn2; j+) /對(duì)右數(shù)組賦值 rightj =

22、 dataq+1+j; i = j = 0; k = p; while(in1 & jn2) /將數(shù)組元素值兩兩比較，并合并到data數(shù)組 if(lefti = rightj) datak+ = lefti+; else datak+ = rightj+; for(; in1; i+) /如果左數(shù)組有元素剩余，則將剩余元素合并到data數(shù)組 datak+ = lefti; for(; jn2; j+) /如果右數(shù)組有元素剩余，則將剩余元素合并到data數(shù)組 datak+ = rightj; void mergeSort(int *data, int p, int r) int q; if(p

23、r) /只有一個(gè)或無記錄時(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ù)組 void output(int *A) ofstream output(c:textcode.txt,ios_base:out); output數(shù)組元素如下：; for(int i=0;in;i+) outputAi,; output.close();ofstream output1(c:bincode.bin,ios:binary);for(int i=0;in;i+)output1Ai,;output1.close ();int main() int An; srand(time(0); for(int i=0;in;i+) Ai=rand()%n; cout 排序算法的性能endl; cout 1.插入排序endl; cout 2.希爾排序endl; cout 3.