算法分析与设计实验报告-合并排序、快速排序

实验报告课程计算机算法设计与分析实验名称合并排序、快速排序学号姓名实验日期：实验一合并排序、快速排序一．实验目的（1）学习合并排序和快速排序算法的思想，掌握原理。（2）运用合并排序和快速排序算法的思想进行编程实现，以加深理解。二．实验内容（1）输入几个整数，运用合并排序的思想进行编程实现，输出正确的排序结果。（2）输入10个整数，运用快速排序的思想进行编程实现，输出正确的排序结果三．实验代码(1)合并排序源代码如下：#includeiomanip.h//调用setw#includeiostream.h//将b[0]至b[right-left+1]拷贝到a[left]至a[right]templateclassTvoidCopy(Ta[],Tb[],intleft,intright){intsize=right-left+1;for(inti=0;isize;i++){a[left++]=b[i];}}//合并有序数组a[left:i],a[i+1:right]到b,得到新的有序数组btemplateclassTvoidMerge(Ta[],Tb[],intleft,inti,intright){inta1cout=left,//指向第一个数组开头a1end=i,//指向第一个数组结尾a2cout=i+1,//指向第二个数组开头a2end=right,//指向第二个数组结尾bcout=0;//指向b中的元素for(intj=0;jright-left+1;j++)//执行right-left+1次循环{if(a1couta1end){b[bcout++]=a[a2cout++];continue;}//如果第一个数组结束，拷贝第二个数组的元素到bif(a2couta2end){b[bcout++]=a[a1cout++];continue;}//如果第二个数组结束，拷贝第一个数组的元素到bif(a[a1cout]a[a2cout]){b[bcout++]=a[a1cout++];continue;}//如果两个数组都没结束，比较元素大小，把较小的放入belse{b[bcout++]=a[a2cout++];continue;}}}//对数组a[left:right]进行合并排序templateclassTvoidMergeSort(Ta[],intleft,intright){T*b=newint[right-left+1];if(leftright){inti=(left+right)/2;//取中点MergeSort(a,left,i);//左半边进行合并排序MergeSort(a,i+1,right);//右半边进行合并排序Merge(a,b,left,i,right);//左右合并到b中Copy(a,b,left,right);//从b拷贝回来}}intmain(){intn;cout请输入您将要排序的数目:;cinn;int*a=newint[n];cout请输入相应的数字：;for(inti=0;in;i++){cina[i];}MergeSort(a,0,n-1);cout排序结果:;for(intj=0;jn;j++){coutsetw(5)a[j];}coutendl;return1;}（2）快速排序源代码如下：#includeiostream.h#defineMAX10intQuickSort(inta[],intl,intr){intpivot;//枢轴inti=l;intj=r;inttmp;pivot=a[(l+r)/2];//取数组中间的数为枢轴do{while(a[i]pivot)i++;//i右移while(a[j]pivot)j--;//j左移if(i=j){tmp=a[i];a[i]=a[j];a[j]=tmp;//交换a[i]和a[j]i++;j--;}}while(i=j);if(lj)QuickSort(a,l,j);if(ir)QuickSort(a,i,r);return1;}intmain(){intarray[MAX];inti;cout请输入MAX个整数:;for(i=0;iMAX;i++)cinarray[i];QuickSort(array,0,MAX-1);cout快速排序后：endl;for(i=0;iMAX;i++)coutarray[i];coutendl;return0;}四．实验结果五．总结与思考