實驗四 排序 實驗報告材料

word數(shù)據(jù)結(jié)構(gòu)實驗報告實驗名稱：實驗四 排序?qū)W生：班級：班序號：學(xué)號：日期：2012年12月21日1、 實驗要求題目2使用鏈表實現(xiàn)下面各種排序算法，并進(jìn)展比擬。排序算法：1、插入排序2、冒泡排序3、快速排序4、簡單項選擇擇排序5、其他要求：1、測試數(shù)據(jù)分成三類：正序、逆序、隨機(jī)數(shù)據(jù)。2、對于這三類數(shù)據(jù)，比擬上述排序算法中關(guān)鍵字的比擬次數(shù)和移動次數(shù)其中關(guān)鍵字交換計為3次移動。 3、對于這三類數(shù)據(jù)，比擬上述排序算法中不同算法的執(zhí)行時間，準(zhǔn)確到微秒選作。4、對2和3的結(jié)果進(jìn)展分析，驗證上述各種算法的時間復(fù)雜度。編寫測試main()函數(shù)測試線性表的正確性。2、 程序分析 說明：本程序排序序列的存儲由鏈表來完成。 其存儲結(jié)構(gòu)如如下圖所示。(1)單鏈表存儲結(jié)構(gòu)：結(jié)點 地址：1000HA21080H頭指針地址：1020HA0 10C0H地址：1080H A3NULL地址：10C0HA11000H2結(jié)點結(jié)構(gòu)struct Nodeint data;Node * next;示意圖：int dataNode * next一：關(guān)鍵算法 (一)直接插入排序 void LinkSort:InsertSort()直接插入排序是插入排序中最簡單的排序方法，其根本思想是：依次將待排序序列中的每一個記錄插入到一個已排好的序列中，直到全部記錄都排好序。1算法自然語言1.將整個待排序的記錄序列劃分成有序區(qū)和無序區(qū)，初始時有序區(qū)為待排序記錄序列中的第一個記錄，無序區(qū)包括所有剩余待排序的記錄；2.將無須去的第一個記錄插入到有序區(qū)的適宜位置中，從而使無序區(qū)減少一個記錄，有序區(qū)增加一個記錄；3.重復(fù)執(zhí)行2，直到無序區(qū)中沒有記錄為止。2源代碼void LinkSort:InsertSort()/從第二個元素開始，尋找前面那個比它大的Node * P = front->next;/要插入的節(jié)點的前驅(qū)while(P->next)Node * S = front;/用來比擬的節(jié)點的前驅(qū)while(1)pareCount+;if( P->next->data < S->next->data )/ P的后繼比S的后繼小如此插入 insert(P, S); break; S = S->next;if(S=P)/假如一趟比擬完畢，且不需要插入 P = P->next; break; (3)時間和空間復(fù)雜度最好情況下，待排序序列為正序，時間復(fù)雜度為On。最壞情況下，待排序序列為逆序，時間復(fù)雜度為On2。直接插入排序只需要一個記錄的輔助空間，用來作為待插入記錄的暫存單元和查找記錄的插入位置過程中的“哨兵。直接插入排序是一種穩(wěn)定的排序方法。直接插入排序算法簡單容易實現(xiàn)，當(dāng)序列中的記錄根本有序或帶排序記錄較少時，他是最優(yōu)的排序方法。但當(dāng)待排序的記錄個數(shù)較多時，大量的比擬和移動操作使直接插入排序算法的效率減低。二冒泡排序 void LinkSort:BubbleSort()冒泡排序是交換排序中最簡單的排序方法，其根本思想是：兩兩比擬相鄰記錄的關(guān)鍵碼，如果反序如此交換，直到?jīng)]有反序的記錄為止。本程序采用改良的冒泡程序。1算法自然語言1.將整個待排序的記錄序列劃分成有序區(qū)和無序區(qū)，初始狀態(tài)有序區(qū)為空，無序區(qū)包括所有待排序的記錄。2.對無序區(qū)從前向后依次將相鄰記錄的關(guān)鍵碼進(jìn)展比擬，假如反序如此交換，從而使得關(guān)鍵碼小的記錄向前移，關(guān)鍵碼大的記錄向后移像水中的氣泡，體積大的先浮上來。3.將最后一次交換的位置pos，做為下一趟無序區(qū)的末尾。4.重復(fù)執(zhí)行2和3，直到無序區(qū)中沒有反序的記錄。2源代碼void LinkSort:BubbleSort()Node * P = front->next;while(P->next)/第一趟排序并查找無序圍pareCount+;if( P->data > P->next->data)swap(P, P->next);P = P->next;Node * pos = P;P = front->next;while(pos != front->next)Node * bound = pos;pos = front->next;while(P->next != bound)pareCount+;if( P->data > P->next->data) swap(P, P->next); pos = P->next;P = P->next;P = front->next;(3)時間和空間復(fù)雜度在最好情況下，待排序記錄序列為正序，算法只執(zhí)行了一趟，進(jìn)展了n-1次關(guān)鍵碼的比擬，不需要移動記錄，時間復(fù)雜度為On；在最壞情況下，待排序記錄序列為反序，時間復(fù)雜度為On2，空間復(fù)雜度為O(1)。冒泡排序是一種穩(wěn)定的排序方法。初始鍵值序列 50 13 55 97 27 38 49 65第一趟排序結(jié)果 13 50 55 27 38 49 65 97第二趟排序結(jié)果 13 50 27 38 49 55 65 97第三趟排序結(jié)果 13 27 38 49 50 55 65 97第四趟排序結(jié)果 13 27 38 49 50 55 65 97 冒泡排序過程三快速排序 void LinkSort:Qsort()1算法自然語言1.首先選一個軸值即比擬的基準(zhǔn)，將待排序記錄分割成獨立的兩局部，左側(cè)記錄的關(guān)鍵碼均小于或等于軸值，右側(cè)記錄的關(guān)鍵碼均大于或等于軸值。2.然后分別對這兩局部重復(fù)上述過程，直到整個序列有序。3.整個快速排序的過程遞歸進(jìn)展。2源代碼void LinkSort:Qsort()Node * End = front;while(End->next) End = End->next;Partion(front, End);void LinkSort:Partion(Node * Start, Node * End)if(Start->next=End | Start=End)/遞歸返回return ;Node * Mid = Start;/基準(zhǔn)值前驅(qū)Node * P = Mid->next;while(P!=End && P!=End->next)pareCount+;if( Mid->next->data > P->next->data )/元素值小于軸點值，如此將該元素插在軸點之前 if( P->next = End )/假如該元素為End，如此將其前驅(qū)設(shè)為EndEnd = P;insert(P, Mid); Mid = Mid->next; else P = P->next;Partion(Start, Mid);/遞歸處理基準(zhǔn)值左側(cè)鏈表Partion(Mid->next, End);/遞歸處理基準(zhǔn)值右側(cè)鏈表3時間和空間復(fù)雜度在最好的情況下，時間復(fù)雜度為Onlog2n。在最壞的情況下，時間復(fù)雜度為On2?？焖倥判蚴且环N不穩(wěn)定的排序方法。四簡單項選擇擇排序根本思想為：第i趟排序通過n-i次關(guān)鍵碼的比擬，在n-i+11in-1各記錄中選取關(guān)鍵碼最小的記錄，并和第i個記錄交換作為有序序列的第i個記錄。1算法自然語言1.將整個記錄序列劃分為有序區(qū)和無序區(qū)，初始狀態(tài)有序區(qū)為空，無序區(qū)含有待排序的所有記錄。2.在無序區(qū)中選取關(guān)鍵碼最小的記錄，將它與無序區(qū)中的第一個記錄交換，使得有序區(qū)擴(kuò)展了一個記錄，而無序區(qū)減少了一個記錄。3.不斷重復(fù)2，直到無序區(qū)之剩下一個記錄為止。2源代碼void LinkSort:SelectSort()Node * S = front;while(S->next->next)Node * P = S;Node * Min = P;while(P->next) /查找最小記錄的位置pareCount+;if(P->next->data < Min->next->data) Min = P;P = P->next;insert(Min, S);S = S->next;3時間和空間復(fù)雜度簡單項選擇擇排序最好、最壞和平均的時間復(fù)雜度為On2。簡單項選擇擇排序是一種不穩(wěn)定的排序方法。五輸出比擬結(jié)果函數(shù)含計算函數(shù)體執(zhí)行時間代碼1算法自然語言1、依次調(diào)用直接插入排序、冒泡排序、快速排序、簡單項選擇擇排序的函數(shù)體，進(jìn)展序列的排序，并輸出相應(yīng)的比擬次數(shù)、移動次數(shù)。2、獲取當(dāng)前系統(tǒng)時間。在調(diào)用函數(shù)之前設(shè)定一個調(diào)用代碼前的時間，在調(diào)用函數(shù)之后再次設(shè)定一個調(diào)用代碼后的時間，兩個時間相減就是代碼運(yùn)行時間。說明：運(yùn)用QueryPerformanceFrequency()可獲取計時器頻率；QueryPerformanceCounter()用于得到高精度計時器的值。2源代碼void printResult(LinkSort &a, LinkSort &b, LinkSort &c, LinkSort &d)_LARGE_INTEGER time_start; /開始時間 _LARGE_INTEGER time_over; /完畢時間double dqFreq; /計時器頻率 LARGE_INTEGER f; /計時器頻率 QueryPerformanceFrequency(&f); dqFreq=(double)f.QuadPart; a.print();double TimeCount;pareCount = 0; MoveCount = 0; TimeCount = 0;QueryPerformanceCounter(&time_start); /記錄起始時間a.InsertSort();QueryPerformanceCounter(&time_over); /記錄完畢時間TimeCount = (time_over.QuadPart-time_start.QuadPart)/dqFreq)*1000000;cout << "排序結(jié)果：" a.print(); cout << "1.插入。 比擬次數(shù)：" << setw(3) << pareCount << " 移動次數(shù)：" << setw(3) << MoveCount << " 時間: " << TimeCount <<"us"<< endl;pareCount = 0; MoveCount = 0; TimeCount = 0;QueryPerformanceCounter(&time_start); /記錄起始時間b.BubbleSort();QueryPerformanceCounter(&time_over); /記錄完畢時間TimeCount = (time_over.QuadPart-time_start.QuadPart)/dqFreq)*1000000;cout << "2.冒泡。 比擬次數(shù)：" << setw(3) << pareCount << " 移動次數(shù)：" << setw(3) << MoveCount << " 時間: " << TimeCount << "us"<<endl;pareCount = 0; MoveCount = 0; TimeCount = 0;QueryPerformanceCounter(&time_start); /記錄起始時間c.Qsort();QueryPerformanceCounter(&time_over); /記錄完畢時間TimeCount = (time_over.QuadPart-time_start.QuadPart)/dqFreq)*1000000 ;cout << "3.快速。 比擬次數(shù)：" << setw(3) << pareCount << " 移動次數(shù)：" << setw(3) << MoveCount << " 時間: " << TimeCount << "us"<<endl;pareCount = 0; MoveCount = 0; TimeCount = 0;QueryPerformanceCounter(&time_start); /記錄起始時間d.SelectSort();QueryPerformanceCounter(&time_over); /記錄完畢時間TimeCount = (time_over.QuadPart-time_start.QuadPart)/dqFreq)*1000000;cout << "4.選擇。 比擬次數(shù)：" << setw(3) << pareCount << " 移動次數(shù)：" << setw(3) << MoveCount << " 時間: " << TimeCount << "us"<<endl;3時間和空間復(fù)雜度時間復(fù)雜度O(1)(因為不包含循環(huán)體)。其他排序方法平均情況最好情況最壞情況輔助空間直接插入排序O(n2)O(n)O(n2)O(1)希爾排序O(nlog2n)O(n2)O(n1.3)O(n2)O(1)起泡排序O(n2)O(n)O(n2)O(1)快速排序O(nlog2n)O(nlog2n)O(n2)O(log2n) O(n)簡單項選擇擇排序O(n2)O(n2)O(n2)O(1)堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)歸并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)3、程序運(yùn)行結(jié)果1程序流程圖開始輸入數(shù)據(jù)順序數(shù)組四種排序和統(tǒng)計逆序數(shù)組四種排序和統(tǒng)計亂序數(shù)組四種排序和統(tǒng)計輸出統(tǒng)計結(jié)果結(jié) 束2測試條件規(guī)模為10個數(shù)字，在正序、逆序和亂序的條件下進(jìn)展測試，未出現(xiàn)問題。3運(yùn)行結(jié)果：4說明：各函數(shù)運(yùn)行正常，沒有出現(xiàn)bug。四、總結(jié)1、調(diào)試時出現(xiàn)的問題與解決方法由于經(jīng)過一種排序后，原始數(shù)據(jù)改變，導(dǎo)致后面的排序所用的數(shù)據(jù)全為排好后的數(shù)據(jù)。將數(shù)據(jù)在排序前重新初始化后，該問題被排除。還有就是因為編程時沒有注意格式，所以在調(diào)試錯誤時花費(fèi)了不少時間。2、心得體會這是最后一次編程實驗。這次試驗，我覺得主要目的還是在掌握好課本知識的根底上，對代碼進(jìn)展相應(yīng)的優(yōu)化，以達(dá)到時間復(fù)雜度和空間復(fù)雜度的最優(yōu)。 其次，本次實驗是經(jīng)過借鑒課本上的程序進(jìn)展編寫，是基于課本完成的?？紤]到假如完全由自己編寫，如此又可能限于自己能力問題，將較簡單的算法編寫的過于麻煩，造成關(guān)鍵碼的比擬次數(shù)和移動次數(shù)比一些復(fù)雜算法還多，從而影響結(jié)果?；谡n本編寫，最大好處是可以借鑒、仔細(xì)研讀書上的優(yōu)秀例子，開拓以后編寫程序的思路?；谡n本編寫，最大壞處是自己獨立思考、獨立編寫、修改程序的能力未得到鍛煉。對于正序序列，直接插入、起泡排序法有較高的效率。對于逆序序列，簡單項選擇擇排序效率較高。對于在隨機(jī)序列，快速排序法的效率比擬高。程序的優(yōu)化是一個艱辛的過程，如果只是實現(xiàn)一般的功能，將變得容易很多，當(dāng)加上優(yōu)化，不論是效率還是結(jié)構(gòu)優(yōu)化，都需要精心設(shè)計。這次做優(yōu)化的過程中，遇到不少阻力。由于優(yōu)化中用到很多類的封裝和訪問控制方面的知識，而這局部知識恰好是大一一年學(xué)習(xí)的薄弱點。因而以后要多花力氣學(xué)習(xí)C+編程語言，必須要加強(qiáng)這方面的訓(xùn)練，這樣才能在將編程思想和數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換為代碼的時候能得心應(yīng)手。17 / 17