数据结构实验报告：内部排序算法比较

1实验报告课程名称：数据结构实验名称：内部排序算法比较任课教师：专业:计网类班级:2007级1班学号：姓名：___________完成日期：2008年12月30日一、实验目的：掌握主要排序算法的基本思想，包括插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序及基数排序；掌握以上排序算法的实现方法；对各种算法的效率进行比较。二、主要实验内容及要求：（1）使用VC++语言编写程序，分别实现以下算法：插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序及基数排序。（2）编译运行以上算法程序，在运行过程中观察它们的执行过程和结果，给出比较结果。三、程序说明：(算法设计思路)2四、实验结果与结论：（经调试正确的源程序和程序的运行结果）编程员:lghgxu程序源代码：一、插入排序#includestdio.h#includestdlib.h#defineOVERFLOW-2typedefstruct{int*elem;intlength;}SqList;SqListcreate(intn)//建立一个顺序表{SqListL;L.elem=(int*)malloc(n*sizeof(int));if(!L.elem)exit(OVERFLOW);L.length=n;for(intj=1;jn;j++){printf(请输入第%d个整数:\n,j);scanf(%d,&L.elem[j]);}returnL;}voidInsertSort(SqList&L)//对顺序表L作直接插入排序。{inti,j;intcount=0;for(i=2;iL.length;++i)if(L.elem[i]L.elem[i-1])//时，需将L.elem[i]插入有序子表{count++;L.elem[0]=L.elem[i];//复制为哨兵for(j=i-1;L.elem[0]L.elem[j];--j)L.elem[j+1]=L.elem[j];//记录后移L.elem[j+1]=L.elem[0];//插入到正确位置printf(第%d轮排序顺序如下：\n,count);for(intk=1;kL.length;++k)printf(%6d,L.elem[k]);3printf(\n);}}//InsertSortvoidmain(){SqListT;intn=0,flag=0;charyes_no;do{do{printf(请输入顺序表的长度(大于0)(第一个存储单元不存数据)：\n);scanf(%d,&n);}while(n=0);T=create(n);InsertSort(T);printf(数据排序后如下：\n);for(inti=1;iT.length;i++){printf(%5d,T.elem[i]);}printf(\n);do{printf(如果想继续验证请输入Y或y,否则输入N或n：\n\n);scanf(%s,&yes_no);}while(yes_no!='Y'&&yes_no!='y'&&yes_no!='N'&&yes_no!='n');}while(yes_no=='Y'||yes_no=='y');}运行结果：请输入顺序表的长度(大于0)(第一个存储单元不存数据)：8请输入第1个整数:12请输入第2个整数:23请输入第3个整数:34请输入第4个整数:454请输入第5个整数:45请输入第6个整数:56请输入第7个整数:67数据排序后如下：12233445455667如果想继续验证请输入Y或y,否则输入N或n：二、冒泡排序#includestdio.h#includestdlib.h#defineOVERFLOW-2typedefstruct{int*elem;intlength;}SqList;SqListcreate(intn)//建立一个顺序表{SqListL;L.elem=(int*)malloc(n*sizeof(int));if(!L.elem)exit(OVERFLOW);L.length=n;for(intj=0;jn;j++){printf(请输入第%d个整数:\n,j+1);scanf(%d,&L.elem[j]);}returnL;}voidInsertSort(SqList&L)//冒泡排序。{inti,j,temp;for(i=1;iL.length;++i){for(j=i;jL.length;++j){if(L.elem[j]L.elem[j-1]){temp=L.elem[j-1];L.elem[j-1]=L.elem[j];L.elem[j]=temp;5}}printf(第%d轮排序顺序如下：\n,i);for(intk=1;kL.length;++k)printf(%6d,L.elem[k]);printf(\n);}}//InsertSortvoidmain(){SqListT;intn=0,k,flag=0;charyes_no;do{do{printf(请输入顺序表的长度(大于0)：\n);scanf(%d,&n);}while(n=0);T=create(n);InsertSort(T);do{printf(如果想继续验证请输入Y或y,否则输入N或n：\n\n);scanf(%s,&yes_no);}while(yes_no!='Y'&&yes_no!='y'&&yes_no!='N'&&yes_no!='n');}while(yes_no=='Y'||yes_no=='y');}运行结果：请输入顺序表的长度(大于0)(第一个存储单元不存数据)：8请输入第1个整数:12请输入第2个整数:32请输入第3个整数:34请输入第4个整数:46请输入第5个整数:12请输入第6个整数:64请输入第7个整数:56第1轮排序顺序如下：4123234126456第2轮排序顺序如下：4121232346456第3轮排序顺序如下：4121232345664数据排序后如下：4121232345664如果想继续验证请输入Y或y,否则输入N或n：三、快速排序#includestdio.h#includestdlib.h#defineOVERFLOW-2typedefstruct{int*elem;intlength;}SqList;SqListcreate(intn)//建立一个顺序表{SqListL;L.elem=(int*)malloc(n*sizeof(int));if(!L.elem)exit(OVERFLOW);L.length=n;for(intj=1;jn;j++){printf(请输入第%d个整数:\n,j);scanf(%d,&L.elem[j]);}printf(输入的数据如下:\n,j);for(intk=1;kn;k++)printf(%6d,L.elem[k]);printf(\n);returnL;7}intPartition(SqList&L,intlow,inthigh){//交换顺序表L中子序列L.elem[low..high]的记录，使枢轴记录到位，//并返回其所在位置，此时，在它之前（后）的记录均不大（小）于它intpivotkey;L.elem[0]=L.elem[low];//用子表的第一个记录作枢轴记录pivotkey=L.elem[low];//枢轴记录关键字while(lowhigh){//从表的两端交替地向中间扫描while(lowhigh&&L.elem[high]=pivotkey)--high;L.elem[low]=L.elem[high];//将比枢轴记录小的记录移到低端while(lowhigh&&L.elem[low]=pivotkey)++low;L.elem[high]=L.elem[low];//将比枢轴记录大的记录移到高端}L.elem[low]=L.elem[0];//枢轴记录到位returnlow;//返回枢轴位置}//PartitionvoidQSort(SqList&L,intlow,inthigh){//对顺序表L中的子序列L.r[low..high]进行快速排序intpivotloc;if(lowhigh){pivotloc=Partition(L,low,high);//将L.elem[low..high]一分为二QSort(L,low,pivotloc-1);//对低子表递归排序，pivotloc是枢轴位置QSort(L,pivotloc+1,high);//对高子表递归排序}}//QSortSqListQuickSort(SqList&L){QSort(L,1,L.length);returnL;}8voidmain(){SqListT;intn,low,high;charyes_no;do{do{printf(请输入顺序表的长度(大于0)(注:第一个存储单元不存放数据)：\n);scanf(%d,&n);}while(n=0);T=create(n);T=QuickSort(T);printf(排序后数据如下：\n);for(intk=2;k=n;k++)printf(%6d,T.elem[k]);printf(\n);do{printf(如果想继续验证请输入Y或y,否则输入N或n：\n\n);scanf(%s,&yes_no);}while(yes_no!='Y'&&yes_no!='y'&&yes_no!='N'&&yes_no!='n');}while(yes_no=='Y'||yes_no=='y');}运行结果：请输入顺序表的长度(大于0)(注:第一个存储单元不存放数据)：9请输入第1个整数:12请输入第2个整数:43请输入第3个整数:456请输入第4个整数:7请输入第5个整数:4请输入第6个整数:78请输入第7个整数:978请输入第8个整数:45输入的数据如下:124345674787845排序后数据如下：471243457878456如果想继续验证请输入Y或y,否则输入N或n：四、归并排序#includestdio.h#includestdlib.h#defineOVERFLOW-2typedefstruct{int*elem;intlength;}SqList;SqListcreate(intn)//建立一个顺序表{SqListL;L.elem=(int*)malloc(n*sizeof(int));if(!L.elem)exit(OVERFLOW);L.length=n;for(intj=0;jn;j++){printf(请输入第%d个整数:\n,j+1);scanf(%d,&L.elem[j]);}returnL;}voidMerge(SqListL,SqList&T,inti,intm,intn){//将有序的L[i..m]和SR[m+1..n]归并为有序的T[i..n]intj,k;for(j=m+1,k=i;i=m&&j=n;++k){//将L中记录由小到大地并入Tif(L.elem[i]L.elem[j])T.elem[k]=L.elem[i++];elseT.elem[k]=L.elem[j++];}if(i=m)//T[k..n]=L[i..m];将剩余的L[i..m]复制到T10while(k=n&&i=m)T.elem[k++]=L.elem[i++];if(j=n)//将剩余的L[j..n]复制到Twhile(k=n&&j=n)T.elem[k++]=L.elem[j++];}//MergevoidMSort(SqListL,SqList&T,ints,intt){//将L[s..t]归并排序为T[s..t]。intm;SqListw;w.elem=(int*)malloc(20*sizeof(int));if(!w.elem)exit(OVERFLOW);w.lengt