排序綜合實驗報告

1、數(shù)據(jù)結(jié)構(gòu)排序算法綜合實驗報告姓 名： xx x x 班 級： 10電信1 學(xué) 號： xxx 指導(dǎo)老師： 胡圣榮 日期： 2012.12.152013.1.5 華南農(nóng)業(yè)大學(xué)工程學(xué)院算法基本思想：1、插入排序：每次將一個待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排序好的序列中的適當位置，直到全部記錄插入完畢為止。（1）直接插入排序：在排序過程中，每次都講無序區(qū)中第一條記錄插入到有序區(qū)中適當位置，使其仍保持有序。初始時，取第一條記錄為有序區(qū)，其他記錄為無序區(qū)。顯然，隨著排序過程的進行，有序區(qū)不斷擴大，無序區(qū)不斷縮小。最終無序區(qū)變?yōu)榭?，有序區(qū)中包含了所有的記錄，排序結(jié)束。（2）希爾排序：將排序表分成若

2、干組，所有相隔為某個“增量”的記錄為一組，在各組內(nèi)進行直接插入排序；初始時增量d1較大，分組較多（每組的記錄數(shù)少），以后增量逐漸減少，分組減少（每組的記錄數(shù)增多），直到最后增量為1（d1d2.dt=1）,所有記錄放為一組，再整體進行一次直接插入排序。2、交換排序：每次比較兩個待排序的記錄，如果發(fā)現(xiàn)他們關(guān)鍵字的次序與排序要求相反時就交換兩者的位置，直到?jīng)]有反序的記錄為止。（1）冒泡排序：設(shè)想排序表r1到rn垂直放置，將每個記錄ri看作是重量為ri.key的氣泡；根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組r，凡違反本原則的輕氣泡，就使其向上“漂浮”，如此反復(fù)進行，直到最后任何兩個氣泡都是輕

3、者在上，重者在下為止。（2）快速排序：在待排序的n個記錄中任取一個作為“基準”，將其與記錄分為兩組，第一組中個記錄的鍵值均小于或等于基準的鍵值，第二組中個記錄的鍵值均大于或等于基準的鍵值，而基準就排在這兩組中間（這也是該記錄的最終位置），這稱為一趟快速排序（或一次劃分）。對所分成的兩組重復(fù)上述方法，直到所有記錄都排在適當位置為止。3、選擇排序：每次從待排序的記錄中選出關(guān)鍵字最小（或最大）的記錄，順序放在已排好序的子序列的后面（或最前），直到全部記錄排序完畢。（1）直接選擇排序：首先，所有記錄組成初始無序區(qū)r1到rn，從中選出鍵值最小的記錄，與無序區(qū)第一個記錄r1交換；新的無序區(qū)為r2到rn，從

4、中再選出鍵值最小的記錄，與無序區(qū)第一個記錄r2交換；類似，第i趟排序時r1到ri-1是有序區(qū)，無序區(qū)為ri到rn，從中選出鍵值最小的記錄，將它與無序區(qū)第一個記錄ri交換，r1到ri變?yōu)樾碌挠行騾^(qū)。因為每趟排序都使有序區(qū)中增加一個記錄，所以，進行n-1趟排序后，整個排序表就全部有序了。（2）堆排序：利用小根堆（或大根堆）來選取當前無序區(qū)中關(guān)鍵字最?。ɑ蜃畲螅┑挠涗泚韺崿F(xiàn)排序的。下面介紹利用大根堆來排序。首先，將初始無序區(qū)調(diào)整為一個大根堆，輸出關(guān)鍵字最大的堆頂記錄后，將剩下的n-1個記錄在重建為堆，于是便得到次小值。如此反復(fù)執(zhí)行，知道全部元素輸出完，從而得到一個有序序列。4、并歸排序：指將若干個已

