數(shù)據(jù)結(jié)構(gòu)試驗報告——排序

1、數(shù)據(jù)結(jié)構(gòu)實驗報告排序?qū)嶒烆}目：輸入十個數(shù)，從插入排序，快速排序，選擇排序三類算法中各選一種編程實現(xiàn)。實驗所使用的數(shù)據(jù)結(jié)構(gòu)內(nèi)容及編程思路：1 .插入排序：直接插入排序的基本操作是，將一個記錄到已排好序的有序表中，從而得到一個新的，記錄增一得有序表。一般情況下，第i趟直接插入排序的操作為：在含有i-1個記錄的有序子序列r1.i-1中插入一個記錄ri后，變成含有i個記錄的有序子序列r1.i；并且，和順序查找類似，為了在查找插入位置的過程中避免數(shù)組下標(biāo)出界，在r0處設(shè)置哨兵。在自i-1起往前搜索的過程中，可以同時后移記錄。整個排序過程為進(jìn)行n-1趟插入，即：先將序列中的第一個記錄看成是一個有序的子序列

2、，然后從第2個記錄起逐個進(jìn)行插入，直至整個序列變成按關(guān)鍵字非遞減有序序列為止。2 .快速排序：基本思想是，通過一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個序列有序。假設(shè)待排序的序列為s,s+1,-t,首先任意選取一個記錄（通常可選第一個記錄s）作為樞軸（或支點）（pivot）,然后按下述原則重新排列其余記錄：將所有關(guān)鍵字較它小的記錄都安置在它的位置之前，將所有關(guān)鍵字較大的記錄都安置在它的位置之后。由此可以該“樞軸”記錄最后所羅的位置i作為界線，將序列s,，t分割成兩個子序列i+1,L.i+2,t。這個過程

3、稱為一趟快速排序，或一次劃分。一趟快速排序的具體做法是：附設(shè)兩個指針low和high,他們的初值分別為low和high,設(shè)樞軸記錄的關(guān)鍵字為pivotkey,則首先從high所指位置起向前搜索找到第一個關(guān)鍵字小于pivotkey的記錄和樞軸記錄互相交換，然后從low所指位置起向后搜索，找到第一個關(guān)鍵字大于pivotkey的記錄和樞軸記錄互相交換，重復(fù)這兩不直至low=high為止。具體實現(xiàn)上述算法是，每交換一對記錄需進(jìn)行3次記錄移動（賦值）的操作。而實際上，在排列過程中對樞軸記錄的賦值是多余的，因為只有在一趟排序結(jié)束時，即low=high的位置才是樞軸記錄的最后位置。由此可以先將樞軸記錄暫存在

4、r0的位置上，排序過程中只作rlow或rhigh的單向移動，直至一趟排序結(jié)束后再將樞軸記錄移至正確位置上。整個快速排序的過程可遞歸進(jìn)行。若待排序列中只有一個記錄，顯然已有序，否則進(jìn)行一趟快速排序后再分別對分割所得的兩個子序列進(jìn)行快速排序。3 .簡單選擇排序：其操作為，通過n-i次關(guān)鍵字間的比較，從n-i+1個記錄中選出關(guān)鍵字最小的記錄，并和第i(1<i<n)個記錄交換之。顯然，對1n中的記錄進(jìn)行簡單選擇排序的算法為：令i從1至n-1,進(jìn)行n-1趟選擇操作?？梢钥闯觯唵芜x擇排序過程中，所需進(jìn)行記錄移動的操作次數(shù)較少，其最小值為“0”，最大值為3(n-1)。然后，無論記錄的初始排列如

5、何，所需進(jìn)行的關(guān)鍵字之間的比較次數(shù)相同，均為n(n-1)/20程序清單：1.插入排序：#include<>structsqlistintkey11;intlength;insertsort(structsqlist*l)inti,j;for(i=2;i<=l->length;i+)if(l->keyi<l->keyi-1)l->key0=l->keyi;l->keyi=l->keyi-1;for(j=i-2;l->key0<l->keyj;j-)l->keyj+1=l->keyj;l->key

6、j+1=l->key0;main()inti,j,k;structsqlistnum;=10;for(i=1;i<=;i+)scanf("%d",&i);insertsort(&num);printf("charu:")；for(i=1;i<=;i+)printf("%d",i);)測試用例：輸入：233412985645678937輸出：charu:8912233437455667982快速排序：#include<>structsqlistintkey11;intlength;);int

7、partition(structsqlist*l,intlow,inthigh)intpivotkey;l->key0=l->keylow;pivotkey=l->keylow;while(low<high)while(low<high&&l->keyhigh>=pivotkey)high-;l->keylow=l->keyhigh;while(low<high&&l->keylow<=pivotkey)low+;l->keyhigh=l->keylow;)l->keylo

8、w=l->key0;returnlow;)voidqsort(structsqlist*l,intlow,inthigh)intpivotloc;if(low<high)pivotloc=partition(l,low,high);qsort(l,low,pivotloc-1);qsort(l,pivotloc+1,high);)voidquicksort(structsqlist*l)(qsort(l,1,l->length);)main()(inti,j;structsqlistnum;=10;for(i=1;i<=;i+)scanf("%d",

9、&i);quicksort(&num);printf("kuaisu：")；for(i=1;i<=;i+)printf("%d",i);)測試用例：輸入：233412985645678937輸出：charu:8912233437455667983選擇排序：#include<>structsqlistintkey11;intlength;);intselectminkey(structsqlist*l,inta)inti,j=a;for(i=a;i<=l->length;i+)if(l->keyi<

10、l->keyj)j=i;returnj;)voidselectsort(structsqlist*l)inti,j,k;for(i=1;i<l->length;i+)j=selectminkey(l,i);if(i!=j)k=l->keyi;l->keyi=l->keyj;l->keyj=k;main()inti,j;structsqlistnum;=10;for(i=1;i<=;i+)scanf("%d",&i);selectsort(&num);printf("xuanze：")；for

11、(i=1;i<=;i+)printf("%d",i);測試用例：輸入：233412985645678937輸出：charu:891223343745566798編程感想：本次編程總共使用了三種排序方法，而這三種編程方法放在一起進(jìn)行編寫時，很容易就讓我們對齊難易程度有了更深刻的了解。首先，三種排序中，我們都像查表那樣，設(shè)置了哨兵，而哨兵的使用可以減少對整個表的驗空操作，使程序更加節(jié)省空間。其次，對于插入排序，每次都要對一段序列進(jìn)行檢索，每排一次所要檢索的序列長度減一，其時間發(fā)雜度為O(nA2)0接著，對于快速排序，這個程序是比較復(fù)雜的，總共是3個函數(shù)，并且使用了遞歸的方法，這是但是，這種算法卻是最優(yōu)越的，平均性能也是最好的，我在編這個程序時，對其排序的思想有了進(jìn)一步的了解，并努力