實(shí)驗(yàn)四 排序 實(shí)驗(yàn)報(bào)告材料

《實(shí)驗(yàn)四 排序 實(shí)驗(yàn)報(bào)告材料》由會(huì)員分享，可在線閱讀，更多相關(guān)《實(shí)驗(yàn)四 排序 實(shí)驗(yàn)報(bào)告材料（17頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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

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

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

4、 void LinkSort::InsertSort()//從第二個(gè)元素開始，尋找前面那個(gè)比它大的 { Node * P = front->next;//要插入的節(jié)點(diǎn)的前驅(qū) while(P->next) { Node * S = front;//用來比擬的節(jié)點(diǎn)的前驅(qū) while(1) { pareCount++; if( P->next->data < S->next->data )// P的后繼比S的后繼小如此插入 { insert(P, S); break; } S = S->next; if(S==P)//假如一趟比擬完畢，且不需要插入 { P

5、 = P->next; break; } } } } (3)時(shí)間和空間復(fù)雜度 最好情況下，待排序序列為正序，時(shí)間復(fù)雜度為O〔n〕。 最壞情況下，待排序序列為逆序，時(shí)間復(fù)雜度為O〔n2〕。 直接插入排序只需要一個(gè)記錄的輔助空間，用來作為待插入記錄的暫存單元和查找記錄的插入位置過程中的“哨兵〞。 直接插入排序是一種穩(wěn)定的排序方法。直接插入排序算法簡(jiǎn)單容易實(shí)現(xiàn)，當(dāng)序列中的記錄根本有序或帶排序記錄較少時(shí)，他是最優(yōu)的排序方法。但當(dāng)待排序的記錄個(gè)數(shù)較多時(shí)，大量的比擬和移動(dòng)操作使直接插入排序算法的效率減低。

6、 〔二〕冒泡排序 void LinkSort::BubbleSort() 冒泡排序是交換排序中最簡(jiǎn)單的排序方法，其根本思想是：兩兩比擬相鄰記錄的關(guān)鍵碼，如果反序如此交換，直到?jīng)]有反序的記錄為止。本程序采用改良的冒泡程序。 〔1〕算法自然語(yǔ)言 1.將整個(gè)待排序的記錄序列劃分成有序區(qū)和無(wú)序區(qū)，初始狀態(tài)有序區(qū)為空，無(wú)序區(qū)包括所有待排序的記錄。 2.對(duì)無(wú)序區(qū)從前向后依次將相鄰記錄的關(guān)鍵碼進(jìn)展比擬，假如反序如此交換，從而使得關(guān)鍵碼小的記錄向前移，關(guān)鍵碼大的記錄向后移〔像水中的氣泡，體積大的先浮上來〕。 3.將最后一次交換的位置pos，做為下一趟無(wú)序區(qū)的末尾。 4.重復(fù)執(zhí)行2和3，

7、直到無(wú)序區(qū)中沒有反序的記錄。 〔2〕源代碼 void LinkSort::BubbleSort() { Node * P = front->next; while(P->next)//第一趟排序并查找無(wú)序圍 { 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->ne

8、xt; 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)時(shí)間和空間復(fù)雜度 在最好情況下，待排序記錄序列為正序，算法只執(zhí)行了一趟，進(jìn)展了n-1次關(guān)鍵碼的比擬，不需要移動(dòng)記錄，時(shí)間復(fù)雜度為O〔n〕； 在最壞情況下，待排序記錄序列為反序，時(shí)間復(fù)雜度為O〔n2〕，空間復(fù)雜度為O(1)。 冒泡排序是一種穩(wěn)定的排序方法。

9、 初始鍵值序列 ［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〕算法自然語(yǔ)言

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

11、(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 )//元素值小于軸點(diǎn)值，如此將該元素插在軸點(diǎn)之前 { if( P->next == End )//假如該元素為End，如此將其前驅(qū)設(shè)為End End = P; insert(P, Mid); Mid = Mid->n

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

