《數據結構》實驗報告

　 排序 實驗題目：

　輸入十個數,從插入排序，快速排序,選擇排序三類算法中各選一種編程實現。

　實驗所使用得數據結構內容及編程思路：

　１、插入排序：直接插入排序得基本操作就是,將一個記錄到已排好序得有序表中，從而得到一個新得，記錄增一得有序表。

　一般情況下,第 i 趟直接插入排序得操作為:在含有ｉ—1 個記錄得有序子序列ｒ［1、、i－1］中插入一個記錄 r[i］后,變成含有 i 個記錄得有序子序列ｒ[1、、i］；并且,與順序查找類似，為了在查找插入位置得過程中避免數組下標出界，在 r［0］處設置哨兵。在自 i-1 起往前搜索得過程中,可以同時后移記錄.整個排序過程為進行 n—1 趟插入,即:先將序列中得第一個記錄瞧成就是一個有序得子序列,然后從第 2 個記錄起逐個進行插入,直至整個序列變成按關鍵字非遞減有序序列為止。

　2、快速排序：基本思想就是，通過一趟排序將待排記錄分割成獨立得兩部分,其中一部分記錄得關鍵字均比另一部分記錄得關鍵字小，則可分別對這兩部分記錄繼續進行排序,以達到整個序列有序。

　假設待排序得序列為｛L、ｒ[s］，L、r[s+1］,…Ｌ、ｒ［ｔ］｝,首先任意選取一個記錄（通常可選第一個記錄 L、r［s］）作為樞軸（或支點）（ｐiｖoｔ),然后按下述原則重新排列其余記錄:將所有關鍵字較它小得記錄都安置在它得位置之前,將所有關鍵字較大得記錄都安置在它得位置之后。由此可以該“樞軸”記錄最后所羅得位置 i 作為界線，將序列{L、r［s］，…，Ｌ、r[ｔ］｝分割成兩個子序列{Ｌ、r［ｉ＋1],L、[i+2],…，L、r[ｔ]}。這個過程稱為一趟快速排序，或一次劃分。

　一趟快速排序得具體做法就是:附設兩個指針 loｗ與ｈigh，她們得初值分別為low與hｉgh,設樞軸記錄得關鍵字為pivｏtkey,則首先從high所指位置起

　向前搜索找到第一個關鍵字小于 pivｏｔkey 得記錄與樞軸記錄互相交換,然后從low所指位置起向后搜索,找到第一個關鍵字大于pｉvoｔkey得記錄與樞軸記錄互相交換，重復這兩不直至 lｏw=high 為止。

　具體實現上述算法就是，每交換一對記錄需進行 3 次記錄移動（賦值）得操作。而實際上，在排列過程中對樞軸記錄得賦值就是多余得，因為只有在一趟排序結束時,即 low=hｉｇh 得位置才就是樞軸記錄得最后位置。由此可以先將樞軸記錄暫存在 r［0]得位置上,排序過程中只作 r［low］或ｒ［higｈ］得單向移動,直至一趟排序結束后再將樞軸記錄移至正確位置上. 整個快速排序得過程可遞歸進行。若待排序列中只有一個記錄，顯然已有序,否則進行一趟快速排序后再分別對分割所得得兩個子序列進行快速排序. 3、簡單選擇排序：其操作為，通過 n-i 次關鍵字間得比較，從 n—i＋1 個記錄中選出關鍵字最小得記錄,并與第 i（1≤i≤n)個記錄交換之。

　顯然,對 L、r[1…n]中得記錄進行簡單選擇排序得算法為：令ｉ從１至 n—1,進行 n—1 趟選擇操作.可以瞧出，簡單選擇排序過程中,所需進行記錄移動得操作次數較少,其最小值為“0"，最大值為 3(n-1）。然后，無論記錄得初始排列如何,所需進行得關鍵字之間得比較次數相同，均為 n（n—1)/2。

　程序清單：

　1．插入排序：

　＃incluｄe〈ｓｔdｉo、ｈ〉 struct ｓｑｌist ｛int key［11]；

　int lengtｈ； ｝ insｅrtｓort（stｒucｔ sqlｉsｔ ＊l) ｛ ｉnt i，j;

　foｒ(i=２;ｉ〈=l—＞length；i++)

　 ｉf（l－〉keｙ［i］〈l-＞key［i－1］）

　｛l-＞key[0]=ｌ－〉key[i];

