数据结构实验四题目一排序实验报告.docx

《数据结构实验四题目一排序实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构实验四题目一排序实验报告.docx（28页珍藏版）》请在第一文库网上搜索。

1、数据结构实验报告实验名称：实验四排序学生姓名：XX班级：班内序号：学号：日期：1.实验要求实验目的：通过选择实验内容中的两个题目之一，学习、实现、对比、各种排序的算法，掌握各种排序算法的优劣，以及各种算法使用的情况。题目1:使用简单数组实现下面各种排序算法，并进行比较。排序算法如下：1、插入排序；2、希尔排序；3、冒泡排序；5、简单选择排序；6、堆排序；7、归并排序；8、基数排序（选作）；9、其他。具体要求如下：1、测试数据分成三类：正序、逆序、随机数据。2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换记为3次移动卜3、对于这三类数据，比较上述排序算法中不同算法

2、的执行时间，精确到微妙。4、对2和3的结果进行分析，验证上述各种算法的时间复杂度。5、编写main（）函数测试各种排序算法的正确性。2.程序分析2.1 存储结构存储结构：数组OA11A22A33A44A5O匚Ae2.2 关键算法分析一、关键算法：1、插入排序a、取排序的第二个数据与前一个比较b、若比前一个小，则赋值给哨兵c、从后向前比较，将其插入在比其小的元素后d、循环排序2、希尔排序a、将数组分成两份b、将第一份数组的元素与哨兵比较c、若其大与哨兵，其值赋给哨兵d、哨兵与第二份数组元素比较，将较大的值赋给第二份数组e、循环进行数组拆分3、对数据进行编码a、取数组元素与下一个元素比较b、若比下

3、一个元素大，则与其交换c、后移，重复d、改变总元素值，并重复上述代码4、快速排序a、 选取标准值b、 比较高低指针指向元素，若指针保持前后顺序，且后指针元素大于标准值，后指针前移，重新比较c、 否则后面元素赋给前面元素d、 若后指针元素小于标准值，前指针后移，重新比较e、 否则前面元素赋给后面元素5、简单选择排序a、 从数组中选择出最小元素b、 若不为当前元素，则交换c、 后移将当前元素设为下一个元素6、堆排序a、 生成小顶堆b、 将堆的根节点移至数组的最后c、 去掉已做过根节点的元素继续生成小顶堆d、 数组倒置7、归并排序a、 将数组每次以1/2拆分，直到为最小单位b、 小相邻单位数组比较重

4、排合成新的单位c、 循环直至完成排序二、代码详细分析：1、插入排序关键代码： 取排序的第二个数据与前一个比较：if(rivri-1) 若比前一个小，则赋值给哨兵:rO=ri; 从后向前比较，将其插入在比其小的元素后：r0+1=r0；a+;r0+1=rO;循环排序2、希尔排序关键代码：将数组分成两份：d=n2将第一份数组的元素与哨兵比较：for(inti=d+1;i=n;i+)若其大与哨兵，其值赋给哨兵:if(rO0&r0=1;d=d/2)3、冒泡排序关键代码：取数组元素与下一个元素比较：for(inti=1;iri+1)若比下一个元素大，则与其交换:rO=ri;ri=ri+1;ri+1=rO;

