大数据结构预算法之排序算法比较.doc

数据结构与算法课程综合训练实验报告第1次姓名魏豪班级软件62学号2161601038电话**********Email1061431874@日期2017-10-18一、实验题目任务1完成直接插入排序、简单选择排序、冒泡排序、快速排序和归并排序的实现;要求:不能使用你所使用的编程语言内置的排序算法;排序算法的实现只能使用最基本的交换、比较、循环等操作;每个排序算法都尽可能使用课堂上所讲授的步骤,不要对任何排序算法进行额外的优化。任务2完成对每一个排序算法在输入规模为:100、200、300、……、10000的排序时间统计。要求:在同等规模的数据量下,需要统计正序序列和逆序序列两种序列的排序时间;将所有记录的排序时间按照如下分类方式进行图示化,需要完成如下的7张图:图1-图5:每一个图对应一个排序算法,相应的图中记录该排序算法对正序序列和逆序数据序列的时间(x轴代表数据规模、y轴代表运行时间,以下同);图6:用来将5个排序算法在正序数据序列下的运行时间图示化;图7:用来将5个排序算法在逆序数据序列下的运行时间图示化;在每张图的下面用简短的语句描述时间变化趋势的原因。任务3完成对每一个排序算法在输入规模为:100、200、300、……、10000的随机数据序列的排序时间统计。要求:切记,每个排序算法在同样数据规模的随机序列要保持一致;记录5个排序算法在相同规模下的排序时间,并形成图8;图8:用来将5个排序算法在随机数据序列下的运行时间图示化;二、实验内容任务一:直接插入排序:publicstaticvoidsort(int[]array){ for(inti=1;i<;i++) for(intj=i;(j>0)&&(array[j]<array[j-1]);j--){ inttemp=array[j]; array[j]=array[j-1]; array[j-1]=temp; } }简单选择排序:publicstaticvoidsimpleSelectMethod(int[]array){//lowIndex用于记录i+-1这个区间的最小值的下标(i会递增),i表示要交换的位置。for(inti=0;i<-1;i++){ intlowIndex=i; for(intj=i+1;j<;j++) if(array[j]<array[lowIndex]) lowIndex=j; if(lowIndex!=i){ inttemp=array[lowIndex]; array[lowIndex]=array[i]; array[i]=temp; }}}冒泡排序:publicstaticvoidBubbleSort(int[]array){ for(inti=0;i<;i++) for(intj=-1;j>i;j--){ if(array[j]<array[j-1]){ swap(array,j,j-1); } } } publicstaticvoidswap(int[]array,inta,intb){ inttemp=array[b]; array[b]=array[a]; array[a]=temp; }快速排序: publicstaticvoidqsort(int[]array,inti,intj){ intpivotindex=(i+j)/2; //pickapivot swap(array,pivotindex,j); //putpivotatend intk=partition(array,i-1,j,array[j]); swap(array,k,j); if((k-i)>1)qsort(array,i,k-1); if((j-k)>1)qsort(array,k+1,j); } publicstaticvoidswap(int[]array,inta,intb){ inttemp=array[a]; array[a]=array[b]; array[b]=temp; } publicstaticintpartition(int[]array,intl,intr,intpivot){ do{ while(array[++l]<pivot); while((r!=0)&&array[--r]>pivot); swap(array,l,r); }while(l<r); swap(array,l,r); returnl; }归并排序:publicstaticvoidmergeSort(int[]a,intleft,intright){ if(left<right){ intcenter=