實(shí)驗(yàn)四排序?qū)嶒?yàn)報(bào)告

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：實(shí)驗(yàn)四 排序?qū)W生姓名：班級：班內(nèi)序號：學(xué)號：日期：2012年12月21日1、 實(shí)驗(yàn)要求題目2使用鏈表實(shí)現(xiàn)下面各種排序算法，并進(jìn)行比較。排序算法：1、插入排序2、冒泡排序3、快速排序4、簡單選擇排序5、其他要求：1、測試數(shù)據(jù)分成三類：正序、逆序、隨機(jī)數(shù)據(jù)。2、對于這三類數(shù)據(jù)，比較上述排序算法中關(guān)鍵字的比較次數(shù)和移動次數(shù)（其中關(guān)鍵字交換計(jì)為3次移動）。 3、對于這三類數(shù)據(jù)，比較上述排序算法中不同算法的執(zhí)行時(shí)間，精確到微秒（選作）。4、對2和3的結(jié)果進(jìn)行分析，驗(yàn)證上述各種算法的時(shí)間復(fù)雜度。編寫測試main()函數(shù)測試線性表的正確性。2、 程序分析2

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

3、1）算法自然語言1.將整個(gè)待排序的記錄序列劃分成有序區(qū)和無序區(qū)，初始時(shí)有序區(qū)為待排序記錄序列中的第一個(gè)記錄，無序區(qū)包括所有剩余待排序的記錄；2.將無須去的第一個(gè)記錄插入到有序區(qū)的合適位置中，從而使無序區(qū)減少一個(gè)記錄，有序區(qū)增加一個(gè)記錄；3.重復(fù)執(zhí)行2，直到無序區(qū)中沒有記錄為止。（2）源代碼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)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)時(shí)間和空間復(fù)雜度最好情況下，待排序序列為正序，時(shí)間復(fù)雜度為O（n）。最壞情況下，待排序序列為逆序，時(shí)間復(fù)雜度為O（n2）。直接插入排序只需要一個(gè)記錄的輔助空間，用來作為待插入記錄的暫存單元和查找記錄的插入位置過程中的“哨兵”。直接插入排序是一種穩(wěn)定的排序方法。直接插入排序算法簡單容易實(shí)現(xiàn)，當(dāng)序列中的記錄

5、基本有序或帶排序記錄較少時(shí)，他是最佳的排序方法。但當(dāng)待排序的記錄個(gè)數(shù)較多時(shí)，大量的比較和移動操作使直接插入排序算法的效率減低。（二）冒泡排序 void LinkSort:BubbleSort()冒泡排序是交換排序中最簡單的排序方法，其基本思想是：兩兩比較相鄰記錄的關(guān)鍵碼，如果反序則交換，直到?jīng)]有反序的記錄為止。本程序采用改進(jìn)的冒泡程序。（1）算法自然語言1.將整個(gè)待排序的記錄序列劃分成有序區(qū)和無序區(qū)，初始狀態(tài)有序區(qū)為空，無序區(qū)包括所有待排序的記錄。2.對無序區(qū)從前向后依次將相鄰記錄的關(guān)鍵碼進(jì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)時(shí)間和空間復(fù)雜度在最好情況下，待排序記錄序列為正序，算法只執(zhí)行了一趟，進(jìn)行了n-1次關(guān)鍵碼的比較，不需要移動記錄，時(shí)間復(fù)雜度為O（n）；在最壞情況下，待排序記錄序列為反序，時(shí)間復(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.首先選一個(gè)軸值（即比較的基準(zhǔn)），將待排序記錄分割成獨(dú)立的兩部分，左側(cè)記錄的關(guān)鍵碼均小于或等于軸值，右側(cè)記錄的關(guān)鍵碼均大于或等于軸值。2.然后分別對這兩部分重復(fù)上述過程，直

9、到整個(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(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 )/元素值小于軸點(diǎn)值，則將該元素插在軸點(diǎn)之前 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）時(shí)間和空間復(fù)雜度在最好的情況下，時(shí)

11、間復(fù)雜度為O（nlog2n）。在最壞的情況下，時(shí)間復(fù)雜度為O（n2）?？焖倥判蚴且环N不穩(wěn)定的排序方法。（四）簡單選擇排序基本思想為：第i趟排序通過n-i次關(guān)鍵碼的比較，在n-i+1（1in-1）各記錄中選取關(guān)鍵碼最小的記錄，并和第i個(gè)記錄交換作為有序序列的第i個(gè)記錄。（1）算法自然語言1.將整個(gè)記錄序列劃分為有序區(qū)和無序區(qū)，初始狀態(tài)有序區(qū)為空，無序區(qū)含有待排序的所有記錄。2.在無序區(qū)中選取關(guān)鍵碼最小的記錄，將它與無序區(qū)中的第一個(gè)記錄交換，使得有序區(qū)擴(kuò)展了一個(gè)記錄，而無序區(qū)減少了一個(gè)記錄。3.不斷重復(fù)2，直到無序區(qū)之剩下一個(gè)記錄為止。（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）時(shí)間和空間復(fù)雜度簡單選擇排序最好、最壞和平均的時(shí)間復(fù)雜度為O（n2）。簡單選擇排序是一種不穩(wěn)定的排序方法。（五）輸出比較結(jié)果函數(shù)（含計(jì)算函數(shù)體執(zhí)行時(shí)間代碼）（

13、1）算法自然語言1、依次調(diào)用直接插入排序、冒泡排序、快速排序、簡單選擇排序的函數(shù)體，進(jìn)行序列的排序，并輸出相應(yīng)的比較次數(shù)、移動次數(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 &

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

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

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

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

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

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

20、 << "4.選擇。 比較次數(shù)：" << setw(3) << CompareCount << " 移動次數(shù)：" << setw(3) << MoveCount << " 時(shí)間: " << TimeCount << "us"<<endl;（3）時(shí)間和空間復(fù)雜度時(shí)間復(fù)雜度O(1)(因?yàn)椴话h(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、程序運(yùn)行結(jié)果（1）程序流程圖開始 輸入數(shù)據(jù)順序數(shù)組四種排序和統(tǒng)計(jì)逆序數(shù)組四種排序和統(tǒng)計(jì)亂序數(shù)組四種排序和統(tǒng)計(jì)輸