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

《数据结构预算法之排序算法比较》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构与算法课程综合训练实验报告第1次姓名魏豪班级软件62学号2161601038电话18291505923Email1061431874@qq.com日期2017-10-18一、实验题目任务1完成直接插入排序、简单选择排序、冒泡排序、快速排序和归并排序的实现；要求：不能使用你所使用的编程语言内置的排序算法；排序算法的实现只能使用最基本的交换、比较、循环等操作；每个排序算法都尽可能使用课堂上所讲授的步骤，不要对任何排序算法进行额外的优化。任务2完成对每一个排序算法在输入规模为：100、200、300、……、10000的排序时

2、间统计。要求：在同等规模的数据量下，需要统计正序序列和逆序序列两种序列的排序时间；将所有记录的排序时间按照如下分类方式进行图示化，需要完成如下的7张图：图1-图5：每一个图对应一个排序算法，相应的图中记录该排序算法对正序序列和逆序数据序列的时间（x轴代表数据规模、y轴代表运行时间，以下同）；图6：用来将5个排序算法在正序数据序列下的运行时间图示化；图7：用来将5个排序算法在逆序数据序列下的运行时间图示化；在每张图的下面用简短的语句描述时间变化趋势的原因。任务3完成对每一个排序算法在输入规模为：100、200、300、……、10

3、000的随机数据序列的排序时间统计。要求：切记，每个排序算法在同样数据规模的随机序列要保持一致；记录5个排序算法在相同规模下的排序时间，并形成图8；图8：用来将5个排序算法在随机数据序列下的运行时间图示化；二、实验内容任务一：a)直接插入排序：publicstaticvoidsort(int[]array){for(inti=1;i0)&&(array[j]

4、;array[j-1]=temp;}}b)简单选择排序：publicstaticvoidsimpleSelectMethod(int[]array){//lowIndex用于记录i+1到args.length-1这个区间的最小值的下标（i会递增），i表示要交换的位置。for(inti=0;i

5、){inttemp=array[lowIndex];array[lowIndex]=array[i];array[i]=temp;}}}a)冒泡排序：publicstaticvoidBubbleSort(int[]array){for(inti=0;ii;j--){if(array[j]

6、nttemp=array[b];array[b]=array[a];array[a]=temp;}b)快速排序：publicstaticvoidqsort(int[]array,inti,intj){intpivotindex=(i+j)/2;//pickapivotswap(array,pivotindex,j);//putpivotatendintk=partition(array,i-1,j,array[j]);swap(array,k,j);if((k-i)>1)qsort(array,i,k-1);if((j-k)>

7、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);swap(array,l,r);}while(l

8、ay,l,r);returnl;}a)归并排序：publicstaticvoidmergeSort(int[]a,intleft,intright){if(left