排序綜合實驗資料報告材料

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

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

3、 ，如此反復進行，直到最后任何兩個氣泡都是輕者在上，重者在下 為止。（ 2）快速排序：在待排序的 n 個記錄中任取一個作為“基準” ，將其與記錄分為兩組，第一 組中個記錄的鍵值均小于或等于基準的鍵值， 第二組中個記錄的鍵值均大于或等于基準的鍵 值，而基準就排在這兩組中間（這也是該記錄的最終位置），這稱為一趟快速排序（或一次劃分）。對所分成的兩組重復上述方法，直到所有記錄都排在適當位置為止。3、選擇排序 ：每次從待排序的記錄中選出關鍵字最?。ɑ蜃畲螅┑挠涗洠樞蚍旁谝雅藕?序的子序列的后面（或最前） ，直到全部記錄排序完畢。（1） 直接選擇排序：首先，所有記錄組成初始無序區(qū)R1到Rn，從中選出鍵

4、值最小的記錄，與無序區(qū)第一個記錄 R1交換；新的無序區(qū)為 R2到Rn，從中再選出鍵值最小的記 錄，與無序區(qū)第一個記錄 R2 交換；類似，第 i 趟排序時 R1 到 Ri-1 是有序區(qū)，無序區(qū) 為 Ri 到 Rn ，從中選出鍵值最小的記錄， 將它與無序區(qū)第一個記錄 Ri 交換， R1 到 Ri 變?yōu)樾碌挠行騾^(qū)。因為每趟排序都使有序區(qū)中增加一個記錄，所以，進行 n-1 趟排序后，整個排序表就全部有序了。（2）堆排序：利用小根堆（或大根堆）來選取當前無序區(qū)中關鍵字最?。ɑ蜃畲螅┑挠涗?來實現(xiàn)排序的。 下面介紹利用大根堆來排序。 首先，將初始無序區(qū)調(diào)整為一個大根堆， 輸出 關鍵字最大的堆頂記錄后， 將

5、剩下的 n-1 個記錄在重建為堆， 于是便得到次小值。 如此反復 執(zhí)行，知道全部元素輸出完，從而得到一個有序序列。4、并歸排序 ：指將若干個已排序的子表合成一個有序表。（1）二路并歸排序：開始時，將排序表 R1到Rn看成n個長度為1的有序子表，把這些子表兩兩并歸， 便得到 n/2 個有序的子表 （當 n 為奇數(shù)時， 并歸后仍是有一個長度為 1 的子表）；然后，再把這 n/2 個有序的子表兩兩并歸，如此反復，直到最后得到一個程度為n 的有序表為止。各種排序?qū)嶒灲Y果:CPU(英特爾)lntel(R) Core(TM) i5 CPU M 4802.67GHzXX存4.00 GB (金士頓 PC3-1

6、0600 DDR3 1333MHz)學號xxxxxxxxxx主板宏碁 JE40_CP班級10電信1班操作系統(tǒng)Microsoft Windows 7旗艦版 (64 位/Service Pack 1)xxxxxxxxxxxxx編譯軟件Visual C+ 6.0email609803959qq.10A42*10A410A52*10A510A62*10A610A72*10A710A81QA5正序逆序直接插入（帶監(jiān)視哨）tC24.874100.1582500.39995.60.0999995000.05（時間）0.1560.54613.39153.417>5min027.486直接插入（無監(jiān)視哨）

7、tC24.874100.1582500.39995.60.0999994999.950.1560.57814.2156.715>5min029.137希爾排序（無監(jiān)視哨）tC0.261664 0598651 4.291069.6094670.5165166.9291084.562461.3717159.61.500012.244580.0150.0160.0470.1090.7171.59111.54427.735208.7220.020.02直接選擇tC0000000.2180.7819.36777.32>5min19.75120.249冒泡（上升）C49.9905199.985

8、4999.9419999.90.0999994999.950.4521.82545.542182.678>5min047.326冒泡（下沉）C49.9904199.964999.7819999.90.0999994999.950.4831.90247.239189.081>5min047.503快速（遞歸）tC0.170775 0361618 2.170424.7964625.812557.6668320.86647.4543493.62201.32201.40.010.010.0310.0620.2190.4842.5775.29729.37718.02618.195堆排序（非遞

