1、數據結構實驗報告實驗名稱：實驗四 排序學生姓名：班級：班內序號：學號：日期：2012年12月21日1、 實驗要求題目2使用鏈表實現下面各種排序算法，并進行比較。排序算法：1、插入排序2、冒泡排序3、快速排序4、簡單選擇排序5、其他要求：1、測試數據分成三類：正序、逆序、隨機數據。2、對于這三類數據，比較上述排序算法中關鍵字的比較次數和移動次數（其中關鍵字交換計為3次移動）。 3、對于這三類數據，比較上述排序算法中不同算法的執行時間，精確到微秒（選作）。4、對2和3的結果進行分析，驗證上述各種算法的時間復雜度。編寫測試main()函數測試線性表的正確性。2、 程序分析2.1存儲結構 說明：本程序

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

3、待排序的記錄序列劃分成有序區和無序區，初始時有序區為待排序記錄序列中的第一個記錄，無序區包括所有剩余待排序的記錄；2.將無須去的第一個記錄插入到有序區的合適位置中，從而使無序區減少一個記錄，有序區增加一個記錄；3.重復執行2，直到無序區中沒有記錄為止。（2）源代碼void LinkSort:InsertSort() /從第二個元素開始，尋找前面那個比它大的Node * P = front-next; /要插入的節點的前驅while(P-next)Node * S = front; /用來比較的節點的前驅while(1)CompareCount+;if( P-next-data next-dat

4、a )/ P的后繼比S的后繼小則插入 insert(P, S); break; S = S-next;if(S=P)/若一趟比較結束，且不需要插入 P = P-next; break; (3)時間和空間復雜度最好情況下，待排序序列為正序，時間復雜度為O（n）。最壞情況下，待排序序列為逆序，時間復雜度為O（n2）。直接插入排序只需要一個記錄的輔助空間，用來作為待插入記錄的暫存單元和查找記錄的插入位置過程中的“哨兵”。直接插入排序是一種穩定的排序方法。直接插入排序算法簡單容易實現，當序列中的記錄基本有序或帶排序記錄較少時，他是最佳的排序方法。但當待排序的記錄個數較多時，大量的比較和移動操作使直接插

5、入排序算法的效率減低。r1r2 ri-1 ri ri+1 rn有序區 無序區 直接插入排序的基本思想插入到合適位置 直接插入排序過程初始鍵值序列 12 15 9 20 6 31 24 第一趟排序結果 12 15 9 20 6 31 24 第二趟排序結果 9 12 15 20 6 31 24 第三趟排序結果 9 12 15 20 6 31 24 第四趟排序結果 6 9 12 15 20 31 24 第五趟排序結果 6 9 12 15 20 31 24 第六趟排序結果 6 9 12 15 20 24 31（二）冒泡排序 void LinkSort:BubbleSort()冒泡排序是交換排序中最簡單

6、的排序方法，其基本思想是：兩兩比較相鄰記錄的關鍵碼，如果反序則交換，直到沒有反序的記錄為止。本程序采用改進的冒泡程序。（1）算法自然語言1.將整個待排序的記錄序列劃分成有序區和無序區，初始狀態有序區為空，無序區包括所有待排序的記錄。2.對無序區從前向后依次將相鄰記錄的關鍵碼進行比較，若反序則交換，從而使得關鍵碼小的記錄向前移，關鍵碼大的記錄向后移（像水中的氣泡，體積大的先浮上來）。3.將最后一次交換的位置pos，做為下一趟無序區的末尾。4.重復執行2和3，直到無序區中沒有反序的記錄。（2）源代碼void LinkSort:BubbleSort()Node * P = front-next;wh

7、ile(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 * 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)時間

8、和空間復雜度在最好情況下，待排序記錄序列為正序，算法只執行了一趟，進行了n-1次關鍵碼的比較，不需要移動記錄，時間復雜度為O（n）；在最壞情況下，待排序記錄序列為反序，時間復雜度為O（n2），空間復雜度為O(1)。冒泡排序是一種穩定的排序方法。rj rj+1 ri+1 rn-1 rn 無序區 有序區 1ji-1 已經位于最終位置 起泡排序的基本思想反序則交換初始鍵值序列 50 13 55 97 27 38 49 65第一趟排序結果 13 50 55 27 38 49 65 97第二趟排序結果 13 50 27 38 49 55 65 97第三趟排序結果 13 27 38 49 50 55 65

9、 97第四趟排序結果 13 27 38 49 50 55 65 97 冒泡排序過程（三）快速排序 void LinkSort:Qsort()（1）算法自然語言1.首先選一個軸值（即比較的基準），將待排序記錄分割成獨立的兩部分，左側記錄的關鍵碼均小于或等于軸值，右側記錄的關鍵碼均大于或等于軸值。2.然后分別對這兩部分重復上述過程，直到整個序列有序。3.整個快速排序的過程遞歸進行。（2）源代碼void LinkSort:Qsort()Node * End = front;while(End-next) End = End-next;Partion(front, End);void LinkSort

