2023年数据结构实验四题目一排序实验报告

数据构造试验汇报试验名称试验四一一排序学生姓名XX班级班内序号学号日期

1.试验规定试验目U勺通过选择试验内容中日勺两个题目之一，学习、实现、对比、多种排序R勺算法，掌握多种排序算法日勺优劣，以及多种算法使用口勺状况题目1使用简朴数组实现下面多种排序算法，并进行比较

1、排序算法如下

2、插入排序；

3、希尔排序；

4、冒泡排序；

5、迅速排序;测试条件按题目规定分别输入同组数据的正序、逆序、随机序列进行测试测试结论不一样的排序措施移动次数比较次数和所用时间都是有所区别的

4.总结调试时出现的问题及处理的措施在调试时，开始在归并排序的时候，虽然代码编译成功，但调试出现了错误，通过逐渐调试发现是由于发生了地址冲突因此将原本的直接调用数组改成了构造体数组，通过引用来实现归并排序，最终获得了成功心得体会学习、实现、对比、多种排序日勺算法，掌握多种排序算法的优劣，以及多种算法使用的状况下一步的改善改善计数器，寻找其他排序方式附源代码#includeiostreamusing namespacestd;int Cnum=0;int Mnum=0;class LEDprivate:int compare;int move;public:void Shelllnsertint r[],int n;〃希尔排序void BubbleSortinlr[],inl n;〃冒泡排序void Qsorintr[],int i,in[j;〃迅速排序void SelectSortintr[],int n;〃选择排序void HeapSort intr[],int n;void MergePassintr[],int rl[]Jnt n,int h;int Partionint r[],int first,int end;void Siftint4],int k,int in;void Mcrgcint rlJjnt rll],int s,int m,int t;；void LED::InsertSortint r[],int n〃插入排序compare-0;move=0;fbrint i=2;i=n;i++{r

[0]=r[i];move++;rli]=r[i-l]；move++;inlj；forG=i-2;r