9、歸）tC0.235479 0510793 3.(19386.4389536.793277.5876434.639909.2815012.883.112522.926640.0160.0160.0470.0940.4990.9687.22317.093123.4290.040.05堆排序（遞歸）tC0.235479 0510793 3.019386.4389536.793277.5876434.639909.2815012.883.112522.9266400.0150.0780.1250.9031.82513.65931.742235.3460.060.07二路歸并（非遞歸）tC0.12367

10、6 0267361 1.566513.3330518.716639.4319224.002468.0062540.150.8779860.81502400.0150.0460.0620.250.5463.0176.45735.3090.030.03實驗結果原因分析和結論：1. 插入、冒泡排序的速度較慢，但參加排序的序列局部或整體有序時，這種排序能達到較 快的速度。反而在這種情況下，快速排序反而慢了。當 n 較小時，對穩(wěn)定性不作要求時宜用選擇排序，對穩(wěn)定性有要求時宜用插入或冒泡排序。 若待排序的記錄的關鍵字在一個明顯有限圍時 ,且空間允許是用桶排序。當 n 較大時，關鍵字元素比較隨機，對穩(wěn)定性沒

11、要求宜用快速排序。當 n 較大時，關鍵字元素可能出現(xiàn)本身是有序的，對穩(wěn)定性有要求時，空間允許的情況下。 宜用歸并排序。當 n 較大時，關鍵字元素可能出現(xiàn)本身是有序的，對穩(wěn)定性沒有要求時宜用堆排序。2. 插入排序、冒泡排序、選擇排序的時間復雜性為 O（n2） 其它非線形排序的時間復雜性為 O（nlog2n） 線形排序的時間復雜性為 O（n）;3. 在算法運行期間，運行 QQ軟件、360安全衛(wèi)士、 360殺毒、word文檔、ppt、酷狗等軟件 會影響絕對時間和邏輯時間，使時間增大4. 隨著 n 的取值增大，算法的實際時間增長速度逐漸增大。5. 直接插入排序（有、無監(jiān)視哨） 、冒泡排序（上升、下沉）

12、 、堆排序（遞歸、非遞歸）的關 鍵字比較次數(shù)相同， 但絕對時間相差比較大； 直接選擇排序與冒泡排序的關鍵字比較次數(shù)相 近。6. 相比較其他同學的數(shù)據(jù)，直接插入（有、無監(jiān)視哨） ，直接選擇，冒泡（上升、下沉）的 結果相差較小， 希爾選擇結果相差很大， 另快速 （遞歸），堆（遞歸， 非遞歸），二路歸并 （非 遞歸）結果并不會受計算機環(huán)境而不同。附錄：源程序極其代碼#define CPP C+#define MPP M+#define MP2 M+=2#define MP3 M+=3#include <fstream.h>#include <iomanip.h>#includ

13、e <stdlib.h>#include <time.h>#include <math.h>const int maxsize=20000;/排序表容量typedef int datatype;typedef struct datatype key;/關鍵字域/ othertype other;/其它域 rectype;/ 記錄類型typedef rectype listmaxsize+2; / 排序表類型， 0 號單元不用_int64 C,M;/比較和移動次數(shù)void check(list R,int n) / 檢驗排序結果int i;for(i=2;i&

14、lt;=n;i+)if(Ri.key<Ri-1.key) cout<<"Error!n"return; cout<<"Correct! "void disp(list R,int n) / 顯示排序后的結果int i;for(i=1;i<=n;i+) cout<<setw(4)<<Ri.key<<" "/ if(i%20=0) cout<<endl;cout<<endl;void InsertSort1(list R,int n) / 直接

15、插入排序，帶監(jiān)視哨 ( 并不改變關鍵字次數(shù) ) int i,j;for(i=2;i<=n;i+) 依次插入 R2,R3,Rnif(CPP,Ri.key>=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.key<Rj.key);MPP,Rj+1=R0;/ 插入 Rivoid InsertSort2(list R,int n) / 直接插入排序，無監(jiān)視哨int i,j;rectype

