實驗四 排序 實驗資料報告材料

《實驗四 排序 實驗資料報告材料》由會員分享，可在線閱讀，更多相關(guān)《實驗四 排序 實驗資料報告材料（17頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、word 數(shù)據(jù)結(jié)構(gòu)實驗報告 實驗名稱：實驗四 排序 學(xué)生： 班級： 班序號： 學(xué)號： 日期：2012年12月21日 1、 實驗要求 題目2 使用鏈表實現(xiàn)下面各種排序算法，并進展比擬。 排序算法： 1、插入排序 2、冒泡排序 3、快速排序 4、簡單項選擇擇排序 5、其他 要求： 1、測試數(shù)據(jù)分成三類：正序、逆序、隨機數(shù)據(jù)。 2、對于這三類數(shù)據(jù)，比擬上述排序算法中關(guān)鍵字的比擬次數(shù)和移動次數(shù)〔其中關(guān)鍵字交換計為3次移動〕。 3、對于這三類數(shù)據(jù)，比擬上述排序算法中不同算法的執(zhí)行時間，準確到微秒〔選作〕。 4、對2和3的結(jié)果進展分析，驗證上述各種算法的時

2、間復(fù)雜度。 編寫測試main()函數(shù)測試線性表的正確性。 2、 程序分析 說明：本程序排序序列的存儲由鏈表來完成。 其存儲結(jié)構(gòu)如如如下圖所示。 (1)單鏈表存儲結(jié)構(gòu)： 結(jié)點 地址：1000H A[2] 1080H …… 頭指針 地址：1020H A[0] 10C0H …… 地址：1080H A[3] NULL …… 地址：10C0H A[1] 1000H …… 〔2〕結(jié)點結(jié)構(gòu) struct Node { int data; Node * next; }; 示意圖： int

3、 data Node * next 一：關(guān)鍵算法 (一)直接插入排序 void LinkSort::InsertSort() 直接插入排序是插入排序中最簡單的排序方法，其根本思想是：依次將待排序序列中的每一個記錄插入到一個已排好的序列中，直到全部記錄都排好序。 〔1〕算法自然語言 1.將整個待排序的記錄序列劃分成有序區(qū)和無序區(qū)，初始時有序區(qū)為待排序記錄序列中的第一個記錄，無序區(qū)包括所有剩余待排序的記錄； 2.將無須去的第一個記錄插入到有序區(qū)的適宜位置中，從而使無序區(qū)減少一個記錄，有序區(qū)增加一個記錄； 3.重復(fù)執(zhí)行2，直到無序區(qū)中沒有記錄為止。 〔2〕源

4、代碼 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的后繼小如此插入

5、 { insert(P, S); break; } S = S->next; if(S==P) //假設(shè)一趟比擬完畢，且不需要插入 { P = P->next; break; } } } } (3)時間和空間復(fù)雜度 最好情況下，待排序序列為正序，時間復(fù)雜度為O〔n〕。 最壞情況下，待排序序列為逆序，時間復(fù)雜度為O〔n2〕。 直接插入排序只需要一個記錄的輔助空間，用來作為待插入記錄的暫存單元和查找記錄的插入位置過程中的“哨兵〞。 直接插入排序是一種穩(wěn)定的排序方法。直接插入排序算法簡單容易實現(xiàn)

6、，當(dāng)序列中的記錄根本有序或帶排序記錄較少時，他是最優(yōu)的排序方法。但當(dāng)待排序的記錄個數(shù)較多時，大量的比擬和移動操作使直接插入排序算法的效率減低。 〔二〕冒泡排序 void LinkSort::BubbleSort() 冒泡排序是交換排序中最簡單的排序方法，其根本思想是：兩兩比擬相鄰記錄的關(guān)鍵碼，如果反序如此交換，直到?jīng)]有反序的記錄為止。本程序采用改良的冒泡程序。 〔1〕算法自然語言 1.將整個待排序的記錄序列劃分成有序區(qū)和無序區(qū)，初始狀態(tài)有序區(qū)為空，無序區(qū)包括所有待排序的記錄。 2.對無序區(qū)從前向后