5、后移,重复:for(inti=1;ibound;i+)改变总元素值，并重复上述代码：intbound=pos;关键代码:选取标准值:rO=ri比较高低指针指向元素，若指针保持前后顺序，且后指针元素大于标准值，后指针前移,重新比较:whi1e(i=f1ag)j-;否则后面元素赋给前面元素：ri=rj;若后指针元素小于标准值，前指针后移，重新比较:whi1e(ij&ri=f1ag)i+J否则前面元素赋给后面元素：rj=ri;5、简单选择排序关键代码：从数组中选择出最小元素：for(intj=i+1;j=n;j+)if(rUrindex)index=j;若不为当前元素，则交换：if(index!=i

6、)rO=ri;ri=rindex;rindex=r0;后移将当前元素设为下一个元素：fo(inti=1;ivn;i+)6、堆排序关键代码：生成小顶堆:whi1e(j=m)if(jr0+1)j+；if(ri0;i-)coutri7、归并排序关键代码：将数组每次以1/2拆分，直到为最小单位：mid=(1ow+high)2;小相邻单位数组比较重排合成新的单位：whi1e(i=m&j=high)if(1.ri=1.rO)tk+=1.ri+;e1setk+=1.rj+;whi1e(i=m)tk+=1.ri+;whi1e(j=high)tk+=1.rj+;for(i=1ow,k=03=highji+,k+

7、)1.ri=tk;151115265961771948151115192648596177三、计算关键算法的时间、空间复杂度插入排序O(M)希尔排序0(n2)冒泡排序O(M)快速排序O(n1og2n)简单选择排序O(M)堆排序0(n1og2n)归并排序0(n1og2n)3 .程序运行结果1、测试主函数流程：流程图如图所示流程图示意图程序运行结果图如下:图C:Windowssystem32cmd.exe345入将要排序的元素逆序:（乱序）：321125106608，；;0;0;0160312443数数数胁动疆做也晟数动动;动勤的助勤的勤统-3;3;3;4148移另：7101010为为为;0;0;

8、00，为为为数数数719417116数数数次次次为为为为为为为为为次次次数数数数数数数比比比次次次次次次次次次比比比I444Uu1u1ubp1U1U1U1UUU232323454545454545454545232323：1.1：1232323232323232323：1HyvBy身身身I11(口4口吐口一乡-n111身身身吐口在呈口正逆乱正逆乱正逆乱2、测试条件：按题目要求分别输入同组数据的正序、逆序、随机序列进行测试。3、测试结论：不同的排序方法移动次数比较次数和所用时间都是有所区别的。4 .总结调试时出现的问题及解决的方法：在调试时，开始在归并排序的时候，虽然代码编译成功，但调试出现了错

9、误，通过逐步调试发现是由于发生了地址冲突。因此将原本的直接调用数组改成了结构体数组，通过引用来实现归并排序，最终获得了成功心得体会：学习、实现、对比、各种排序的算法，掌握各种排序算法的优劣，以及各种算法使用的情况下一步的改进：改进计数器，寻找其他排序方式。附：源代码#inc1udeusingnamespacestd;intCnum=O;intMnum=O;c1ass1ED(private:intcompare;intmove;pub1ic:void1nsertSort(intr,intn);直接插入排序voidShe111nsert(intr,intn);希尔排序voidBubb1eSort(

10、intr,intn);冒泡排序voidQsort(intr,inti,intj);快速排序voidSe1ectSort(intr,intn);选择排序voidHeapSort(intr,intn);voidMergePass(intr,intr1,intn,inth);intPartion(intr,intfirst,intend);voidSift(intr,intk,intm);voidMerge(intr,intr1,ints1intm,intt);)；插入排序void1ED:1nsertSort(intr,intn)compare=0;move=0;for(inti=2;i=n;i+)

11、(if(r(iri-1)(rO=ri;move+;r=ri-1;move+;intj；for(j=i-2;r0rO；j)(compare+;rj+1=rD;move+;)+compare;rQ+1=rO;move+;+compare;for(inti=1;i=n;i+)coutri=1;d=d/2)(for(inti=d+1;i=n;i+)(if(r0&r0rj;j=j-d)(rd=r;move+;compare+;r0+d=rO;move+;compare+;for(inti=1;i=n;i+)coutri,;COUtVV”比较次数为“compare；移动次数为“vvmovew；”；void1ED:Bubb1eSort(intr,intn)冒泡排序改进(compare=O;move=O;intpos=n;whi1e(pos!=O)(intbound=pos;pos=O;for(inti=1;iri+1)(rO=ri;ri=ri+1;ri+1=rO;交换pos=i;move=move+3;for(inti=1;i=n;i