5、排序的子表合成一個有序表。（1）二路并歸排序：開始時，將排序表r1到rn看成n個長度為1的有序子表，把這些子表兩兩并歸，便得到n/2個有序的子表（當n為奇數(shù)時，并歸后仍是有一個長度為1的子表）；然后，再把這n/2個有序的子表兩兩并歸，如此反復(fù)，直到最后得到一個程度為n的有序表為止。各種排序?qū)嶒灲Y(jié)果：cpu(英特爾)intel(r) core(tm) i5 cpu m 480 2.67ghz姓名xx內(nèi)存4.00 gb (金士頓 pc3-10600 ddr3 1333mhz)學(xué)號xxxxxxxxxx主板宏碁 je40_cp班級10電信1班操作系統(tǒng)microsoft windows 7 旗艦版 (6

6、4位/service pack 1)電話xxxxxxxxxxxxx編譯軟件visual c+ 6.0 email6098039591042*1041052*1051062*1061072*107108105正序逆序直接插入(帶監(jiān)視哨）c24.874100.1582500.39995.60.0999995000.05t(時間)0.1560.54613.39153.4175min027.486直接插入(無監(jiān)視哨）c24.874100.1582500.39995.60.0999994999.95t0.1560.57814.2156.7155min029.137希爾排序(無監(jiān)視哨)c0.2616640

7、.5986514.291069.6094670.5165166.9291084.562461.3717159.61.500012.24458t0.0150.0160.0470.1090.7171.59111.54427.735208.7220.020.02直接選擇c000000t0.2180.7819.36777.325min19.75120.249冒泡(上升)c49.9905199.9854999.9419999.90.0999994999.95t0.4521.82545.542182.6785min047.326冒泡(下沉）c49.9904199.964999.7819999.90.099

8、9994999.95t0.4831.90247.239189.0815min047.503快速(遞歸)c0.1707750.3616182.170424.7964625.812557.6668320.86647.4543493.62201.32201.4t0.010.010.0310.0620.2190.4842.5775.29729.37718.02618.195堆排序(非遞歸) c0.2354790.5107933.019386.4389536.793277.5876434.639909.2815012.883.112522.92664t0.0160.0160.0470.0940.4990

9、.9687.22317.093123.4290.040.05堆排序(遞歸)c0.2354790.5107933.019386.4389536.793277.5876434.639909.2815012.883.112522.92664t00.0150.0780.1250.9031.82513.65931.742235.3460.060.07二路歸并(非遞歸) c0.1236760.2673611.566513.3330518.716639.4319224.002468.0062540.150.8779860.815024t00.0150.0460.0620.250.5463.0176.4573

10、5.3090.030.03實驗結(jié)果原因分析和結(jié)論：1. 插入、冒泡排序的速度較慢，但參加排序的序列局部或整體有序時，這種排序能達到較快的速度。反而在這種情況下，快速排序反而慢了。當n較小時，對穩(wěn)定性不作要求時宜用選擇排序，對穩(wěn)定性有要求時宜用插入或冒泡排序。若待排序的記錄的關(guān)鍵字在一個明顯有限范圍內(nèi)時,且空間允許是用桶排序。當n較大時，關(guān)鍵字元素比較隨機，對穩(wěn)定性沒要求宜用快速排序。當n較大時，關(guān)鍵字元素可能出現(xiàn)本身是有序的，對穩(wěn)定性有要求時，空間允許的情況下。宜用歸并排序。當n較大時，關(guān)鍵字元素可能出現(xiàn)本身是有序的，對穩(wěn)定性沒有要求時宜用堆排序。2.插入排序、冒泡排序、選擇排序的時間復(fù)雜性為

11、o(n2)其它非線形排序的時間復(fù)雜性為o(nlog2n)線形排序的時間復(fù)雜性為o(n);3.在算法運行期間，運行qq軟件、360安全衛(wèi)士、360殺毒、word文檔、ppt、酷狗等軟件會影響絕對時間和邏輯時間，使時間增大4.隨著n的取值增大，算法的實際時間增長速度逐漸增大。5.直接插入排序（有、無監(jiān)視哨）、冒泡排序（上升、下沉）、堆排序（遞歸、非遞歸）的關(guān)鍵字比較次數(shù)相同，但絕對時間相差比較大；直接選擇排序與冒泡排序的關(guān)鍵字比較次數(shù)相近。6.相比較其他同學(xué)的數(shù)據(jù)，直接插入（有、無監(jiān)視哨），直接選擇，冒泡（上升、下沉）的結(jié)果相差較小，希爾選擇結(jié)果相差很大，另快速（遞歸），堆（遞歸，非遞歸），二路歸

12、并（非遞歸）結(jié)果并不會受計算機環(huán)境而不同。附錄：源程序極其代碼#define cpp c+#define mpp m+#define mp2 m+=2#define mp3 m+=3#include #include #include #include #include const int maxsize=20000; /排序表容量typedef int datatype;typedef struct datatype key; /關(guān)鍵字域/ othertype other; /其它域 rectype; /記錄類型typedef rectype listmaxsize+2; /排序表類型，0號

13、單元不用_int64 c,m; /比較和移動次數(shù)void check(list r,int n) /檢驗排序結(jié)果 int i; for(i=2;i=n;i+) if(ri.keyri-1.key) couterror!n;return; coutcorrect! ;void disp(list r,int n) /顯示排序后的結(jié)果 int i; for(i=1;i=n;i+) coutsetw(4)ri.key ;/ if(i%20=0) coutendl; coutendl;void insertsort1(list r,int n) /直接插入排序，帶監(jiān)視哨(并不改變關(guān)鍵字次數(shù)) int

14、i,j; for(i=2;i=ri-1.key) continue; /ri大于有序區(qū)最后一個記錄，則本趟不需插入 mpp,r0=ri; /r0是監(jiān)視哨 j=i-1; do /查找ri的插入位置 mpp,rj+1=rj;j-; /記錄后移，繼續(xù)向前搜索 while(cpp,r0.keyrj.key); mpp,rj+1=r0; /插入ri void insertsort2(list r,int n) /直接插入排序，無監(jiān)視哨 int i,j;rectype x; /x為輔助量(用r0代替時間變長) for(i=2;i=ri-1.key) continue; mpp,x=ri; /待排記錄暫存到

15、x j=i-1; do /順序比較和移動 mpp,rj+1=rj;j-; while(j=1 & (cpp,x.key=1;h=h/2)for(i=1;i=h;i+)/i為組號 for(j=i+h;j=rj-h.key) continue;/rj大于有序區(qū)最后一個記錄， /則不需要插入 mpp,r0=rj; /r0保存待插入記錄，但不是監(jiān)視哨k=j-h; /待插記錄的前一個記錄 do /查找正確的插入位置 mpp,rk+h=rk;k=k-h;/后移記錄，繼續(xù)向前搜索 while(k0&(cpp,r0.keyrk.key);mpp,rk+h=r0; /插入rj if(h=1) break; vo

16、id selectsort1(list r,int n) int i,j,k; for(i=1;i=n-1;i+)/n-1趟排序 k=i; for(j=i+1;j=n;j+)/在當前無序區(qū)從前向后找鍵值最小的記錄rkif(rj.keyrk.key) k=j;if(k!=i)r0=ri;ri=rk;rk=r0;/交換ri和r0，r0作輔助量 void bubblesort1(list r,int n) /上升法冒泡排序 int i,j,flag;rectype x; /x為輔助量(可用r0代替) for(i=1;i=i+1;j-) /從下向上掃描 if(cpp,rj.keyrj-1.key) /

17、交換記錄 flag=1; mp3,x=rj;rj=rj-1;rj-1=x;/交換 if(!flag) break; /本趟未交換過記錄，排序結(jié)束 void bubblesort2(list r,int n) /下沉法，冒泡排序 int i,j,flag;rectype x; /x為輔助量(可用r0代替) for(i=1;i=n-1;i+) /做n-1趟掃描 flag=0; /置未交換標志 for(j=1;jrj+1.key) /交換記錄 flag=1; mp3,x=rj;rj=rj+1;rj+1=x;/交換 if(!flag) break; /本趟未交換過記錄，排序結(jié)束 int partiti

18、on(list r,int p,int q) /對rp到rq劃分，返回基準位置 int i,j;rectype x; /輔助量(可用r0代替) i=p;j=q;mpp,x=rp; /x存基準(無序區(qū)第一個記錄) do while(cpp,rj.key=x.key) & ij) j-;/從右向左掃描(取消=變快) if(ij) mpp,ri=rj;i+; /交換ri和rj while(cpp,ri.key=x.key) & ij) i+;/從左向右掃描 if(ij) mpp,rj=ri;j-; /交換ri和rj while(i=t) return; /只有一個記錄或無記錄時無需排序 i=part

19、ition(r,s,t); /對rs到rt做劃分 quicksort1(r,s,i-1); /遞歸處理左區(qū)間 quicksort1(r,i+1,t); /遞歸處理右區(qū)間void sift1(list r,int p,int q) /堆范圍為rprq,調(diào)整rp為堆，非遞歸算法int j;mpp,r0=rp; /r0作輔助量j=2*p; /j指向rp的左孩子while(j=q)if(jq & (cpp,rj.key=rj.key) break; /根結(jié)點鍵值大于孩子結(jié)點，已經(jīng)是堆，調(diào)整結(jié)束mpp,rp=rj; /將rj換到雙親位置上p=j; /修改當前被調(diào)整結(jié)點j=2*p; /j指向rp的左孩子m

20、pp,rp=r0; /原根結(jié)點放入正確位置void sift2(list r,int p,int q) /堆范圍為rprq,調(diào)整rp為堆，遞歸算法int j;if(p=q) return; /只有一個元素或無元素j=2*p;if(jq) return;if(jq & (cpp,rj.key=rj.key) return; /根結(jié)點關(guān)鍵字已最大mpp,r0=rj; /交換rj和rp，r0作輔助量mpp,rj=rp;mpp,rp=r0;sift2(r,j,q); /遞歸void headsort1(list r,int n) /堆r1到rn進行堆排序int i;for(i=n/2;i=1;i-)

21、sift1(r,i,n); /建初始堆for(i=n;i=2;i-) /進行n-1趟堆排序mpp,r0=r1; /堆頂和當前堆底交換，r0作輔助量mpp,r1=ri;mpp,ri=r0;sift1(r,1,i-1); /r1到ri-1重建成新堆void headsort2(list r,int n) /堆r1到rn進行堆排序int i;for(i=n/2;i=1;i-) sift2(r,i,n); /建初始堆for(i=n;i=2;i-) /進行n-1趟堆排序mpp,r0=r1; /堆頂和當前堆底交換，r0作輔助量mpp,r1=ri;mpp,ri=r0;sift2(r,1,i-1); /r1到

22、ri-1重建成新堆void merge(list r,list r1,int low,int mid,int high) /合并r的兩個子表：rlowrmid、rmid+1rhigh，結(jié)果在r1中 int i,j,k; i=low; j=mid+1; k=low; while(i=mid & j=high) if(cpp,ri.key=rj.key) mpp,r1k+=ri+; /取小者復(fù)制 else mpp,r1k+=rj+; while(i=mid) mpp,r1k+=ri+; /復(fù)制左子表的剩余記錄 while(j=high) mpp,r1k+=rj+; /復(fù)制右子表的剩余記錄void

23、mergepass(list r,list r1,int n,int len) /對r做一趟歸并，結(jié)果在r1中 int i,j; i=1; /i指向第一對子表的起始點 while(i+2*len-1=n) /歸并長度為len的兩個子表 merge(r,r1,i,i+len-1,i+2*len-1); i=i+2*len; /i指向下一對子表起始點 if(i+len-1n) /剩下兩個子表，其中一個長度小于len merge(r,r1,i,i+len-1,n); else /子表個數(shù)為奇數(shù),剩一段 for(j=i;j=n;j+) /將最后一個子表復(fù)制到r1中 mpp,r1j=rj;void me

24、rgesort(list r,list r1,int n) /對r二路歸并排序，結(jié)果在r中(非遞歸算法) int len; len=1; while(len=0) x=x1; else x=x1+m; r=1.*x/m;if(r0.5) g+; n+;r1+=r;r2+=r*r; if(n%maxsize=0) coutx=r g n=n r1/n r2/n (r2-r1)/n+.25endl; return x;void main() rectype *r,*r1,*s; /r1用于歸并排序的輔助存儲，s用于保存初始排序數(shù)據(jù) r=new list;if(r=null) cout數(shù)組太大!n;exit(-1); r1=new list;if(r1=null) cout數(shù)組太大!n;exit(-1); s=new list;if(s=null) cout數(shù)組太大!n;exit(-1); int i,n=maxsize; int choice; clock_t t1,t2; / float s,t; / 正序序列 / for(i=1;i=n;i+) / si.key=i; /反序序列 / for(i=1;i=n;i+) / si.key=n-i+1; / srand( (unsigned)time( null ) ); for(i=1;i=n;i+) si.key=ra