7、依次將相鄰記錄的關(guān)鍵碼進展比擬，假設(shè)反序如此交換，從而使得關(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-

8、>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; }

9、 P = P->next; } P = front->next; } } (3)時間和空間復(fù)雜度 在最好情況下，待排序記錄序列為正序，算法只執(zhí)行了一趟，進展了n-1次關(guān)鍵碼的比擬，不需要移動記錄，時間復(fù)雜度為O〔n〕； 在最壞情況下，待排序記錄序列為反序，時間復(fù)雜度為O〔n2〕，空間復(fù)雜度為O(1)。 冒泡排序是一種穩(wěn)定的排序方法。 初始鍵值序列 ［50 13 55 97 27 38 49 65］ 第一趟排序結(jié)果 ［13 50 55 27 38 49 65］ 97 第二趟排序結(jié)果 ［13 5

10、0 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.首先選一個軸值〔即比擬的基準〕，將待排序記錄分割成獨立的兩局部，左側(cè)記錄的關(guān)鍵碼均小于或等于軸值，右側(cè)記錄的關(guān)鍵碼均大于或等于軸值。 2.然后分別對這兩局部重復(fù)上述過程，直到整個序列有序。 3.整個快速排序

11、的過程遞歸進展。 〔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; //基準值前驅(qū)

12、 Node * P = Mid->next; while(P!=End && P!=End->next) { pareCount++; if( Mid->next->data > P->next->data ) //元素值小于軸點值，如此將該元素插在軸點之前 { if( P->next == End ) //假設(shè)該元素為End，如此將其前驅(qū)設(shè)為End End = P; insert(P, Mid); Mid = Mid->next; } else P = P->next; } Partion(Start, Mid);

13、 //遞歸處理基準值左側(cè)鏈表 Partion(Mid->next, End); //遞歸處理基準值右側(cè)鏈表 } 〔3〕時間和空間復(fù)雜度 在最好的情況下，時間復(fù)雜度為O〔nlog2n〕。 在最壞的情況下，時間復(fù)雜度為O〔n2〕。 快速排序是一種不穩(wěn)定的排序方法。 〔四〕簡單項選擇擇排序 根本思想為：第i趟排序通過n-i次關(guān)鍵碼的比擬，在n-i+1〔1≤i≤n-1〕各記錄中選取關(guān)鍵碼最小的記錄，并和第i個記錄交換作為有序序列的第i個記錄。 〔1〕算法自然語言 1.將整個記錄序列劃

14、分為有序區(qū)和無序區(qū)，初始狀態(tài)有序區(qū)為空，無序區(qū)含有待排序的所有記錄。 2.在無序區(qū)中選取關(guān)鍵碼最小的記錄，將它與無序區(qū)中的第一個記錄交換，使得有序區(qū)擴展了一個記錄，而無序區(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) //查找最小記錄的位置

15、{ pareCount++; if(P->next->data < Min->next->data) Min = P; P = P->next; } insert(Min, S); S = S->next; } } 〔3〕時間和空間復(fù)雜度 簡單項選擇擇排序最好、最壞和平均的時間復(fù)雜度為O〔n2〕。 簡單項選擇擇排序是一種不穩(wěn)定的排序方法。 〔五〕輸出比擬結(jié)果函數(shù)〔含計算函數(shù)體執(zhí)行時間代碼〕 〔1〕算法自然語言 1、依次調(diào)用直接插入排序、冒泡排序、快速排序、簡單項選擇擇排

