数据结构实验八-排序

实验八排序学生姓名吴肖遥学号20151681310131专业班级电子信息类5班实验地点理工大楼610实验日期2016.6.13指导教师李红蕾实验环境Visualc++6.0实验学时2学时实验类型验证实验成绩一、实验目的1、掌握常用的排序方法，如归并排序、快速排序等。2、深刻理解排序的定义和排序方法的特点，并能加以灵活应用。3、能够分析各种算法的效率和适用条件。二、实验要求1、认真阅读程序。2、上机调试，并运行程序。3、保存和截图程序的运行结果，并结合程序进行分析。三、实验内容和基本原理1、实验8.1归并排序的实现已知关键字序列为{1,8,6,4,10,5,3,2,22}，请对此序列进行归并排序，并输出结果。见参考程序8.1。2、实验8.2快速排序的实现快速排序是通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。见参考程序8.2。参考程序8.1归并排序#includestdio.hintnum=0;voidprint_data(intdata[],intfirst,intlast){inti=0;for(i=0;ifirst;i++)printf(*);for(i=first;i=last;i++)printf(%3d,data[i]);for(i=last;i=8;i++)printf(*);printf(\n);}voidmerge(intarray[],intfirst,intlast)/*一趟归并*/{intmid,i1,i2,i3;inttemp[10];inti,j;mid=(first+last)/2;i1=0;i2=first;i3=mid+1;while(i2=mid&&i3=last){if(array[i2]array[i3])temp[i1++]=array[i2++];elsetemp[i1++]=array[i3++];}if(i2=mid)while(i2=mid)temp[i1++]=array[i2++];if(i3=last)while(i3=last)temp[i1++]=array[i3++];for(i=first,j=0;i=last;i++,j++)array[i]=temp[j];print_data(array,first,last);}voidmergesort(intdata[],intfirst,intlast)/*归并排序*/{intmid;if(firstlast){mid=(first+last)/2;mergesort(data,first,mid);mergesort(data,mid+1,last);print_data(data,first,last);merge(data,first,last);}}voidmain(){inta[]={1,8,6,4,10,5,3,2,22};/*可根据实际情况初始化*/mergesort(a,0,8);}参考程序8.2快速排序#includeiostream.h#includestdio.h#defineMAX8intQuickSort(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;printf(请输入%d个整数:,MAX);for(i=0;iMAX;i++)scanf(%d,&array[i]);QuickSort(array,0,MAX-1);printf(快速排序后:);for(i=0;iMAX;i++)printf(%d,array[i]);printf(\n);return0;}四、实验验证与练习1、设给定的排序码序列为（72，73，71，23，94，16，05，68），请写出归并排序和快速排序过程中每趟排序的结果。归并排序：第一趟：（7273）（2371）（1694）（0568）第二趟：（23717273）（05166894）第三趟：（0516236871727394）快速排序：第一趟：设72为支点（6805712316）72（9473）第二趟：设68为支点（160523）68（71），设94为支点（73）94第三趟：设16为支点（05）16（23）得到有序序列：（0516236871727394）结束2、已知关键字集合（12,2,16,30,8,28,4,10,20,6,18)，用快速排序从小到大排序（选第一个记录为基准进行划分），写出第一趟排序结束时的序列。（621048）12（2830201618）思考题：1、对序列（15，9，7，8，20，-1，4）进行排序，进行一趟排序后，数据的排列变为（4，9，7，8，-1，15，20），则采用的是（B）排序。A.选择排序B.快速排序C.希尔排序D.冒泡排序2、设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最后选用（C）排序法。A.冒泡排序B.快速排序C.堆排序D.直接插入排序五、实验说明：请同学们每次实验记得签到，把每次上机的内容保存好，将所有的实验内容压缩为：学号+班级+姓名+课程名，每次实验后由班长或学习委员统一收取，发送到：[e-mail]邮箱。