上傳人：I***

認(rèn)證信息

認(rèn)證類型：個人認(rèn)證

認(rèn)證主體：吉**（實名認(rèn)證）

IP屬地：貴州

IP屬地：貴州 上傳時間：2022-03-03 格式：DOC 頁數(shù)：18 大小：114.50KB 積分：20 舉報 版權(quán)申訴

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)實驗報告實驗名稱：實驗四 排序?qū)W生姓名：班級：班內(nèi)序號：學(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é)果進行分析，驗證上述各種算法的時間復(fù)雜度。編寫測試main()函數(shù)測試線性表的正確性。2、 程序分析2

2、.1存儲結(jié)構(gòu) 說明：本程序排序序列的存儲由鏈表來完成。 其存儲結(jié)構(gòu)如下圖所示。(1)單鏈表存儲結(jié)構(gòu)：結(jié)點 地址：1000HA21080H頭指針地址：1020HA0 10C0H 地址：1080H A3NULL地址：10C0HA11000H（2）結(jié)點結(jié)構(gòu)struct Nodeint data;Node * next;示意圖：int dataNode * next2.2關(guān)鍵算法分析一：關(guān)鍵算法 (一)直接插入排序 void LinkSort:InsertSort()直接插入排序是插入排序中最簡單的排序方法，其基本思想是：依次將待排序序列中的每一個記錄插入到一個已排好的序列中，直到全部記錄都排好序。（

3、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)CompareCount+;if(

4、 P->next->data < S->next->data )/ P的后繼比S的后繼小則插入 insert(P, S); break; S = S->next;if(S=P)/若一趟比較結(jié)束，且不需要插入 P = P->next; break; (3)時間和空間復(fù)雜度最好情況下，待排序序列為正序，時間復(fù)雜度為O（n）。最壞情況下，待排序序列為逆序，時間復(fù)雜度為O（n2）。直接插入排序只需要一個記錄的輔助空間，用來作為待插入記錄的暫存單元和查找記錄的插入位置過程中的“哨兵”。直接插入排序是一種穩(wěn)定的排序方法。直接插入排序算法簡單容易實現(xiàn)，當(dāng)序列中的記錄

5、基本有序或帶排序記錄較少時，他是最佳的排序方法。但當(dāng)待排序的記錄個數(shù)較多時，大量的比較和移動操作使直接插入排序算法的效率減低。（二）冒泡排序 void LinkSort:BubbleSort()冒泡排序是交換排序中最簡單的排序方法，其基本思想是：兩兩比較相鄰記錄的關(guān)鍵碼，如果反序則交換，直到?jīng)]有反序的記錄為止。本程序采用改進的冒泡程序。（1）算法自然語言1.將整個待排序的記錄序列劃分成有序區(qū)和無序區(qū)，初始狀態(tài)有序區(qū)為空，無序區(qū)包括所有待排序的記錄。2.對無序區(qū)從前向后依次將相鄰記錄的關(guān)鍵碼進行比較，若反序則交換，從而使得關(guān)鍵碼小的記錄向前移，關(guān)鍵碼大的記錄向后移（像水中的氣泡，體積大的先浮上來

6、）。3.將最后一次交換的位置pos，做為下一趟無序區(qū)的末尾。4.重復(fù)執(zhí)行2和3，直到無序區(qū)中沒有反序的記錄。（2）源代碼void LinkSort:BubbleSort()Node * P = front->next;while(P->next) /第一趟排序并查找無序范圍CompareCount+;if( P->data > P->next->data)swap(P, P->next);P = P->next;Node * pos = P;P = front->next;while(pos != front->next)Node *

7、 bound = pos;pos = front->next;while(P->next != bound)CompareCount+;if( P->data > P->next->data) swap(P, P->next); pos = P->next;P = P->next;P = front->next;(3)時間和空間復(fù)雜度在最好情況下，待排序記錄序列為正序，算法只執(zhí)行了一趟，進行了n-1次關(guān)鍵碼的比較，不需要移動記錄，時間復(fù)雜度為O（n）；在最壞情況下，待排序記錄序列為反序，時間復(fù)雜度為O（n2），空間復(fù)雜度為O(1)。冒

8、泡排序是一種穩(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ù)上述過程，直

9、到整個序列有序。3.整個快速排序的過程遞歸進行。（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!=