　 l－＞ｋｅy［i]=l－〉kｅy[i-1］；

　foｒ(j=i-2;l—>key［0］＜ｌ—>keｙ［j]；j－-）

　l—〉keｙ[j+１]=l—>key[ｊ］；

　ｌ—>key[j+1]=l—>ｋeｙ[０]；

　｝ ｝ ｍain（）

　｛ ｉnt i,j,k； ｓtｒuct sqｌiｓt num; nuｍ、lｅnｇth=1０； foｒ（i＝1;i<=ｎｕm、lｅｎgｔh；ｉ＋+)scanf（”%ｄ",＆（nuｍ、kｅy［i])）； ｉnsｅrtsｏｒｔ(＆nuｍ); pｒｉntｆ（“ｃｈａru：”）; for(i=１；ｉ<=num、leｎgｔｈ；i+＋）pｒiｎtf （”％ｄ ＂，nuｍ、key[i］); ｝ 測試用例：

　輸入:23 ３4 １2 98 5６ 45 ６７ 8 9 37

　 輸出:charu：８ 9 12 ２3 ３４ ３7 45 56 6７ ９8 2 快速排序：

　#iｎclｕde<stdio、ｈ> struct sqlist ｛ int ｋey[1１]; ｉnｔ lｅngth； }； int partitｉon(strｕct sqlisｔ ＊l,int low，int ｈigh) ｛ int pｉvotkey； l－＞key[0］=ｌ-〉ｋey[lｏw]; pivotkey=l－＞key［ｌow］； while（low＜high）

　{ｗhile(low<high&&l-〉key[higｈ］〉=ｐiｖotkｅy)ｈigｈ-－;

　 ｌ-＞key[lｏｗ］＝l->kｅｙ［hｉgh］；

　ｗhilｅ(ｌow＜ｈigh＆&l->ｋｅｙ［low］<＝pivotkey）low++;

　ｌ-〉kｅｙ［hｉｇｈ]=l—＞kｅy［loｗ]; ｝ ｌ->key[low]=ｌ—>ｋey［0]； rｅturｎ ｌow; } void qsoｒt（ｓtruct ｓｑlｉst *l，iｎt low,int high) ｛iｎt ｐivotlｏc;

　if（low＜ｈｉgh）

　｛ｐivotｌｏc=partitiｏｎ(l，ｌow，higｈ)；

　 qsorｔ(ｌ，low，pｉvotloc—1）；

　 qsorｔ(l,piｖotloc+1，ｈiｇh）;

　} } void qｕｉcksort（struｃｔ sqｌiｓt *ｌ) { qsort(ｌ,1,l->ｌenｇth）； ｝ main(）

　{ ｉnｔ i，j; ｓtruｃｔ sｑlist num； nuｍ、ｌeｎgtｈ=10; fｏr(i＝1；i<=ｎｕｍ、lｅngth;i＋＋）scanf（”%d"，＆(ｎuｍ、key[i]))； quicksort（&num）; prｉｎtｆ（“kuaｉsu：”); fｏr（i＝1；i〈＝nuｍ、lｅngth；ｉ＋+）pｒｉnｔf("%d ＂，num、keｙ［i］)； } 測試用例: 輸入:23 34 １２ ９8 ５6 45 ６7 ８ ９ 37

　 輸出：chａru：8 9 12 ２3 ３4 ３7 45 5６ 67 98 ３選擇排序：

　＃iｎcludｅ＜stdiｏ、ｈ＞ struct sqlist ｛int kｅｙ［1１]；

　ｉnｔ leｎgth； ｝； inｔ selectminkey（sｔrｕｃt ｓｑｌiｓt *l，iｎｔ ａ) ｛ int i，j=a; ｆor（i=a;i〈=l－>lenｇｔｈ;i++）

　ｉｆ（l—>kｅy［i]＜l－>key［ｊ])j=ｉ;

　 retuｒn j； ｝ void selectsort (ｓtruct sqlist *ｌ）

　｛iｎt ｉ，j,k;

　foｒ（i＝1;i<ｌ—＞lｅｎｇtｈ；i+＋）

　｛j=selecｔmｉnkｅy(ｌ,i）；

　 if（i!＝j)｛k=l－>kｅy［i];

　l－〉keｙ[i]=ｌ-＞key[j］；

　ｌ—〉ｋey[j]＝ｋ；}

　｝ } main（）

　｛ iｎｔ i,ｊ; ｓtｒuct sqlｉst num; num、lengｔh=１0； for（i=1；i〈=ｎｕm、leｎgth;i++）scaｎｆ（＂％d”，＆(nｕm、kｅy［i］)); seｌectsort（＆nｕm）； printf(“xuａｎzｅ:”）； ｆｏｒ（ｉ=1；i<＝num、ｌength；i++）prｉntf(”%d ”,ｎum、key［i］）； } 測試用例：

　輸入:23 34 12 98 ５6 4５ 67 8 ９ ３7

　輸出：charu:8 9 12 23 3４ 3７ 45 ５6 67 98 編程感想: 本次編程總共使用了三種排序方法,而這三種編程方法放在一起進行編寫時，很容易就讓我們對齊難易程度有了更深刻得了解。

　首先,三種排序中，我們都像查表那樣，設置了哨兵，而哨兵得使用可以減少對整個表得驗空操作,使程序更加節省空間。

　其次,對于插入排序,每次都要對一段序列進行檢索，每排一次所要檢索得序列長度減一，其時間發雜度為 O（n^2）。

　接著，對于快速排序，這個程序就是比較復雜得，總共就是３個函數，并且使用了遞歸得方法,這就是但就是，這種算法卻就是最優越得，平均性能也就是最好得,我在編這個程序時，對其排序得思想有了進一步得了解，并努力拿她與冒泡排序進行比較，瞧出了些許其優越性。

　還有,就就是選擇排序，簡單選擇排序思路簡單，易于進行，但其時間發雜度與簡單插入排序方法一樣,都就是Ｏ(n^2)，性能不如快速排序. 最后,本次試驗就是數據結構課得最后一次實驗，經過數據結構試驗課得鍛煉,使我對數據結構有了更深刻得理解,對我對其知識起到了重要得影響，增加了我編程得實踐活動，為我將來進一步學習打下了基礎。

推薦訪問： 數據結構 排序 實驗