实验九 内部排序.doc

实验九 内部排序1、 实验目的1、 深入了解各种排序方法的基本思想、排序过程。2、 熟练掌握各种排序方法的实现和特点，掌握各种排序方法的时间复杂度的分析方法。3、 掌握各种排序方法所适应的不同场合，能加以灵活运用。2、 实验内容和要求2、 典型内部排序算法的比较。（1） 针对“12.11.4参考源程序”，随机产生整数样本，进行8种排序，并比较各种排序算法的执行时间，如执行时间均为0，可考虑增大样本，如加大至5000。（2） 修改“12.11.4参考源程序”，输出8种排序算法的每一趟结果。3、 实验过程及结果（1）源代码：#include stdio.h#include conio.h#include stdlib.h#include time.h#define OK 1#define ERROR 0#define OVERFLOW -1#define MAXSIZE 5000/设待排序记录数不超过5000个typedef int Status;typedef int KeyType;/定义关键字为整型typedef int InfoType;/定义其它数据项类型为整型typedef struct KeyType key;/关键字项InfoType otherinfo;/其他数据项RedType;typedef struct /定义顺序表的结构RedType *r;/存储空间基址，人r0闲置或用作哨兵或用作缓冲区int length;/顺序表长度SqList;Status InitSqList(SqList *L);/构造一个空的顺序表LStatus CreateSqList(SqList *L);/输入数据元素个数，随机产生整数样本Status CopySqList(SqList L_BAK,SqList *L);/Status OutputSqList(SqList L);/输出排序之后的数据int LT(KeyType e1,KeyType e2);/判断数据元素e1是否小余e2void Swap(RedType *e1,RedType *e2);/数据元素e1和e2互换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.rlow.high进行快速排序Status QuickSort(SqList *L);/对L进行快速排序Status SelectSort(SqList *L);/直接选择排序Status HeapAdjust(SqList *H,int S,int m);/调整L.rs的关键字，使L.rs.m成大顶堆Status HeapSort(SqList *L);/堆排序Status Merge(SqList *L,int low,int mid,int high);/将两个有序的子序列L.rlow.mid和L.rmid.high归并成有序的序列L.rlow.highvoid MSort(SqList *L,int len);/对L.r1.n做一趟归并排序Status MergeSort(SqList *L);/对L.r1.n自底向上二路归并排序void main()/典型内部排序的比较SqList L,L_BAK;int select,flag=1,t,dltaMAXSIZE;double duration;clock_t start,finish;/clock_t用于计时InitSqList(&L);InitSqList(&L_BAK);CreateSqList(&L_BAK);t=0;/产生希尔排序的增量序列dlta0.tdlta0=L_BAK.length/2;while(dltat1)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(select)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 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);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;/输出算数时间printf(nThe Sort Spend: %lf secondsn,duration);Status InitSqList(SqList *L)L-r=(RedType *)malloc(MAXSIZE+1)*sizeof(RedType);/分配内存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();/随机产生整数样本printf(nnThe UnSorted data 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 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=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 ShellInsert(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 SqList 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-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;jlength-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 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归并后的结果L1.r=(RedType *)malloc(high-low+1)*sizeof(RedType);/分配内存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;/将归并结果复制回L-rlow.highreturn OK;void MSort(SqList *L,int len)int i;for(i=1;i+2*len-1length;i=i+2*len)/归并长度为len的两个相邻的子序列Merge(L,i,i+len-1,i+2*len-1);if(i+len-1length)/仍有一个子序列，其中后一个长度小于len;此时,若ilength且i+len-1=L-length时，则剩余一个子序列轮空，无须归并Merge(L,i,i+len-1,L-length);/归并最后两个子序列Status MergeSort(SqList *L)int len;if(!L-length)printf(The SqList is Empty!);return ERROR;for(len=1;lenlength;len*=2)/有效长度len=n时终止MSort(L,len);return OK;结果：1、 样本数量为100时：依次进行8种排序的执行时间：2、 样本数量为1000时：