数据结构内排序实验报告

一、实验目的1、了解内排序都是在内存中进行的。2、为了提高数据的查找速度，需要对数据进行排序。3、掌握内排序的方法。二、实验内容1、设计一个程序exp10—1.cpp实现直接插入排序算法，并输出{9,8,7,6,5,4,3,2,1,0}的排序过程。（1）源程序如下所示：//文件名:exp10-1.cpp#includestdio.h#defineMAXE20//线性表中最多元素个数typedefintKeyType;typedefcharInfoType[10];typedefstruct//记录类型{KeyTypekey;//关键字项InfoTypedata;//其他数据项,类型为InfoType}RecType;voidInsertSort(RecTypeR[],intn)//对R[0..n-1]按递增有序进行直接插入排序{inti,j,k;RecTypetemp;for(i=1;in;i++){temp=R[i];j=i-1;//从右向左在有序区R[0..i-1]中找R[i]的插入位置while(j=0&&temp.keyR[j].key){R[j+1]=R[j];//将关键字大于R[i].key的记录后移j--;}R[j+1]=temp;//在j+1处插入R[i]printf(i=%d,,i);//输出每一趟的排序结果printf(插入%d,结果为:,temp);for(k=0;kn;k++)printf(%3d,R[k].key);printf(\n);}}voidmain(){inti,k,n=10;KeyTypea[]={9,8,7,6,5,4,3,2,1,0};RecTypeR[MAXE];for(i=0;in;i++)R[i].key=a[i];printf(初始关键字:);//输出初始关键字序列for(k=0;kn;k++)printf(%3d,R[k].key);printf(\n);InsertSort(R,n);printf(最后结果:);//输出初始关键字序列for(k=0;kn;k++)printf(%3d,R[k].key);printf(\n);}（2）运行的结果如下图所示：2、设计一个程序exp10—2.cpp实现希尔插入排序算法，并输出{9,8,7,6,5,4,3,2,1,0}的排序过程。（1）源程序如下所示：//文件名:exp10-2.cpp#includestdio.h#defineMAXE20//线性表中最多元素个数typedefintKeyType;typedefcharInfoType[10];typedefstruct//记录类型{KeyTypekey;//关键字项InfoTypedata;//其他数据项,类型为InfoType}RecType;voidShellSort(RecTypeR[],intn)//希尔排序算法{inti,j,d,k;RecTypetemp;d=n/2;//d取初值n/2while(d0){for(i=d;in;i++)//将R[d..n-1]分别插入各组当前有序区中{j=i-d;while(j=0&&R[j].keyR[j+d].key){temp=R[j];//R[j]与R[j+d]交换R[j]=R[j+d];R[j+d]=temp;j=j-d;}}printf(d=%d:,d);//输出每一趟的排序结果for(k=0;kn;k++)printf(%3d,R[k].key);printf(\n);d=d/2;//递减增量d}}voidmain(){inti,k,n=10;KeyTypea[]={9,8,7,6,5,4,3,2,1,0};RecTypeR[MAXE];for(i=0;in;i++)R[i].key=a[i];printf(初始关键字:);//输出初始关键字序列for(k=0;kn;k++)printf(%3d,R[k].key);printf(\n);ShellSort(R,n);printf(最后结果:);//输出初始关键字序列for(k=0;kn;k++)printf(%3d,R[k].key);printf(\n\n);}（2）结果如下图所示：3、设计一个程序exp10—3.cpp实现冒泡排序算法，并输出{9,8,7,6,5,4,3,2,1,0}的排序过程。（1）源程序如下所示：//文件名:exp10-3.cpp#includestdio.h#defineMAXE20//线性表中最多元素个数typedefintKeyType;typedefcharInfoType[10];typedefstruct//记录类型{KeyTypekey;//关键字项InfoTypedata;//其他数据项,类型为InfoType}RecType;voidBubbleSort(RecTypeR[],intn)//冒泡排序算法{inti,j,k;RecTypetemp;for(i=0;in-1;i++){for(j=n-1;ji;j--)//比较,找出本趟最小关键字的记录if(R[j].keyR[j-1].key){temp=R[j];//R[j]与R[j-1]进行交换,将最小关键字记录前移R[j]=R[j-1];R[j-1]=temp;}printf(i=%d,冒出的最小关键字:%d,结果为:,i,R[i].key);//输出每一趟的排序结果for(k=0;kn;k++)printf(%2d,R[k].key);printf(\n);}}voidmain(){inti,k,n=10;KeyTypea[]={9,8,7,6,5,4,3,2,1,0};RecTypeR[MAXE];for(i=0;in;i++)R[i].key=a[i];printf(初始关键字:);//输出初始关键字序列for(k=0;kn;k++)printf(%2d,R[k].key);printf(\n);BubbleSort(R,n);printf(最后结果:);//输出初始关键字序列for(k=0;kn;k++)printf(%2d,R[k].key);printf(\n);}（2）结果如下图所示：