16、 x;/x 為輔助量 (用 R0 代替時間變長 )for(i=2;i<=n;i+) /進行 n-1 次插入if(CPP,Ri.key>=Ri-1.key) continue;MPP,x=Ri;/ 待排記錄暫存到 xj=i-1;do / 順序比較和移動MPP,Rj+1=Rj;j-; while(j>=1 && (CPP,x.key<Rj.key);MPP,Rj+1=x;/ 插入 Rivoid ShellSort1(list R,int n)/ 一趟插入排序， h 為本趟增量int h,i,j,k;for(h=n/2;h>=1;h=h/2)for(i=

17、1;i<=h;i+)/i 為組號for(j=i+h;j<=n;j+=h)/每組從第 2 個記錄開始插入if(CPP,Rj.key>=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(k>0&&(CPP,R0.key<Rk.key);MPP,Rk+h=R0;/ 插入 Rjif(h=1) break;void SelectS

18、ort1(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ū)從前向后找鍵值最小的記錄 Rk if(Rj.key<Rk.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; for(i=1;i<=n-1;i+) flag=0; for(j=n;j>=i+1;j-)/x為輔助量（

19、可用R0代替）/做 n-1 趟掃描/置未交換標志/從下向上掃描/交換記錄if(CPP,Rj.key<Rj-1.key) flag=1;MP3,x=Rj;Rj=Rj-1;Rj-1=x;/ 交換 if(!flag) break;/本趟未交換過記錄，排序結束void BubbleSort2(list R,int n) / 下沉法，冒泡排序 int i,j,flag;rectype x; for(i=1;i<=n-1;i+) flag=0; for(j=1;j<=n-i;j+)/X為輔助量（可用R0代替）/做 n-1 趟掃描 /置未交換標志 /從上向下掃描if(CPP,Rj.key&

20、gt;Rj+1.key) / 交換記錄 flag=1; MP3,x=Rj;Rj=Rj+1;Rj+1=x;/ 交換 if(!flag) break; /本趟未交換過記錄，排序結束int Partition(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) && i<j) j-;/從右向左掃描 (取消=變快)if(i<j) MPP,Ri=Rj;i+

21、;/交換 Ri 和 Rjwhile(CPP,Ri.key<=x.key) && i<j) i+;/ 從左向右掃描if(i<j) MPP,Rj=Ri;j-;/交換 Ri和 Rj while(i<j);MPP,Ri=x;/基準移到最終位置return i;/最后 i=jvoid QuickSort1(list R,int s,int t) / 對 Rs到 Rt快速排序，遞歸算法mint i;if(s>=t) return;/只有一個記錄或無記錄時無需排序i=Partition(R,s,t);對Rs到Rt做劃分QuickSort1(R,s,i-1);/遞

22、歸處理左區(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; while(j<=q)/j 指向 Rp 的左孩子if(j<q && (CPP,Rj.key<Rj+1.key) j+;/j 指向 Rp 的右孩子if(CPP,R0.key>=Rj.key) break;/根結點鍵值大于孩子結點，已經(jīng)是堆，調(diào)整結束MPP,Rp=Rj; p=j;j=2*p;MPP,Rp=R0;/將 Rj

23、換到雙親位置上/修改當前被調(diào)整結點/j 指向 Rp 的左孩子/原根結點放入正確位置void Sift2(list R,int p,int q)/堆圍為 RpRq, 調(diào)整 Rp 為堆，遞歸算法int j; if(p>=q) return;j=2*p; if(j>q) return;/只有一個元素或無元素if(j<q && (CPP,Rj.key<Rj+1.key) j+;/j 指向 Rp 的右孩子if(CPP,Rp.key>=Rj.key) return;/根結點關鍵字已最大MPP,R0=Rj;MPP,Rj=Rp;MPP,Rp=R0;/交換Rj和Rp

24、 , R0作輔助量Sift2(R,j,q);/遞歸void HeadSort1(list R,int n)堆R1到Rn進行堆排序/建初始堆/進行 n-1 趟堆排序/堆頂和當前堆底交換，R0作輔助量int i; for(i=n/2;i>=1;i-) Sift1(R,i,n); for(i=n;i>=2;i-)MPP,R0=R1;MPP,R1=Ri;MPP,Ri=R0;/R1 到 Ri-1 重建成新堆Sift1(R,1,i-1);void HeadSort2(list R,int n) int i;for(i=n/2;i>=1;i-) Sift2(R,i,n); for(i=n;

25、i>=2;i-)MPP,R0=R1;MPP,R1=Ri;MPP,Ri=R0;Sift2(R,1,i-1);/堆R1到Rn進行堆排序/建初始堆/進行 n-1 趟堆排序/堆頂和當前堆底交換，R0作輔助量/R1 到 Ri-1 重建成新堆void Merge(list R,list R1,int low,int mid,int high) /合并 R 的兩個子表： RlowRmid 、Rmid+1Rhigh ，結果在 R1 中 int i,j,k; i=low;j=mid+1;/取小者復制/復制左子表的剩余記錄/復制右子表的剩余記錄k=low; while(i<=mid &&

26、; 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+;void MergePass(list R,list R1,int n,int len) / 對 R 做一趟歸并，結果在 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

27、=i+2*len;/i 指向下一對子表起始點if(i+len-1<n)/剩下兩個子表，其中一個長度小于lenMerge(R,R1,i,i+len-1,n);for(j=i;j<=n;j+)/ 將最后一個子表復制到R1 中MPP,R1j=Rj;void MergeSort(list R,list R1,int n) / 對 R 二路歸并排序，結果在 R 中 (非遞歸算法 ) int len;len=1; while(len<n) MergePass(R,R1,n,len);len=len*2;/一趟歸并，結果在 R1 中MergePass(R1,R,n,len);len=len

28、*2;/再次歸并，結果在 R 中int random1(int num) return rand(); /0RAND_MAX=32767int random3(int num) / 素數(shù)模乘同余法 ,0Mint A=16807; / 16807,39722040,764261123,630360016 48271?int M=2147483647; /有符號4字節(jié)最大素數(shù)，2人31-1int Q=M/A;int R=M%A;static int x=1，n=0，g=0; /seed(set to 1)static double r，r1=0，r2=0;int x1;x1=A*(x%Q)-R*(

29、x/Q);if(x1>=0) x=x1;else x=x1+M;r=1.*x/M;if(r>0.5) g+;n+;r1+=r;r2+=r*r;if(n%maxsize=0) cout<<"x="<<r<<" "<<g<<" "<<"n="<<n<<" "<<r1/n<<" "<<r2/n<<" "<

30、;<(r2-r1)/n+.25<<endl; 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=random3(n);/生成 0-n 之間的隨機數(shù)do C=M=0;/取出初始數(shù)據(jù)用于排序for(i=1;i<=n;i+)Ri.key=S