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

北京邮电大学信息与通信工程学院第1页数据结构实验报告实验名称：实验四——排序学生姓名：XX班级：班内序号：学号：日期：1．实验要求实验目的：通过选择实验内容中的两个题目之一，学习、实现、对比、各种排序的算法，掌握各种排序算法的优劣，以及各种算法使用的情况。题目1：使用简单数组实现下面各种排序算法，并进行比较。排序算法如下：1、插入排序；2、希尔排序；3、冒泡排序；4、快速排序；5、简单选择排序；6、堆排序；7、归并排序；8、基数排序（选作）；9、其他。具体要求如下：1、测试数据分成三类：正序、逆序、随机数据。2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换记为3次移动）。3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微妙。4、对2和3的结果进行分析，验证上述各种算法的时间复杂度。5、编写main（）函数测试各种排序算法的正确性。2.程序分析2.1存储结构北京邮电大学信息与通信工程学院第2页存储结构：数组0A11A22A33A44A55A6…………NAn-12.2关键算法分析一、关键算法：1、插入排序a、取排序的第二个数据与前一个比较b、若比前一个小，则赋值给哨兵c、从后向前比较，将其插入在比其小的元素后d、循环排序2、希尔排序a、将数组分成两份b、将第一份数组的元素与哨兵比较c、若其大与哨兵，其值赋给哨兵d、哨兵与第二份数组元素比较，将较大的值赋给第二份数组e、循环进行数组拆分3、对数据进行编码a、取数组元素与下一个元素比较b、若比下一个元素大，则与其交换c、后移，重复d、改变总元素值，并重复上述代码4、快速排序a、选取标准值b、比较高低指针指向元素，若指针保持前后顺序，且后指针元素大于标准值，后指针前移，重新比较c、否则后面元素赋给前面元素d、若后指针元素小于标准值，前指针后移，重新比较e、否则前面元素赋给后面元素5、简单选择排序a、从数组中选择出最小元素b、若不为当前元素，则交换c、后移将当前元素设为下一个元素6、堆排序a、生成小顶堆b、将堆的根节点移至数组的最后c、去掉已做过根节点的元素继续生成小顶堆北京邮电大学信息与通信工程学院第3页d、数组倒置7、归并排序a、将数组每次以1/2拆分，直到为最小单位b、小相邻单位数组比较重排合成新的单位c、循环直至完成排序二、代码详细分析：1、插入排序关键代码：①取排序的第二个数据与前一个比较：if(r[i]r[i-1])②若比前一个小，则赋值给哨兵：r[0]=r[i];③从后向前比较，将其插入在比其小的元素后：for(j=i-1;r[0]r[j];j--){r[j+1]=r[j];a++;}r[j+1]=r[0];④循环排序2、希尔排序关键代码：①将数组分成两份：d=n/2②将第一份数组的元素与哨兵比较：for(inti=d+1;i=n;i++)③若其大与哨兵，其值赋给哨兵：if(r[0]r[i-d]){r[0]=r[i];}④哨兵与第二份数组元素比较，将较大的值赋给第二份数组：for(j=i-d;j0&&r[0]r[j];j=j-d){r[j+d]=r[j];}⑤循环进行数组拆分：for(int;d=1;d=d/2)3、冒泡排序关键代码：①取数组元素与下一个元素比较：for(inti=1;ibound;i++)if(r[i]r[i+1])②若比下一个元素大，则与其交换：r[0]=r[i];r[i]=r[i+1];r[i+1]=r[0];③后移，重复：for(inti=1;ibound;i++)④改变总元素值，并重复上述代码：intbound=pos;4、快速排序关键代码：①选取标准值：r[0]=r[i]②比较高低指针指向元素，若指针保持前后顺序，且后指针元素大于标准值，后指针前移，重新比较：while(ij&&r[j]=flag){j--;}③否则后面元素赋给前面元素：r[i]=r[j];④若后指针元素小于标准值，前指针后移，重新比较：while(ij&&r[i]=flag){i++;}⑤否则前面元素赋给后面元素：r[j]=r[i];5、简单选择排序关键代码：①从数组中选择出最小元素：for(intj=i+1;j=n;j++)②{if(r[j]r[index])index=j;}北京邮电大学信息与通信工程学院第4页③若不为当前元素，则交换：if(index!=i){r[0]=r[i];r[i]=r[index];r[index]=r[0];}④后移将当前元素设为下一个元素：for(inti=1;in;i++)6、堆排序关键代码：①生成小顶堆：while(j=m){if(jm&&r[j]r[j+1]){j++;}②if(r[i]r[j]){break;}③else{intx;x=r[i];r[i]=r[j];r[j]=x;i=j;j=2*i;}}④将堆的根节点移至数组的最后：x=r[1];r[1]=r[n-i+1];r[n-i+1]=x;⑤去掉已做过根节点的元素继续生成小顶堆：sift(r,1,n-i,x,y);⑥数组倒置输出:for(inti=n;i0;i--)coutr[i];7、归并排序关键代码：①将数组每次以1/2拆分，直到为最小单位：mid=(low+high)/2;②小相邻单位数组比较重排合成新的单位：while(i=m&&j=high)if(L.r[i]=L.r[j])t[k++]=L.r[i++];elset[k++]=L.r[j++];while(i=m)t[k++]=L.r[i++];while(j=high)t[k++]=L.r[j++];for(i=low,k=0;i=high;i++,k++)L.r[i]=t[k];北京邮电大学信息与通信工程学院第5页三、计算关键算法的时间、空间复杂度插入排序O（n2）希尔排序O（n2）冒泡排序O（n2）快速排序O（nlog2n）简单选择排序O（n2）堆排序O（nlog2n）归并排序O（nlog2n）3.程序运行结果1、测试主函数流程：流程图如图所示北京邮电大学信息与通信工程学院第6页流程图示意图程序运行结果图如下：北京邮电大学信息与通信工程学院第7页2、测试条件：按题目要求分别输入同组数据的正序、逆序、随机序列进行测试。3、测试结论：不同的排序方法移动次数比较次数和所用时间都是有所区别的。4.总结调试时出现的问题及解决的方法：在调试时，开始在归并排序的时候，虽然代码编译成功，但调试出现了错误，通过逐步调试发现是由于发生了地址冲突。因此将原本的直接调用数组改成了结构体数组，通过引用来实现归并排序，最终获得了成功心得体会：学习、实现、对比、各种排序的算法，掌握各种排序算法的优劣，以及各种算法使用的情况下一步的改进：改进计数器，寻找其他排序方式。附：源代码#includeiostreamusingnamespacestd;intCnum=0;intMnum=0;classLED{private:intcompare;intmove;public:voidInsertSort(intr[],intn);//直接插入排序voidShellInsert(intr[],intn);//希尔排序voidBubbleSort(intr[],intn);//冒泡排序voidQsort(intr[],inti,intj);//快速排序voidSelectSort(intr[],intn);//选择排序voidHeapSort(intr[],intn);voidMergePass(intr[],intr1[],intn,inth);intPartion(intr[],intfirst,intend);voidSift(intr[],intk,intm);voidMerge(intr[],intr1[],ints,intm,intt);};voidLED::InsertSort(intr[],intn)//插入排序{compare=0;move=0;for(inti=2;i=n;i++){if(r[i]r[i-1]){r[0]=r[i];move++;r[i]=r[i-1];move++;intj;北京邮电大学信息与通信工程学院第8页for(j=i-2;r[0]r[j];j--){compare++;r[j+1]=r[j];move++;}++compare;r[j+1]=r[0];move++;}++compare;}for(inti=1;i=n;i++)coutr[i];cout比较次数为compare;移动次数为move;;}voidLED::ShellInsert(intr[],intn)//希尔排序{compare=0;move=0;for(intd=n/2;d=1;d=d/2){for(inti=d+1;i=n;i++){if(r[i]r[i-d]){move++;r[0]=r[i];intj;for(j=i-d;j0&&r[0]r[j];j=j-d){r[j+d]=r[j];move++;}compare++;r[j+d]=r[0];move++;}compare++;}}for(inti=1;i=n;i++)coutr[i];cout比较次数为compare;移动次数为move;;}北京邮电大学信息与通信工程学院第9页voidLED::BubbleSort(intr[],intn)//冒泡排序改进{compare=0;move=0;intpos=n;while(pos!=0){intbound=pos;pos=0;for(inti=1;ibound;i++){compare++;if(r[i]r[i+1]){r[0]=r[i];r[i]=r[i+1];r[i+1]=r[0];//交换pos=i;move=move+3;}}}for(inti=1;i=n;i++)coutr[i];cout比较次数为compare;移动次数为move;;}intLED::Partion(intr[],intfirst,intend){inti=first;//分区的左界intj=end;//分区的右界intpivot=r[i];//保存第一个元素，作为基准元素while(ij){while((ij)&&(r[j]=pivot))//右侧扫描，寻找pivot的元素前移{j--;Cnum++;}r[i]=r[j];while((ij)&&(r[i]=pivot))//左侧扫描，寻找pivot的元素后移{i++;Cnum++;北京邮电大学信息与通信工程学院第10页}r[j]=r[i];}r[i]=pivot;//将轴值移动到i=j的位置returni;//返回分区的分界值i}voidLED::Qsort(intr[],inti,intj){if(ij){Mnum++;intpivotloc=Partion(r,i,j);Qsort(r,i,pivotloc-1);//左分区快速排序Qsort(r,pivotloc+1,j);//右分区快速排序}else{}}voidLED::SelectSort(intr[],intn)//简单选择排序{compare=0;move=0;for(inti=1;in;i++)//n-1趟排序{intindex=i;//查找最小记录的位置indexfor(intj=i+1;j=n;j++){compare++;if(r[j]r[index])index=j;}if(index!=i)//若第一就是最小元素，则不用交换{r[0]=r[i];r[i]=r[index];r[index]=r[0];//利用r[0]，作为临时空间交换记录move+=3;}}for(inti=1;i=n;i++)coutr[i];北京邮电大学信息与通信工程学院第11页cout比