10、End->next)CompareCount+;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ù)雜度在最好的情況下，時

11、間復(fù)雜度為O（nlog2n）。在最壞的情況下，時間復(fù)雜度為O（n2）?？焖倥判蚴且环N不穩(wěn)定的排序方法。（四）簡單選擇排序基本思想為：第i趟排序通過n-i次關(guān)鍵碼的比較，在n-i+1（1in-1）各記錄中選取關(guān)鍵碼最小的記錄，并和第i個記錄交換作為有序序列的第i個記錄。（1）算法自然語言1.將整個記錄序列劃分為有序區(qū)和無序區(qū)，初始狀態(tài)有序區(qū)為空，無序區(qū)含有待排序的所有記錄。2.在無序區(qū)中選取關(guān)鍵碼最小的記錄，將它與無序區(qū)中的第一個記錄交換，使得有序區(qū)擴展了一個記錄，而無序區(qū)減少了一個記錄。3.不斷重復(fù)2，直到無序區(qū)之剩下一個記錄為止。（2）源代碼void LinkSort:SelectSort(

12、)Node * S = front;while(S->next->next)Node * P = S;Node * Min = P;while(P->next) /查找最小記錄的位置CompareCount+;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í)行時間代碼）（

13、1）算法自然語言1、依次調(diào)用直接插入排序、冒泡排序、快速排序、簡單選擇排序的函數(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 &

14、;d)_LARGE_INTEGER time_start; /開始時間 _LARGE_INTEGER time_over; /結(jié)束時間 double dqFreq; /計時器頻率 LARGE_INTEGER f; /計時器頻率 QueryPerformanceFrequency(&f); dqFreq=(double)f.QuadPart; a.print(); double TimeCount;CompareCount = 0; MoveCount = 0; TimeCount = 0;QueryPerformanceCounter(&time_start); /記錄起始時間

15、a.InsertSort();QueryPerformanceCounter(&time_over); /記錄結(jié)束時間TimeCount = (time_over.QuadPart-time_start.QuadPart)/dqFreq)*;cout << "排序結(jié)果：" a.print(); cout << "1.插入。 比較次數(shù)：" << setw(3) << CompareCount << " 移動次數(shù)：" << setw(3) << M

16、oveCount << " 時間: " << TimeCount <<"us"<< endl;CompareCount = 0; MoveCount = 0; TimeCount = 0;QueryPerformanceCounter(&time_start); /記錄起始時間b.BubbleSort();QueryPerformanceCounter(&time_over); /記錄結(jié)束時間TimeCount = (time_over.QuadPart-time_start.QuadPar

17、t)/dqFreq)*;cout << "2.冒泡。 比較次數(shù)：" << setw(3) << CompareCount << " 移動次數(shù)：" << setw(3) << MoveCount << " 時間: " << TimeCount << "us"<<endl;CompareCount = 0; MoveCount = 0; TimeCount = 0;QueryPerformanceCo

18、unter(&time_start); /記錄起始時間c.Qsort();QueryPerformanceCounter(&time_over); /記錄結(jié)束時間TimeCount = (time_over.QuadPart-time_start.QuadPart)/dqFreq)* ;cout << "3.快速。 比較次數(shù)：" << setw(3) << CompareCount << " 移動次數(shù)：" << setw(3) << MoveCount <<

19、; " 時間: " << TimeCount << "us"<<endl;CompareCount = 0; MoveCount = 0; TimeCount = 0;QueryPerformanceCounter(&time_start); /記錄起始時間d.SelectSort();QueryPerformanceCounter(&time_over); /記錄結(jié)束時間TimeCount = (time_over.QuadPart-time_start.QuadPart)/dqFreq)*;cout

20、 << "4.選擇。 比較次數(shù)：" << setw(3) << CompareCount << " 移動次數(shù)：" << setw(3) << MoveCount << " 時間: " << TimeCount << "us"<<endl;（3）時間和空間復(fù)雜度時間復(fù)雜度O(1)(因為不包含循環(huán)體)。2.3其他排序方法平均情況最好情況最壞情況輔助空間直接插入排序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、程序運行結(jié)果（1）程序流程圖開始 輸入數(shù)據(jù)順序數(shù)組四種排序和統(tǒng)計逆序數(shù)組四種排序和統(tǒng)計亂序數(shù)組四種排序和統(tǒng)計輸