實(shí)驗(yàn)九 內(nèi)部排序

1、實(shí)驗(yàn)九 內(nèi)部排序1、 實(shí)驗(yàn)?zāi)康?、 深入了解各種排序方法的基本思想、排序過程。2、 熟練掌握各種排序方法的實(shí)現(xiàn)和特點(diǎn)，掌握各種排序方法的時(shí)間復(fù)雜度的分析方法。3、 掌握各種排序方法所適應(yīng)的不同場合，能加以靈活運(yùn)用。2、 實(shí)驗(yàn)內(nèi)容和要求2、 典型內(nèi)部排序算法的比較。（1） 針對“12.11.4參考源程序”，隨機(jī)產(chǎn)生整數(shù)樣本，進(jìn)行8種排序，并比較各種排序算法的執(zhí)行時(shí)間，如執(zhí)行時(shí)間均為0，可考慮增大樣本，如加大至5000。（2） 修改“12.11.4參考源程序”，輸出8種排序算法的每一趟結(jié)果。3、 實(shí)驗(yàn)過程及結(jié)果（1）源代碼：#include stdio.h#include conio.h#incl

2、ude stdlib.h#include time.h#define OK 1#define ERROR 0#define OVERFLOW -1#define MAXSIZE 5000/設(shè)待排序記錄數(shù)不超過5000個(gè)typedef int Status;typedef int KeyType;/定義關(guān)鍵字為整型typedef int InfoType;/定義其它數(shù)據(jù)項(xiàng)類型為整型typedef struct KeyType key;/關(guān)鍵字項(xiàng)InfoType otherinfo;/其他數(shù)據(jù)項(xiàng)RedType;typedef struct /定義順序表的結(jié)構(gòu)RedType *r;/存儲空間基址，人

3、r0閑置或用作哨兵或用作緩沖區(qū)int length;/順序表長度SqList;Status InitSqList(SqList *L);/構(gòu)造一個(gè)空的順序表LStatus CreateSqList(SqList *L);/輸入數(shù)據(jù)元素個(gè)數(shù)，隨機(jī)產(chǎn)生整數(shù)樣本Status CopySqList(SqList L_BAK,SqList *L);/Status OutputSqList(SqList L);/輸出排序之后的數(shù)據(jù)int LT(KeyType e1,KeyType e2);/判斷數(shù)據(jù)元素e1是否小余e2void Swap(RedType *e1,RedType *e2);/數(shù)據(jù)元素e1和e

4、2互換Status InsertSort(SqList *L);/直接排入排序Status BInsertSort(SqList *L);/折半插入排序Status ShellInsert(SqList *L,int dk);/一趟希爾排序Status ShellSort(SqList *L,int dlta,int t);/希爾排序Status BubbleSort(SqList *L);/冒泡排序int Partition(SqList *L,int low,int high);/一趟快速排序void QSort(SqList *L,int low,int high);/對L中子序列L.r

5、low.high進(jìn)行快速排序Status QuickSort(SqList *L);/對L進(jìn)行快速排序Status SelectSort(SqList *L);/直接選擇排序Status HeapAdjust(SqList *H,int S,int m);/調(diào)整L.rs的關(guān)鍵字，使L.rs.m成大頂堆Status HeapSort(SqList *L);/堆排序Status Merge(SqList *L,int low,int mid,int high);/將兩個(gè)有序的子序列L.rlow.mid和L.rmid.high歸并成有序的序列L.rlow.highvoid MSort(SqList

6、*L,int len);/對L.r1.n做一趟歸并排序Status MergeSort(SqList *L);/對L.r1.n自底向上二路歸并排序void main()/典型內(nèi)部排序的比較SqList L,L_BAK;int select,flag=1,t,dltaMAXSIZE;double duration;clock_t start,finish;/clock_t用于計(jì)時(shí)InitSqList(&L);InitSqList(&L_BAK);CreateSqList(&L_BAK);t=0;/產(chǎn)生希爾排序的增量序列dlta0.tdlta0=L_BAK.length/2;while(dltat

7、1)dltat+1=dltat/2;t+;while(flag)CopySqList(L_BAK,&L);printf(Please select:n);printf(1.InsertSortn);printf(2.BInsertSortn);printf(3.ShellSort n);printf(4.BubbleSortn);printf(5.QuickSort n);printf(6.SelectSortn);printf(7.HeapSort n);printf(8.MergeSort n);printf(9.Exit n);scanf(%d,&select);switch(selec

8、t)case 1:printf(nNow is in InsertSort.);start=clock();InsertSort(&L);finish=clock();break;case 2:printf(nNow is in BInsertSort.);start=clock();BInsertSort(&L);finish=clock();break;case 3:printf(nNow is in ShellSort.);start=clock();ShellSort(&L,dlta,t+1);finish=clock();break;case 4:printf(nNow is in

9、BUbbleSort.);start=clock();BubbleSort(&L);finish=clock();break;case 5:printf(nNow is in QuickSort.);start=clock();QuickSort(&L);finish=clock();break;case 6:printf(nNow is in SelectSort.);start=clock();SelectSort(&L);finish=clock();break;case 7:printf(nNow is in HeapSort.);start=clock();HeapSort(&L);