[0]rU]:j-{compare++;rU+l]=r|j]；move++;++compare;rU+U=r[O];move++;}++compare;}forint i=l;i=n;i++cout«r[i]«{compare=0;move=0;forint d=n/2;d=l;d=d/2forint i=d+l;i=n;i++ifr[i]r[i-d]move++;r[O]=r[i];intj；forj=i-d;j0r

[0]r[j];j=j-d{r[j+d]=rjl;move++;}compare++;r[j+d]=r[O];compare++;forint i=l;i=n;i++cout«r[il«cout«比较次数为vvcomparevv”;移动次数为move;”；Ivoid LED::BubbleSortint r[],int n〃冒泡排序改善compare=0;move=0;int pos=n;whiiepos!=0{int bound=pos;pos=0;fbrint i=l;i bound;i++r[01=r[i];rni=r[i+ll;r[i+l]=r[O];〃互换pos=i;move=move+3;fbrint i=I;i=n;i++cout«r[i]«coutvv比较次数为“〈〈compare vv”；移动次数为vmoveint LED::Partionintr[l,int first,int endint i=first;〃分区口勺左界int j=end;〃分区日勺右界int pivot=r[i];〃保留第一种元素，作为基准元素whileijwhileijr[j]=pivot//右侧扫描，寻找vpivotW、J元素前移j；Cnum++;r[i]=r[j];whileijr[i]=pivot〃左侧扫描，寻找Apivo出勺元素后移i++；Cnum++;rU]=r[i];}r[i]=pivot;〃将轴值移动到i=jlf9位置return i;〃返回分MI付分界值ivoid LED::Qsortint r[l,int i,int j{Mnum++;int pivotloc=Partionr,i,j;Qsort r,i,pivotloc-1;〃左分区迅速排序Qsort npivotloc+l,j;//右分区迅速排序IelsevoidLED::SelectSortintr[],inln〃简朴选择排序compare-0;move=0;forint i=1;i n;i++〃n-l趟排序int index=i;〃查找最小记录“勺位置indexfbrint j=i+1；j=n;j++ifrj]rlindex]index=j;ifindex!=i〃若第一就是最小元素，则不用互换{rfO]=r[i];r[i]=r[index];r[index]=r

[0];〃运用r

[0],作为临时空间互换记录movc+=3;fbrin i=l;i=n;i++cout«r[i]«couivv比较次数为“〈〈compare vv”;移动次数为〈〈movevv/*void LED::Siftint r[],int k,int minti=k,j=2*i;whilcj=mifjmr[j]r[j+l]j++;ifr[i]=rj]break;else{r

[0]=Hi];r[i]=r[j];r[j]=r

[0]；i=j；j=2*i;}void LED::HeapSortintr[]Jnt nforint i=n/2;i=1;i-//建堆Siftr,i,n;forint i=n;i I;i—〃堆排序〃输出堆顶元素〃重建堆{r[O]=r[l];r[l]=r[i];r[i]=r[O];

6、简朴选择排序；

7、堆排序；

8、归并排序；

9、基数排序（选作）；

10、其他

1、详细规定如下

2、测试数据提成三类正序、逆序、随机数据

3、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字互换记为3次移动）

4、对于这三类数据，比较上述排序算法中不一样算法的执行时间，精确到微妙

5、对2和3的成果进行分析，验证上述多种算法的J时间复杂度

6、编写main（）函数测试多种排序算法打勺对•的J性

2.程序分析

2.1存储构造A1存储构造数组01A22A33A44A55A

[10000];char y;int j=0;cout”请输入元素个数«cndl;cin»j;cout”请输入将要排序H勺元素正序:«endl;fbrin i=l;i=j;i++cin»rl[i];1cout«”请输入将要排序的元素逆序:«endl;forint i=l；i=j；i++cin»r2[i];coutvv”请输入将要排序的元素乱序endl;fbrint i=l;i=j;i++{cin»r3[i];Icout«endl;LED1;COUIVV直接插入排序正序输出成果J.InsertSorUR.j;cout«endl;forint i=l;i=j;i++{R[i]=r2[i];cout直接插入排序逆序输出成果;l.InsertSortR,j;cout«cndl;fbrint i=l;i=j;i++{R[i]=r3[i];}coutvv”直接插入排序乱序输出成果”;l.InsertSortRJ;cout«endl;forint i=l;i=j;i++cout希尔排序正序输出成果U.ShclHnserKRJ;cout«endl;fbrin i=l;i=j;i++R[i]=r2[i];1cout«”希尔排序逆序输出成果:M;l.ShellInsertR,j;cout«endl;fbrint i=i;i=j;i++R[i]=r3liJ;coutw”希尔排序乱序输出成果;I.ShelIInserR,j;cout«endl;forint i=l;i=j;i++{R[i]=rl[i];1cout«”冒泡排序正序输出成果;I.BubbleSonRj;cout«cndl;R[i]=r2[i];cout«,,冒泡排序逆序输出成果;l.BubbleSortR,j;cout«endl;forint i=l;i=j;i++{RliJ=r3[iJ；cout冒泡排序乱序输出成果;LBubhleSortR.j;cout«endl;fbrint i=l;i=j;i++{R[i]=rl[i]；Icoutvv迅速排序正序输出成果:;l.QsortR,l J;forint k=l;k=j;k++cout«R[k]«cout”比较次数为“Cnum；移动次数为MnumCnum=O；Mnum=0;cout«endl;forint i=l;i=j;i++R[i]=r2[i];Icoutvv”迅速排序逆序输出成果;l.QsortRJ,j;forint k=l;k=j;k++cout«Rlk]«cout比较次数为Cnum;移动次数为MnumCnum=;Mnum=0;cout«endl;fbrint i=l;i=j;i++{R[i]=r3[i]；Icoutvv”迅速排序乱序输出成果;l.QsortR,lj;forint k=l;k=j;k++cout«R[k]«cout”比较次数为“Cnum；移动次数为Mnumcout«cndl;forint i=I;i=j;i++R[i]=rl[i];Icoutvv简朴选择排序正序输出成果;l.SelectSortR,j;cout«endl;forint i=l;i=j;i++{R[i]=r2[i];coulv简朴选择排序逆序输出成果;LSelectSortR,j;cout«endl;forint i=l;i=j;i++{R[i]=r3[i]；}coutvv简朴选择排序乱序输出成果:l.SelectSortR.j;cout«endl;

2.2关键算法分析

一、关键算法a、

1.插入排序b、取排序H勺第二个数据与前一种比较c、若比前一种叼、，则赋值给哨兵d、从后向前比较，将其插入在比其小H勺元素后e、循环排序a、

2.希尔排序b、将数组提成两份c、将第一份数组的元素与哨兵比较d、若其大与哨兵，其值赋给哨兵e、哨兵与第二份数组元素比较，将较大日勺值赋给第二份数组f、循环进行数组拆分a、

3.对数据进行编码b、取数组元素与下一种元素比较c、若比下一种元素大，则与其互换d、后移，反复变化总元素值，并反复上述代码a、

4.迅速排序b、选用原则值C、比较高下指针指向元素，若指针保持前后次序，且后指针元素不小于原则值,后指针前移，重新比较d、否则背面元素赋给前面元素e、若后指针元素不不小于原则值，前指针后移，重新比较f、否则前面元素赋给背面元素a、

5.简朴选择排序b、从数组中选择出最小元素c、若不为目前元素，则互换d、后移将目前元素设为下一种元素a、

6.堆排序b、生成小顶堆c、将堆口勺根节点移至数组日勺最终d、去掉己做过根节点日勺元素继续生成小顶堆e、数组倒置

7、归并排序a、将数组每次以1/2拆分，直到为最小单位b、小相邻单位数组比较重排合成新的单位c、循环直至完毕排序

二、代码详细分析

1.插入排序

①关键代码

②取排序的第二个数据与前一种比较:若比前一种小,则赋值给哨兵:r[O]=r[i];从后向前比较，将其插入在比其小的元素后forj=i-l;r

[0]r[j]；j-{rU+l]=rU]；a++；r[j+l]=r[O]；

③循环排序

2.希尔排序

①关键代码

②将数组提成两份:d=n/2

③将第一份数组日勺元素与哨兵比较:forint i=d+l;i=n:i++

④若其大与哨兵,其值赋给哨兵:ifr[O]r[i-d]{r[O]=r[i];}

⑤哨兵与第二份数组元素比较，将较大日勺值赋给第二份数组forG=i-d;j0rlO]r[j]；j=j-d{r[j+d]=r|j];}循环进行数组拆分:forint;d=l;d=d/

23.冒泡排序

①关键代码

②取数组元素与下一种元素比较:forint i=l;ibound;i++ifr[i]r[i+l]

③若比下一种元素大,则与其互换r[O]=r[i];r[i]=r[i+l];r[i+l]=r[O];后移，反复forint i=l;ibound;i++变化总元素值，并反复上述代码intbound=pos;

4.迅速排序

①关键代码

②选用原则值:r⑼=r[i]

③比较高下指针指向元素，若指针保持前后次序，且后指针元素不小于原则值，后指针前移，重新比较:whileijr[j]=flag{j-;l

④否则背面元素赋给前面元素:r[i]=r[j];

⑤若后指针元素不不小于原则值，前指针后移，重新比较whileijr[i]=flagH++；}否则前面元素赋给背面元素:r[j]=rli]；

5.简朴选择排序

①关键代码

②从数组中选择出最小元素forint j=i+1;j=n;j++

③{ifr[j]rindcx]index=j;}

④若不为目前元素，则互换:ifindex!=i{r[O]=r[i];r[i]=r[index];r[index]=r[O];}后移将目前元素设为下一种元素forinti=l;in;i++

6.堆排序

①关键代码

②生成小顶堆whilej=m{ifjmr[j]r[j+1]{j++;}

④else{int x;x=r[i];r[i]=r[j];r[j]=x;i=j;j=2*i;}}

⑤将堆日勺根节点移至数组日勺最终x=r[lj;r[l]=r[n-i+l]；r[n-i+l]=x;

⑥去掉已做过根节点的元素继续生成小顶堆:siflrj,n-i,x,y;

⑦数组倒置输出forim i=n;iX;i-cout«r[i]«M®©®®©*w

77、归并排序

①关键代码mid=low+high/2;

②将数组每次以1/2拆分，直到为最小单位whilei=mj=high小相邻单位数组比较重排合成新勺单位ifL.r[i]=L.r|j]t[k++]=L.r[i++]；else tlk++]=L.r[j++];whilci=ni tlk++j=L.r[i++J;whilej=high t[k++j=L.r|j++|;fori=low,k=0;i=high;i++,k++L.r[i]=t[kJ;回回回■回口回回叵］三X265948267759482659774815192648596177

三、计算关键算法H勺时间、空间复杂度插入排序0希尔排序置泡排序0n2迅速排序0nlog2n简朴选择排序O n2堆排序0nlog2n归并排序O nlog2n

1、