实验一 排序算法性能分析

深圳大学实验报告课程名称： 算法设计与分析实验项目名称： 实验一排序算法性能分析学 院： ******专 业： *******************指导教师： ******报告人：学号：班级：实验时间： 2017年10月11日星期三实验报告提交时间： 2017年10月13日星期五教务处制目录一、实验目的 1二、实验概述 1三、实验内容 1四、实验过程 2排序算法的思想与实现版） 2选择排序 2冒泡排序 2合并排序 3快速排序 4插入排序 5测试不同算法的运行时间 6不同算法效率分析 6性能分析 6各种排序理论效率与实测效率分析 7选择排序 7冒泡排序 7合并排序 8快速排序 9插入排序 9五、实验总结与体会 10I第第10页一、实验目的掌握选择排序、冒泡排序、合并排序、快速排序、插入排序算法原理掌握不同排序算法时间效率的经验分析方法，验证理论分析与经验分析的一致性。二、实验概述三、实验内容实现选择排序、冒泡排序、合并排序、快速排序、插入排序算法；nn2020平均运行时间；3. 分别以n=10,n=100,n=1000,n=10000,2的实验；20个随机样本的平均运行时间与输入规模n1示。分析不同算法的实际运行效率的差别。图1.时间效率与输入规模n的关系图四、实验过程排序算法的思想与实现（Java版）选择排序设所排序序列的记录个数为n设所排序序列的记录个数为ni1,2,…,n-1,n-i+1个记录中找出排序码最小的记录，与第i个记录交换。执行n-1趟后就完成了记录序列的排序。代码实现：privatestaticvoidselectSort(int[]arr,intn){/*选择排序：第[1]趟：第1个数依次跟后面n-1个数比较，前者大则交换第[2]趟：第2个数依次跟后面n-2个数比较...*第[n-1]趟：第n-1个数跟最后一个数比较...*/for(inti=0;i<n-1;++i){for(intj=i+1;j<n;++j){if(arr[i]>arr[j]){intt=arr[i];arr[i]=arr[j];arr[j]=t;}}}}冒泡排序基本思想：对相邻的元素进行两两比较，顺序相反则进行交换，这样，每一趟会将最小或最大的元素对相邻的元素进行两两比较，顺序相反则进行交换，这样，每一趟会将最小或最大的元素“浮”到顶端，最终达到完全有序。代码实现：privatestaticvoidbubbleSort(in[]art,inton){/*冒泡排序：第[1]趟：第1个数跟第2个数比较,前者小则交换；第2个数跟第3比较...较...

一趟过后，最大的数排在了最后第[2]趟：第1个数跟第2个数比较...第n-2个数跟第n-1个数比*...*...*第[n-1]趟：第1个数跟第2个数比较*/for(inti=0;i<n-1;++i){for(intj=0;j<n-1-i;++j){if(arr[j]>arr[j+1]){intt=arr[j];arr[j]=arr[j+1];arr[j+1]=t;}}}}合并排序将若干个有序序列进行两两归并，直至所有待排序记录都在一个有序序列为止。基本思想：将若干个有序序列进行两两归并，直至所有待排序记录都在一个有序序列为止。代码实现：//归并排序privatestaticvoidmergeSort(int[]arr,intn){mergeSort(arr,0,n-1);}privatestaticvoidmergeSort(int[]arr,intlow,inthigh){if(low<high){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){ifif(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;k2<temp.length;k2++){arr[k2+low]=temp[k2];}}快速排序基本思想：的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序。代码实现：////快速排序privatestaticvoidquickSort(int[]arr,intlength){quickSort(arr,0,length-1);}privatestaticvoidquickSort(int[]arr,intlow,inthigh){/*快速排序：先把第一个元素放在正确的位置把数组劈成两半左右两边继续同样操作：把第一个元素放在正确的位置继续递归..最终排好序*/intpos;if(low<high){pos=partition(arr,low,high);quickSortquickSort(arr,low,pos-1);quickSort(arr,pos+1,high);}}privatestaticintpartition(int[]arr,intlow,inthigh){intval=arr[low];while(low<high){while(low<high&&arr[high]>=val){--high;}//如果不满足上面的条件了，说明high位置的元素应该在low的位置//因此把arr[high]赋给arr[low]arr[low]=arr[high];while(low<high&&arr[low]<=val){++low;}arr[high]=arr[low];}arr[low]=val;returnlow;}插入排序基本思想：每次将一个待排序的记录按其关键码的大小插入到一个已经排好序的有序序列中，直到全部每次将一个待排序的记录按其关键码的大小插入到一个已经排好序的有序序列中，直到全部记录排好序。代码实现：////插入排序privatestaticvoidinsertSort(int[]arr,intn){/*插入排序：元素拿出来，符合条件的元素后移*/for(inti=1;i<n;++i){intt=arr[i];intk=i;//k为待插入的位置for(intj=i-1;j>=0&&arr[j]>t;--j){arr[j+1]=arr[j];//arr[j]赋给arr[j+1]，即arr[j]向后移k=j;//此时j位置的元素赋给了j+1位置，那么j位置待插入元素，将它赋给入元素，将它赋给k，更新待插入的位置}arr[k]=t;}}测试不同算法的运行时间n10,100,1000,10000,1000005种排序算法的运行时间不同算法效率分析将实际运行时间的所有数据录入到Excel表中，得出如下表格：表1不同排序算法与规模n实际运行时间（毫秒）取对数（10为底）表规模nn=10n=100n=1000n=10000n=100000冒泡排序-3.67654-1.6413040.403977962.51358385.58063877选择排序-3.7167-1.7028960.224403562.20636714.203022快速排序-3.9272-2.609949-1.08354610.10209051.18469143归并排序-3.40561-2.10513-0.92903910.19589971.29280967插入排序-4.04641-2.046409-0.04640941.95359063.95359058以曲线图展示不同排序算法的运行效率。五种排序性能比对五种排序性能比对86420n=10n=100n=1000n=10000n=100000246冒泡排序选择排序快速排序归并排序插入排序图2排序算法实际运行效率（对数）对比图性能分析10w各种排序理论效率与实测效率分析以规模n=10000的实际值为基准，推算出其他规模的值（m，然后进行分析。注：以n=10,100,1000,10000,100000分别进行测试与推算。选择排序实测(/ms)0.0001920.01982实测(/ms)0.0001920.019821.6765160.8315959.6