13、語(yǔ)言 1.將整個(gè)記錄序列劃分為有序區(qū)和無(wú)序區(qū)，初始狀態(tài)有序區(qū)為空，無(wú)序區(qū)含有待排序的所有記錄。 2.在無(wú)序區(qū)中選取關(guān)鍵碼最小的記錄，將它與無(wú)序區(qū)中的第一個(gè)記錄交換，使得有序區(qū)擴(kuò)展了一個(gè)記錄，而無(wú)序區(qū)減少了一個(gè)記錄。 3.不斷重復(fù)2，直到無(wú)序區(qū)之剩下一個(gè)記錄為止。 〔2〕源代碼 void LinkSort::SelectSort() { Node * S = front; while(S->next->next) { Node * P = S; Node * Min = P; while(P->next) //查找最小記

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

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

16、//開始時(shí)間 _LARGE_INTEGER time_over; //完畢時(shí)間 double dqFreq; //計(jì)時(shí)器頻率 LARGE_INTEGER f; //計(jì)時(shí)器頻率 QueryPerformanceFrequency(&f); dqFreq=(double)f.QuadPart; a.print(); double TimeCount; pareCount = 0; Mov

17、eCount = 0; TimeCount = 0; QueryPerformanceCounter(&time_start); //記錄起始時(shí)間 a.InsertSort(); QueryPerformanceCounter(&time_over); //記錄完畢時(shí)間 TimeCount = ((time_over.QuadPart-time_start.QuadPart)/dqFreq)*1000000; cout << "排序結(jié)果："; a.print(); cout << "1.插入。 比擬次數(shù)：" << setw(3) << pareCou

18、nt << "; 移動(dòng)次數(shù)：" << setw(3) << MoveCount << "; 時(shí)間: " << TimeCount <<"us"<< endl; pareCount = 0; MoveCount = 0; TimeCount = 0; QueryPerformanceCounter(&time_start); //記錄起始時(shí)間 b.BubbleSort(); QueryPerformanceCounter(&time_over); //記錄完畢時(shí)間 TimeCount = ((time_over.QuadPart-time

19、_start.QuadPart)/dqFreq)*1000000; cout << "2.冒泡。 比擬次數(shù)：" << setw(3) << pareCount << "; 移動(dòng)次數(shù)：" << setw(3) << MoveCount << "; 時(shí)間: " << TimeCount << "us"<

20、nter(&time_over); //記錄完畢時(shí)間 TimeCount = ((time_over.QuadPart-time_start.QuadPart)/dqFreq)*1000000 ; cout << "3.快速。 比擬次數(shù)：" << setw(3) << pareCount << "; 移動(dòng)次數(shù)：" << setw(3) << MoveCount << "; 時(shí)間: " << TimeCount << "us"<

21、ceCounter(&time_start); //記錄起始時(shí)間 d.SelectSort(); QueryPerformanceCounter(&time_over); //記錄完畢時(shí)間 TimeCount = ((time_over.QuadPart-time_start.QuadPart)/dqFreq)*1000000; cout << "4.選擇。 比擬次數(shù)：" << setw(3) << pareCount << "; 移動(dòng)次數(shù)：" << setw(3) << MoveCount << "; 時(shí)間: " << TimeCount <<

22、 "us"<

23、2n) O(nlog2n) O(nlog2n) O(1) 歸并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n) 3、程序運(yùn)行結(jié)果 〔1〕程序流程圖 開始 輸入數(shù)據(jù) 順序數(shù)組四種排序和統(tǒng)計(jì) 逆序數(shù)組四種排序和統(tǒng)計(jì) 亂序數(shù)組四種排序和統(tǒng)計(jì) 輸出統(tǒng)計(jì)結(jié)果 結(jié) 束 〔2〕測(cè)試條件 規(guī)模為10個(gè)數(shù)字，在正序、逆序和亂序的條件下進(jìn)展測(cè)試，未出現(xiàn)問題。 〔3〕運(yùn)行結(jié)果： 〔4〕說明：各函數(shù)運(yùn)行正常，沒有出現(xiàn)bug。 四、總結(jié) 1、調(diào)試時(shí)出現(xiàn)的問題與解決方法 由于經(jīng)

24、過一種排序后，原始數(shù)據(jù)改變，導(dǎo)致后面的排序所用的數(shù)據(jù)全為排好后的數(shù)據(jù)。將數(shù)據(jù)在排序前重新初始化后，該問題被排除。還有就是因?yàn)榫幊虝r(shí)沒有注意格式，所以在調(diào)試錯(cuò)誤時(shí)花費(fèi)了不少時(shí)間。 2、心得體會(huì) 這是最后一次編程實(shí)驗(yàn)。這次試驗(yàn)，我覺得主要目的還是在掌握好課本知識(shí)的根底上，對(duì)代碼進(jìn)展相應(yīng)的優(yōu)化，以達(dá)到時(shí)間復(fù)雜度和空間復(fù)雜度的最優(yōu)。 其次，本次實(shí)驗(yàn)是經(jīng)過借鑒課本上的程序進(jìn)展編寫，是基于課本完成的?？紤]到假如完全由自己編寫，如此又可能限于自己能力問題，將較簡(jiǎn)單的算法編寫的過于麻煩，造成關(guān)鍵碼的比擬次數(shù)和移動(dòng)次數(shù)比一些復(fù)雜算法還多，從而影響結(jié)果。 基于課本編寫，最大好處是可以借鑒、仔細(xì)研讀書

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