16、序的函數(shù)體，進展序列的排序，并輸出相應(yīng)的比擬次數(shù)、移動次數(shù)。 2、獲取當(dāng)前系統(tǒng)時間。在調(diào)用函數(shù)之前設(shè)定一個調(diào)用代碼前的時間，在調(diào)用函數(shù)之后再次設(shè)定一個調(diào)用代碼后的時間，兩個時間相減就是代碼運行時間。 說明：運用QueryPerformanceFrequency()可獲取計時器頻率；QueryPerformanceCounter()用于得到高精度計時器的值。 〔2〕源代碼 void printResult(LinkSort &a, LinkSort &b, LinkSort &c, LinkSort &d) { _LARGE_INTEGER time_start;

17、 //開始時間 _LARGE_INTEGER time_over; //完畢時間 double dqFreq; //計時器頻率 LARGE_INTEGER f; //計時器頻率 QueryPerformanceFrequency(&f); dqFreq=(double)f.QuadPart; a.print(); double TimeCount; pare

18、Count = 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ù)：" <

19、< 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 =

20、((time_over.QuadPart-time_start.QuadPart)/dqFreq)*1000000; cout << "2.冒泡。 比擬次數(shù)：" << setw(3) << pareCount << "; 移動次數(shù)：" << setw(3) << MoveCount << "; 時間: " << TimeCount << "us"<

21、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"<

22、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) << Mo

23、veCount << "; 時間: " << TimeCount << "us"<

24、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、程序運行結(jié)果 〔1〕程序流程圖 開始 輸入數(shù)據(jù) 順序數(shù)組四種排序和統(tǒng)計 逆序數(shù)組四種排序和統(tǒng)計 亂序數(shù)組四種排序和統(tǒng)計 輸出統(tǒng)計結(jié)果 結(jié) 束 〔2〕測試條件 規(guī)模為10個數(shù)字，在正序、逆序和亂序的條件下進展測試，未出現(xiàn)問題。 〔3〕運行結(jié)果： 〔4〕說明：各函數(shù)運行正常，

25、沒有出現(xiàn)bug。 四、總結(jié) 1、調(diào)試時出現(xiàn)的問題與解決方法 由于經(jīng)過一種排序后，原始數(shù)據(jù)改變，導(dǎo)致后面的排序所用的數(shù)據(jù)全為排好后的數(shù)據(jù)。將數(shù)據(jù)在排序前重新初始化后，該問題被排除。還有就是因為編程時沒有注意格式，所以在調(diào)試錯誤時花費了不少時間。 2、心得體會 這是最后一次編程實驗。這次試驗，我覺得主要目的還是在掌握好課本知識的根底上，對代碼進展相應(yīng)的優(yōu)化，以達到時間復(fù)雜度和空間復(fù)雜度的最優(yōu)。 其次，本次實驗是經(jīng)過借鑒課本上的程序進展編寫，是基于課本完成的。考慮到假設(shè)完全由自己編寫，如此又可能限于自己能力問題，將較簡單的算法編寫的過于麻煩，造成關(guān)鍵碼的比擬次數(shù)和移動次數(shù)比一些

26、復(fù)雜算法還多，從而影響結(jié)果。 基于課本編寫，最大好處是可以借鑒、仔細研讀書上的優(yōu)秀例子，開拓以后編寫程序的思路?；谡n本編寫，最大壞處是自己獨立思考、獨立編寫、修改程序的能力未得到鍛煉。 對于正序序列，直接插入、起泡排序法有較高的效率。 對于逆序序列，簡單項選擇擇排序效率較高。 對于在隨機序列，快速排序法的效率比擬高。 程序的優(yōu)化是一個艱辛的過程，如果只是實現(xiàn)一般的功能，將變得容易很多，當(dāng)加上優(yōu)化，不論是效率還是結(jié)構(gòu)優(yōu)化，都需要精心設(shè)計。這次做優(yōu)化的過程中，遇到不少阻力。由于優(yōu)化中用到很多類的封裝和訪問控制方面的知識，而這局部知識恰好是大一一年學(xué)習(xí)的薄弱點。因而以后要多花力氣學(xué)習(xí)C++編程語言，必須要加強這方面的訓(xùn)練，這樣才能在將編程思想和數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換為代碼的時候能得心應(yīng)手。 17 / 17