n=10

n=100

n=1000

n=10000

n=100000理论(/ms)

0.000161

0.016083

1.6083

160.83

16083选择排序选择排序54321012345n=10n=100n=1000n=10000n=100000实测(/ms)理论(/ms)分析：

图3选择排序理论实际运行时间（对数）对比图由于时间复杂度是n2n倍时，相应的在时间的消耗上会扩大n2n2n冒泡排序冒泡排序O(n²)10100100010000100000实测(/ms)0.00021060.022842.535326.275380749理论(/ms)0.0003262750.03262753.26275326.27532627.5冒泡排序冒泡排序86420n=10n=100n=1000n=10000n=100000246实测(/ms)理论(/ms)分析：我们发现，虽然时间复杂度是（n2，但当数据规模扩大n倍时，并没有相应的在时间的消耗上扩大n2倍，而是多于n2n合并排序归并排序

n=10

n=100

n=1000

n=10000

n=100000实测(/ms)实测(/ms)0.00028890.0050450.10551.5719理论(/ms)

0.000393

0.00785

0.11775

1.57

19.625归并排序归并排序210n=10n=100n=1000n=10000n=1000001234实测(/ms)理论(/ms)图8合并排序理论实际对比图分析：该合并排序实际运行效率与理论值可以说完全吻合。快速排序快速排序

n=10

n=100

n=1000

n=10000

n=100000实测(/ms)实测(/ms)0.00011830.0024550.08251.26515.3理论(/ms)

0.0003163

0.006325

0.094875

1.265

15.8125快速排序快速排序210n=10n=100n=1000n=10000n=10000012345实测(/ms)理论(/ms)图9快速排序理论实际对比图分析：10000010实际值与理论值的轻微偏差可能是数据的差异造成的或者电脑等其他因素造成。(5)插入排序插入排序n=10n=100n=1000n=10000n=100000实测(/ms)0.000135450.0109550.94489.8659009.25理论(/ms)