排序綜合實驗報告

1、數(shù)據(jù)結(jié)構(gòu)排序算法綜合實驗報告姓 名： xx x x 班 級： 10電信1 學 號： xxx 指導老師： 胡圣榮 日期： 2012.12.152013.1.5 華南農(nóng)業(yè)大學工程學院算法基本思想：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）冒泡排序：設想排序表R1到Rn垂直放置，將每個記錄Ri看作是重量為Ri.key的氣泡；根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R，凡違反本原則的輕氣泡，就使其向上“漂浮”，如此反復進行，直到最后任何兩個氣泡都是輕

3、者在上，重者在下為止。（2）快速排序：在待排序的n個記錄中任取一個作為“基準”，將其與記錄分為兩組，第一組中個記錄的鍵值均小于或等于基準的鍵值，第二組中個記錄的鍵值均大于或等于基準的鍵值，而基準就排在這兩組中間（這也是該記錄的最終位置），這稱為一趟快速排序（或一次劃分）。對所分成的兩組重復上述方法，直到所有記錄都排在適當位置為止。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個記錄在重建為堆，于是便得到次小值。如此反復執(zhí)行，知道全部元素輸出完，從而得到一個有序序列。4、并歸排序：指將若干個已

5、排序的子表合成一個有序表。（1）二路并歸排序：開始時，將排序表R1到Rn看成n個長度為1的有序子表，把這些子表兩兩并歸，便得到n/2個有序的子表（當n為奇數(shù)時，并歸后仍是有一個長度為1的子表）；然后，再把這n/2個有序的子表兩兩并歸，如此反復，直到最后得到一個程度為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)學號xxxxxxxxxx主板宏碁 JE40_CP班級10電信1班操作系統(tǒng)Microsoft Windows 7 旗艦版 (6

6、4位/Service Pack 1)電話xxxxxxxxxxxxx編譯軟件Visual C+ 6.0 1042*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.2

7、616640.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.

8、90.0999994999.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.094

9、0.4990.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.017

10、6.45735.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.插入排序、冒泡排序、選擇排序的

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

13、表類型，0號單元不用_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ù)

14、) int 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) bre

16、ak; void 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.

17、key) /交換記錄 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 P

18、artition(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; /只有一個記錄或無記錄時無需排序

19、i=Partition(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指向R

20、p的左孩子MPP,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=

21、1;i-) 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)

22、; /R1到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+; /取小者復制 else MPP,R1k+=Rj+; while(i=mid) MPP,R1k+=Ri+; /復制左子表的剩余記錄 while(j=high) MPP,R1k+=Rj+; /復制右子表的剩余記

23、錄void 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+) /將最后一個子表復制到R1中 MPP,R1j=Rj;v

24、oid MergeSort(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=r