2023年数据结构排序实验报告

《数据结构》课程设计报告实验五排序一、需求分析:本演示程序用C++6.0编写，完毕各种排序的实现，对输入的一组数字实现不同的排序方法，对其由小到大顺序输出。(1)分别对直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序算法进行编写。(2)、对存储的函数即输入的数字进行遍历。(3)、初始化函数对输入的数字进行保存。(4)、主函数实现使用者操作界面的编写，对输入、选择、保存、输出的各种实现。这当中还涉及了各个函数的调用的实现。上：\最后的浜程没计\口0协9\^序©、6-李乔李乔J^速择顿选直希同展选生欢请1234567李乔李乔J^速择顿选直希同展选生欢请1234567请输入你需要的操作:0:0:■丫:\最后的深星设计■丫:\最后的深星设计\Debug0E序exe・456:::谢作作作7谢口架桑桑的如46然的阳46殂46的阳熬76弗要序3序8!要序3序6!要序3序8!选程需字2字5续需字2字7续需录2录5^^翁76数46继沿76数58继你记76记46继操用入一刖8后3键入一刖8后6键入一刖8后3键入使普5序5序4=0^1^5序2二篇迎靠t12排t12任靠bL2排123隹靠BL2排bL2任请欢（3）各种排序的结果:凌卷入隹需要的操作：1堤岸前数字序列:1258762346排序后数字序列：1223465876任意键继续!请输入你需要的操作：2排序刖数子序列：1258762346排序后数字序列：1223465876任总键继续！凌趣入徐霞整的操作:排序刖数子序列：1258762346排序后数字序列：5876762346键继续I六、设计局限性以及存在问题本程序是基于C++6.0的实现,其实在设计上的改善可以运用类进行操作,这种类的改善了存储上的局限性还可以实现了，对各种的函数基于类的实现，这就是对本程序的改善,这是十分重要的与是改善的基础。本程序出现过的问题是主函数对个函数的调用以及对存储数组的调用上出现了问题，导致排序的结果以及排序的界面出现了问题,的不到实现。后来对算法进行改善，最终把问题得以解决。(5)、程序所能达成的功能：完毕对输入的数字的生成，并通过对各排序的选择实现数字从小到大的输出。二、程序重要功能以及基本规定:(1)、设计一个菜单，格式如下：1、直接插入排序2、希尔排序3、冒泡排序4、快速排序5、选择排序6、堆排序7、退出(2)、选择不同的菜单但进行相应的排序，并给出排序的关键字序列。三、系统框架图：本程序包含了9个函数，它们分别是：(1)、直接插入排序的算法函数InsertSort。。(2)、希尔排序的算法函数ShellS。rt()o主函数主函数各对输操作个入的界面排数组的设序进行计,函算遍历数的加拓调田一主函数(3)、冒泡排序算法函数BubbleSort()。主函数(4)、快速排序的算法函数Partition()。(5)、选择排序算法函数SelectSort。。(6)、堆，序算法函数HeapAdjust()。(7)、对存储数字的遍历函数Visit()o(8)、初始化函数InitSqListOo(9)、主函数main()o四、具体设计实现各个算法的重要内容，下面是各个函数的重要信息：(1)各个排序函数的算法：一、直接插入排序voidInsertSort(SqList&L)(“nti,j;for(i=2；i<=L.length;i++){■if(L.r[i].key<L.r[i-1].key)00{。®L.r[0]=L.rfi];»0L.r[i]=L.r[i-1];dfor(j=i-2;(L.r[0].key<L.r[j].key)；j--)。。L.r[j+lJ=L.r[j]；aL.r[j+1]=L.r[0];do}))二、希尔排序voidShellSort(SqList&L)(inti,j;intdk=1;//增量while(dk<=L.1ength/3)。dk=3*dk+1;〃增大增量while(dk>0)(Mk/=3;〃减小增量ftf0r(i=dk;i<=L.length;i++)。(。«L.r[O].key=L.r[i].key;9=dwhi1e((j>=dk)&&(L.r[j-dk].key>L.r[0].key))(gdL.r[j].key=L.r[j-dk].key;j-=dk;)do»L.r[j].key=L.r[OJ.key;°}。})三、冒泡排序voidBubbleSort(SqList&L)(ainti,j;for(i=0;i<L.length-2;i++)(»intflag=1;for(j=O;j<L.Iength-i-2;j++)if(L.r[j].key>L.r[j+l].key)aoftf1ag=0;g»inttemp；，temp=L.r[j].key；gL.r[jj.key=L.rLj+l].key;»L.r[j+1].key=temp;do)。。〃若无互换说明已有序gif(flag==1)®oobreak；•})四、快速排序intPartition(SqList&L,intlow,inthigh){〃分割区域函数L.r[0]=L.r[low]；intpivotkey=L.r[low].key；〃一般将顺序表第一个元素作为支点while(1ow<high)»while(low<high&&L,r[high],key>=pivotkey)ghigh-»L.r[low]=L.r[high]；whi1e(1ow<high&&L,r[lowl，key<=pivotkey)g1ow++;L.r[high]=L.r[low];0}L.r[lowJ=L.r[OJ；〃返回枢轴位置returnlow;)voidQSort(SqList&L,intlow,inthigh)(〃每张子表的快速排序dif(low<high)(dintpivot1oc=Partition(L>low,high);ooQSort(L,low,pivotloc-1);®QSort(L,pivotloc+1,high);))voidQuickSort(SqList&L)(®QSort(L,l,L.1ength);)五、简朴选择排序voidSelectSort(SqList&L){intmin;intj；®for(inti=0;i<L.length；i++){//选择第i小的记录，并互换L.rfil.key；4min=for(intk=i;k<L.length;k++)L.rfil.key；{//在R[i..n・l]中选择最小的记录，if(L.r[kJ.key<min)。dmin=L.r[k].key;°叼=k;，}。}“f(i!=j)。{//与第i个记录互换«inttemp=L.r[il.key;L.r[iJ.key=L.r[j].key;®®®L.r[j].key=temp;•)0})六、堆排序voidHeapAdjust(HeapTypes,intm)(。〃堆调整,将记录调整为小顶堆intj;dRedTyperc=H.r[s1；〃暂时存储根结点3for(j=2*s;j<=m;j*=2)。〃沿着结点记录较小的向下筛选>if(j<m&&H.r[j].key<H.r[j+l].key)°0°++j；gif(rc.key>=H.r[jl.key)gobreak；H.r[s]=H.r[j]；s=j;)dH.r(s]=rc;}voidHeapSort(HeapType&H)(inti;edTypetemp;for(i=H.length;i>0；--i)HeapAdjust(H,i,H.Iength);for(i=H.length;i>l;-i)otemp=H.r[1];®H.r[1]=H.r[i]；»H.r[i]=temp;®HeapAdjust(H,1,i-1);))(2)遍历函数与初始化voidVisit(SqListL)for(inti=l;i<=L.length;i++)cout«L.r[il.ke