10、:Partion(Node * Start, Node * End)if(Start-next=End | Start=End)/遞歸返回return ;Node * Mid = Start; /基準值前驅Node * P = Mid-next;while(P!=End & P!=End-next)CompareCount+;if( Mid-next-data P-next-data )/元素值小于軸點值，則將該元素插在軸點之前 if( P-next = End )/若該元素為End，則將其前驅設為EndEnd = P;insert(P, Mid); Mid = Mid-next; else

11、P = P-next;Partion(Start, Mid); /遞歸處理基準值左側鏈表Partion(Mid-next, End); /遞歸處理基準值右側鏈表（3）時間和空間復雜度在最好的情況下，時間復雜度為O（nlog2n）。在最壞的情況下，時間復雜度為O（n2）。快速排序是一種不穩定的排序方法。 r1 ri-1 ri ri+1 rn 均ri 軸值 均ri 位于最終位置 快速排序的基本思想圖解（四）簡單選擇排序基本思想為：第i趟排序通過n-i次關鍵碼的比較，在n-i+1（1in-1）各記錄中選取關鍵碼最小的記錄，并和第i個記錄交換作為有序序列的第i個記錄。（1）算法自然語言1.將整個記錄序

12、列劃分為有序區和無序區，初始狀態有序區為空，無序區含有待排序的所有記錄。2.在無序區中選取關鍵碼最小的記錄，將它與無序區中的第一個記錄交換，使得有序區擴展了一個記錄，而無序區減少了一個記錄。3.不斷重復2，直到無序區之剩下一個記錄為止。（2）源代碼void LinkSort:SelectSort()Node * S = front;while(S-next-next)Node * P = S;Node * Min = P;while(P-next) /查找最小記錄的位置CompareCount+;if(P-next-data next-data) Min = P;P = P-next;inse

13、rt(Min, S);S = S-next;（3）時間和空間復雜度簡單選擇排序最好、最壞和平均的時間復雜度為O（n2）。簡單選擇排序是一種不穩定的排序方法。初始鍵值序列 49 27 65 97 76 13 38第一趟排序結果 13 27 65 97 76 49 38第二趟排序結果 13 27 65 97 76 49 38第三趟排序結果 13 27 38 97 76 49 65第四趟排序結果 13 27 38 49 76 97 65第五趟排序結果 13 27 38 49 65 97 76第六趟排序結果 13 27 38 49 65 76 97 簡單選擇排序的過程示例（五）輸出比較結果函數（含計算

14、函數體執行時間代碼）（1）算法自然語言1、依次調用直接插入排序、冒泡排序、快速排序、簡單選擇排序的函數體，進行序列的排序，并輸出相應的比較次數、移動次數。2、獲取當前系統時間。在調用函數之前設定一個調用代碼前的時間，在調用函數之后再次設定一個調用代碼后的時間，兩個時間相減就是代碼運行時間。說明：運用QueryPerformanceFrequency()可獲取計時器頻率；QueryPerformanceCounter()用于得到高精度計時器的值。（2）源代碼void printResult(LinkSort &a, LinkSort &b, LinkSort &c, LinkSort &d)_L

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

16、);QueryPerformanceCounter(&time_over); /記錄結束時間TimeCount = (time_over.QuadPart-time_start.QuadPart)/dqFreq)*1000000;cout 排序結果：; a.print(); cout 1.插入。 比較次數： setw(3) CompareCount ; 移動次數： setw(3) MoveCount ; 時間: TimeCount us endl;CompareCount = 0; MoveCount = 0; TimeCount = 0;QueryPerformanceCounter(&ti

17、me_start); /記錄起始時間b.BubbleSort();QueryPerformanceCounter(&time_over); /記錄結束時間TimeCount = (time_over.QuadPart-time_start.QuadPart)/dqFreq)*1000000;cout 2.冒泡。 比較次數： setw(3) CompareCount ; 移動次數： setw(3) MoveCount ; 時間: TimeCount usendl;CompareCount = 0; MoveCount = 0; TimeCount = 0;QueryPerformanceCoun

18、ter(&time_start); /記錄起始時間c.Qsort();QueryPerformanceCounter(&time_over); /記錄結束時間TimeCount = (time_over.QuadPart-time_start.QuadPart)/dqFreq)*1000000 ;cout 3.快速。 比較次數： setw(3) CompareCount ; 移動次數： setw(3) MoveCount ; 時間: TimeCount usendl;CompareCount = 0; MoveCount = 0; TimeCount = 0;QueryPerformanceC

19、ounter(&time_start); /記錄起始時間d.SelectSort();QueryPerformanceCounter(&time_over); /記錄結束時間TimeCount = (time_over.QuadPart-time_start.QuadPart)/dqFreq)*1000000;cout 4.選擇。 比較次數： setw(3) CompareCount ; 移動次數： setw(3) MoveCount ; 時間: TimeCount usendl;（3）時間和空間復雜度時間復雜度O(1)(因為不包含循環體)。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、程序運行結果（1）程序流程圖開始 輸入數據順序數組四種排序和統計逆序數組四種排序和統計亂序數組四種排序和統計輸出統計結果結 束（2）測試條件規模為10個