內(nèi)部排序?qū)嶒?yàn)報(bào)告.doc

深 圳 大 學(xué) 實(shí) 驗(yàn) 報(bào) 告 課程名稱： 數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)項(xiàng)目名稱： 內(nèi)部排序 學(xué)院： 專業(yè)： 指導(dǎo)教師： 報(bào)告人 學(xué)號(hào)： 班級(jí)： 實(shí)驗(yàn)時(shí)間： 2012-12-25 實(shí)驗(yàn)報(bào)告提交時(shí)間： 2012-12-25 教務(wù)部制實(shí)驗(yàn)?zāi)康呐c要求： 掌握常見(jiàn)的排序算法的思想及其適用條件。 掌握常見(jiàn)的排序算法的程序?qū)崿F(xiàn)。方法、步驟：輸入一組關(guān)鍵字序列分別實(shí)現(xiàn)下列排序:1. 實(shí)現(xiàn)直接插入排序、折半插入排序和希爾排序算法。2. 實(shí)現(xiàn)冒泡排序和快速排序算法。3. 實(shí)現(xiàn)簡(jiǎn)單選擇排序和堆排序算法。4. 實(shí)現(xiàn)歸并排序算法。5. 在主函數(shù)中設(shè)計(jì)一個(gè)簡(jiǎn)單的菜單，分別測(cè)試上述算法。6. （*）綜合訓(xùn)練：采用幾組不同數(shù)據(jù)測(cè)試各個(gè)排序算法的性能（比較次數(shù)和移動(dòng)次數(shù)）。實(shí)驗(yàn)過(guò)程及內(nèi)容：/頭文件#include#include#include / malloc()等#include / EOF(=Z或F6),NULL#include / atoi()#include / floor(),ceil(),abs() #include / cout,cin/函數(shù)結(jié)果狀態(tài)代碼#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1typedef int Status; typedef int Boolean;/對(duì)兩個(gè)數(shù)值型關(guān)鍵字的比較#define EQ(a,b) (a)=(b)#define LT(a,b) (a)(b)#define LQ(a,b) (a)=(b)/待排記錄的數(shù)據(jù)類型#define MAXSIZE 20 /一個(gè)用作示例的小順序表的最大長(zhǎng)度typedef int KeyType; /定義關(guān)鍵字類型為整型typedef int InfoType; /定義其它數(shù)據(jù)項(xiàng)的類型typedef structKeyType key; /關(guān)鍵字項(xiàng)InfoType otherinfo;/其他數(shù)據(jù)項(xiàng)RedType; /記錄類型typedef structRedType rMAXSIZE+1;/r0閑置或用作哨兵單元int length;/順序表長(zhǎng)度SqList;/順序表類型typedef SqList HeapType; / 堆采用順序表存儲(chǔ)表示/順序表插入排序的函數(shù)void InsertSort(SqList &L);void BInsertSort(SqList &L);void ShellInsert(SqList &L,int dk);void ShellSort(SqList &L,int dlta,int t);/快速排序int Partition(SqList &L,int low,int high);void QSort(SqList &L,int low,int high);void QuickSort(SqList &L);/選擇排序int SelectMinKey(SqList L,int i);void SelectSort(SqList &L);/堆排序void HeapAdjust(HeapType &H,int s,int m);void HeapSort(HeapType &H);/歸并排序void Merge(RedType SR,RedType TR,int i,int m,int n);void MSort(RedType SR,RedType TR1,int s, int t);void MergeSort(SqList &L);/輸出函數(shù)void print(SqList L);void print_H(HeapType H);#define N 8#define T 3void main() RedType dN=20,6,52,1,65,3,88,9,47,8,22,4,39,5,74,7; int i; SqList LL; int dtT=5,3,1; / 增量序列數(shù)組 int choice;s123: cout請(qǐng)選擇要使用的排序算法：n0.退出n; cout1.插入排序n2.交換排序n; coutchoice; switch(choice) case 0: break; case 1: /插入排序 for(i=0;iN;i+) /給LL.r賦值 LL.ri+1=di; LL.length=N; printf(直接插入排序前:n); print(LL); InsertSort(LL); printf(直接插入排序后:n); print(LL); for(i=0;iN;i+) LL.ri+1=di; LL.length=N; printf(n折半插入排序前:n); print(LL); BInsertSort(LL); printf(折半插入排序后:n); print(LL); for(i=0;iN;i+) LL.ri+1=di; LL.length=N; printf(n希爾排序前: n); print(LL); ShellSort(LL,dt,T); printf(希爾排序后: n); print(LL); goto s123; case 2: /交換排序 for(i=0;iN;i+) LL.ri+1=di; LL.length=N; printf(快速排序前:n); print(LL); QuickSort(LL); printf(快速排序后:n); print(LL); goto s123; case 3: /選擇排序 for(i=0;iN;i+) LL.ri+1=di; LL.length=N; printf(簡(jiǎn)單選擇排序前:n); print(LL); SelectSort(LL); printf(簡(jiǎn)單選擇排序后:n); print(LL); HeapType h; for(i=0;iN;i+) h.ri+1=di; h.length=N; printf(n堆排序前:n); print_H(h); HeapSort(h); printf(堆排序后:n); print_H(h); goto s123; case 4: /歸并排序 for(i=0;iN;i+) LL.ri+1=di; LL.length=N; printf(歸并排序前:n); print(LL); MergeSort(LL); printf(歸并排序后:n); print(LL); goto s123; default: cout輸入有誤，請(qǐng)輸入正確的選項(xiàng)！n; goto s123; /順序表插入排序的函數(shù)(3個(gè))void InsertSort(SqList &L)/ 對(duì)順序表L作直接插入排序。算法10.1int i,j; for(i=2;i=L.length;+i) if(LT(L.ri.key,L.ri-1.key) L.r0=L.ri; L.ri=L.ri-1; for(j=i-2;LT(L.r0.key,L.rj.key);-j) L.rj+1=L.rj; L.rj+1=L.r0; /InsertSortvoid BInsertSort(SqList &L) /對(duì)順序表L作折半插入排序。算法10.2 int low,high,m; for(int i=2;i=L.length;+i)L.r0=L.ri;low=1;high=i-1;while(low=high+1;-j) L.rj+1=L.rj; L.rhigh+1=L.r0; /for/BInsertSortvoid ShellInsert(SqList &L,int dk) /對(duì)順序表L作一趟希爾插入排序。本算法是和一趟直接插入排序相比，作了以下修改： / 1.前后記錄位置的增量是dk,而不是1; / 2.r0只是暫存單元,不是哨兵。當(dāng)j=0時(shí),插入位置已找到。算法10.4int i,j;for(i=dk+1;i0<(L.r0.key,L.rj.key);j-=dk)L.rj+dk=L.rj; /記錄后移，查找插入位置L.rj+dk=L.r0; /插入void ShellSort(SqList &L,int dlta,int t) /按增量序列dlta0.t-1對(duì)順序表L作希爾排序。算法10.5int k;for(k=0;kt;+k)ShellInsert(L,dltak); /一趟增量為dltak的插入排序printf(第%d趟排序結(jié)果: n,k+1);print(L);int Partition(SqList &L,int low,int high) /交換順序表L中子表rlow.high的記錄，樞軸記錄到位，并返回其 /所在位置，此時(shí)在它之前（后）的記錄均不大（?。┯谒?。算法10.6(b)KeyType pivotkey;L.r0=L.rlow; /用子表的第一個(gè)記錄作樞軸記錄pivotkey=L.rlow.key; /樞軸記錄關(guān)鍵字while(low high) /從表的兩端交替地向中間掃描while(low=pivotkey)-high;L.rlow=L.rhigh; /將比樞軸記錄小的記錄移到低端while(lowhigh&L.rlow.key=pivotkey)+low;L.rhigh=L.rlow; /將比樞軸記錄大的記錄移到高端L.rlow=L.r0; /樞軸記錄到位return low; /返回樞軸位置void QSort(SqList &L,int low,int high) /對(duì)順序表L中的子序列L.rlow.high作快速排序。算法10.7 if(lowhigh) int pivotloc; pivotloc=Partition(L,low,high); QSort(L,low,pivotloc-1); QSort(L,pivotloc+1,high); /if/QSortvoid QuickSort(SqList &L) /對(duì)順序表L作快速排序。算法10.8QSort(L,1,L.length);/QuickSortint SelectMinKey(SqList L,int i) /返回在L.ri.L.length中key最小的記錄的序號(hào)KeyType min;int j,k;k=i; /設(shè)第i個(gè)為最小min=L.ri.key;for(j=i+1;j=L.length;j+)if(L.rj.keymin) /找到更小的k=j;min=L.rj.key;return k;void SelectSort(SqList &L) /對(duì)順序表L作簡(jiǎn)單選擇排序。算法10.9 int i,j,temp; for(i=1;iL.length;+i) j=SelectMinKey(L,i);if(i!=j)temp=i;i=j;j=temp; void HeapAdjust(HeapType &H,int s,int m) /算法10.10 /已知H.rs.m中記錄的關(guān)鍵字除H.rs.key之外均滿足堆的定義，本函數(shù) /調(diào)整H.rs的關(guān)鍵字,使H.rs.m成為一個(gè)大頂堆(對(duì)其中記錄的關(guān)鍵字而言)RedType rc;int j;rc=H.rs;for(j=2*s;j=m;j*=2) /沿key較大的孩子結(jié)點(diǎn)向下篩選if(j0;-i) HeapAdjust(H,i,H.length); for( i=H.length;i1;-i) H.r0=H.r1; H.r1=H.ri; H.ri=H.r0; HeapAdjust(H,1,i-1); /for/HeapSortvoid Merge(RedType SR,RedType TR,int i,int m,int n) /將有序的SRi.m和SRm+1.n歸并為有序的TRi.n 算法10.12int j,k,l;for(j=m+1,k=i;i=m&j=n;+k) /將SR中記錄由小到大地并入TRif LQ(SRi.key,SRj.key)TRk=SRi+;elseTRk=SRj+;if(i=m)for(l=0;l=m-i;l+)TRk+l=SRi+l; /將剩余的SRi.m復(fù)制到TRif(j=n)for(l=0;l=n-j;l+)TRk+l=SRj+l; /將剩余的SRj.n復(fù)制到TRvoid MSort(RedType SR,RedType TR1,int s, int t) /將SRs.t歸并排序?yàn)門R1s.t。算法10.13RedType TR2MAXSIZE;if(s=t)TR1s=SRs;else int m=(s+t)/2; MSort(SR,TR2,s,m); MSort(SR,TR2,m+1,t); Merge(TR2,TR1,s,m,t);void MergeSort(SqList &L) /對(duì)順序表L作歸并排序。算法10.14MSort(L.r,L.r,1,L.length);void print(SqList L)int i;for(i=1;i=L.length;i+)printf( (%d,%d) ,L.ri.key,L.ri.otherinfo);printf(n);vo