实验一 排序算法性能分析

深圳大学实验报告课程名称：算法设计与分析实验项目名称：实验一排序算法性能分析学院：******专业：*******************指导教师：******报告人：学号：班级：实验时间：2017年10月11日星期三实验报告提交时间：2017年10月13日星期五教务处制I目录一、实验目的.................................................................................................................................1二、实验概述.................................................................................................................................1三、实验内容.................................................................................................................................1四、实验过程.................................................................................................................................21.排序算法的思想与实现（Java版）..................................................................................2(1)选择排序....................................................................................................................2(2)冒泡排序....................................................................................................................2(3)合并排序....................................................................................................................3(4)快速排序....................................................................................................................4(5)插入排序....................................................................................................................52.测试不同算法的运行时间..................................................................................................6(1)不同算法效率分析....................................................................................................6(2)性能分析....................................................................................................................63.各种排序理论效率与实测效率分析..................................................................................7(1)选择排序....................................................................................................................7(2)冒泡排序....................................................................................................................7(3)合并排序....................................................................................................................8(4)快速排序....................................................................................................................9(5)插入排序....................................................................................................................9五、实验总结与体会...................................................................................................................10第1页一、实验目的1.掌握选择排序、冒泡排序、合并排序、快速排序、插入排序算法原理2.掌握不同排序算法时间效率的经验分析方法，验证理论分析与经验分析的一致性。二、实验概述排序问题要求我们按照升序排列给定列表中的数据项，目前为止，已有多种排序算法提出。本实验要求掌握选择排序、冒泡排序、合并排序、快速排序、插入排序算法原理，并进行代码实现。通过对大量样本的测试结果，统计不同排序算法的时间效率与输入规模的关系，通过经验分析方法，展示不同排序算法的时间复杂度，并与理论分析的基本运算次数做比较，验证理论分析结论的正确性。三、实验内容1.实现选择排序、冒泡排序、合并排序、快速排序、插入排序算法；2.以待排序数组的大小n为输入规模，固定n，随机产生20组测试样本，统计不同排序算法在20个样本上的平均运行时间；3.分别以n=10,n=100,n=1000,n=10000,n=100000，重复2的实验；4.画出不同排序算法在20个随机样本的平均运行时间与输入规模n的关系，如下图1所示。分析不同算法的实际运行效率的差别。图1.时间效率与输入规模n的关系图5.画出理论效率分析的曲线和实测的效率曲线，注意：由于实测效率是运行时间，而理论效率是基本操作的执行次数，两者需要进行对应关系调整。调整思路：以输入规模为10000的数据运行时间为基准点，计算输入规模为其他值的理论运行时间，画出不同规模数据的理论运行时间曲线，并与实测的效率曲线进行比较。经验分析与理论分析是否一致？如果不一致，请解释存在的原因。第2页四、实验过程1.排序算法的思想与实现（Java版）(1)选择排序基本思想：设所排序序列的记录个数为n。i取1,2,…,n-1,从所有n-i+1个记录（Ri,Ri+1,…,Rn）中找出排序码最小的记录，与第i个记录交换。执行n-1趟后就完成了记录序列的排序。代码实现：privatestaticvoidselectSort(int[]arr,intn){/**选择排序：*第[1]趟：第1个数依次跟后面n-1个数比较，前者大则交换*第[2]趟：第2个数依次跟后面n-2个数比较...*....*第[n-1]趟：第n-1个数跟最后一个数比较...*/for(inti=0;in-1;++i){for(intj=i+1;jn;++j){if(arr[i]arr[j]){intt=arr[i];arr[i]=arr[j];arr[j]=t;}}}}(2)冒泡排序基本思想：对相邻的元素进行两两比较，顺序相反则进行交换，这样，每一趟会将最小或最大的元素“浮”到顶端，最终达到完全有序。代码实现：privatestaticvoidbubbleSort(in[]art,inton){/**冒泡排序：*第[1]趟：第1个数跟第2个数比较,前者小则交换；第2个数跟第3比较...*一趟过后，最大的数排在了最后*第[2]趟：第1个数跟第2个数比较...第n-2个数跟第n-1个数比较...第3页*...*第[n-1]趟：第1个数跟第2个数比较*/for(inti=0;in-1;++i){for(intj=0;jn-1-i;++j){if(arr[j]arr[j+1]){intt=arr[j];arr[j]=arr[j+1];arr[j+1]=t;}}}}(3)合并排序基本思想：将若干个有序序列进行两两归并，直至所有待排序记录都在一个有序序列为止。代码实现：//归并排序privatestaticvoidmergeSort(int[]arr,intn){mergeSort(arr,0,n-1);}privatestaticvoidmergeSort(int[]arr,intlow,inthigh){if(lowhigh){intmid=(low+high)/2;//左边mergeSort(arr,low,mid);//右边mergeSort(arr,mid+1,high);//左右归并merge(arr,low,mid,high);}}privatestaticvoidmerge(int[]arr,intlow,intmid,inthigh){int[]temp=newint[high-low+1];inti=low;//左指针intj=mid+1;//右指针intk=0;//把较小的数先移到新数组中while(i=mid&&j=high){第4页if(arr[i]arr[j]){temp[k++]=arr[i++];}else{temp[k++]=arr[j++];}}//把左边剩余的数移入数组while(i=mid){temp[k++]=arr[i++];}//把右边边剩余的数移入数组while(j=high){temp[k++]=arr[j++];}//把新数组中的数覆盖arr数组for(intk2=0;k2temp.length;k2++){arr[k2+low]=temp[k2];}}(4)快速排序基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序。代码实现：//快速排序privatestaticvoidquickSort(int[]arr,intlength){quickSort(arr,0,length-1);}privatestaticvoidquickSort(int[]arr,intlow,inthigh){/**快速排序：*先把第一个元素放在正确的位置*把数组劈成两半*左右两边继续同样操作：*把第一个元素放在正确的位置*继续递归..最终排好序*/intpos;if(lowhigh){pos=partition(arr,low,