10、finish=clock();break;case 8:printf(nNow is in MergeSort.);start=clock();MergeSort(&L);finish=clock();break;default:flag=0;printf(Press any key to exit!n);getch();printf(n);OutputSqList(L);duration=(double)(finish-start)/CLK_TCK;/輸出算數(shù)時(shí)間printf(nThe Sort Spend: %lf secondsn,duration);Status InitSqList(

11、SqList *L)L-r=(RedType *)malloc(MAXSIZE+1)*sizeof(RedType);/分配內(nèi)存if(!L-r)exit(OVERFLOW);L-length=0;return OK;Status CreateSqList(SqList *L)int i;srand(time(NULL);printf(nPlease Input the Number of UnSorted Data: );scanf(%d,&L-length);for(i=1;ilength;i+)L-ri.key=rand();/隨機(jī)產(chǎn)生整數(shù)樣本printf(nnThe UnSorted d

12、ata is:n);for(i=1;ilength;i+)printf(%8d,L-ri.key);printf(n);return OK;Status CopySqList(SqList L_BAK,SqList *L)int i;if(!L_BAK.length)printf(The SqList is Empty!);return ERROR;for(i=1;iri.key=L_BAK.ri.key;L-length=L_BAK.length;return OK;Status OutputSqList(SqList L)int i;printf(nThe Length of SqList

13、 is:%dn,L.length);printf(nnThe Sorted Data is:n);for(i=1;i=L.length;i+)printf(%8d,L.ri);printf(n);return OK;int LT(KeyType e1,KeyType e2)if(e1length)printf(The SqList is Empty!);return ERROR;for(i=2;ilength;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=

14、L-rj;L-rj+1=L-r0;return OK;Status BInsertSort(SqList *L)int i,j,mid,low,high;if(!L-length)printf(The SqList is Empty!);return ERROR;for(i=2;ilength;i+)L-r0=L-ri;low=1;high=i-1;while(lowr0.key,L-rmid.key)high=mid-1;elselow=mid+1;for(j=i-1;j=high+1;j-)L-rj+1=L-rj;L-rhigh+1=L-r0;return OK;Status ShellI

15、nsert(SqList *L,int dk)int i,j;for(i=dk+1;ilength;i+)if(LT(L-ri.key,L-ri-dk.key)L-r0=L-ri;for(j=i-dk;j0<(L-r0.key,L-rj.key);j-=dk)L-rj+dk=L-rj;L-rj+dk=L-r0;return OK;Status ShellSort(SqList *L,int dlta,int t)int k;if(!L-length)printf(The SqList is Empty!);return ERROR;for(k=0;klength)printf(The Sq

16、List is Empty!);return ERROR;for(i=1;ilength;i+)for(j=1;jlength-i;j+)if(!LT(L-rj.key,L-rj+1.key)Swap(&L-rj,&L-rj+1);return OK;int Partition(SqList *L,int low,int high)int pivotkey;L-r0=L-rlow;pivotkey=L-rlow.key;while(lowhigh)while(lowrhigh.key=pivotkey)high-;L-rlow=L-rhigh;while(lowrhigh.keyrhigh=L

17、-rlow;L-rlow=L-r0;return low;void QSort(SqList *L,int low,int high)int pivotkey;if(lowlength)printf(The SqList is Empty!);return ERROR;QSort(L,1,L-length);return OK;Status SelectSort(SqList *L)int i,j,min;if(!L-length)printf(The SqList is Empty!);return ERROR;for(i=1;ilength;i+)min=i;for(j=i+1;jleng

18、th-i;j+)if(LT(L-rj.key,L-rmin.key)min=j;if(min!=i)Swap(&L-ri,&L-rmin);return OK;Status HeapAdjust(SqList *H,int s,int m)int j;H-r0=H-rs;for(j=2*s;j=m;j*=2)if(jrj.key,H-rj+1.key)j+;if(!LT(H-r0.key,H-rj.key)break;H-rs=H-rj;s=j;H-rs=H-r0;return OK;Status HeapSort(SqList *H)int i;if(!H-length)printf(The

19、 SqList is Empty!);return ERROR;for(i=H-length/2;i0;i-)HeapAdjust(H,i,H-length);for(i=H-length;i1;i-)Swap(&H-r1,&H-ri);HeapAdjust(H,1,i-1);return OK;Status Merge(SqList *L,int low,int mid,int high)int i=low,j=mid+1,k=0;/賦初值SqList L1;/L1暫存L.rlow.mid和L.rmid+1.high歸并后的結(jié)果L1.r=(RedType *)malloc(high-low+

20、1)*sizeof(RedType);/分配內(nèi)存if(!L1.r)exit(OVERFLOW);while(i=mid&jri.key,L-rj.key)?L-ri+:L-rj+;while(iri+;while(jrj+;for(k=0,i=low;iri.key=L1.rk.key;/將歸并結(jié)果復(fù)制回L-rlow.highreturn OK;void MSort(SqList *L,int len)int i;for(i=1;i+2*len-1length;i=i+2*len)/歸并長度為len的兩個(gè)相鄰的子序列Merge(L,i,i+len-1,i+2*len-1);if(i+len-1

21、length)/仍有一個(gè)子序列，其中后一個(gè)長度小于len;此時(shí),若ilength且i+len-1=L-length時(shí)，則剩余一個(gè)子序列輪空，無須歸并Merge(L,i,i+len-1,L-length);/歸并最后兩個(gè)子序列Status MergeSort(SqList *L)int len;if(!L-length)printf(The SqList is Empty!);return ERROR;for(len=1;lenlength;len*=2)/有效長度len=n時(shí)終止MSort(L,len);return OK;結(jié)果：1、 樣本數(shù)量為100時(shí)：依次進(jìn)行8種排序的執(zhí)行時(shí)間：2、 樣本數(shù)量為1000時(shí)：