《几种排序算法的平均性能比较(实验报告)》由会员分享，可在线阅读，更多相关《几种排序算法的平均性能比较(实验报告)（6页珍藏版）》请在装配图网上搜索。
1、验证型实验实验课程：算法分析与设计实验名称：几种排序算法的平均性能比较实验目标：1几种排序算法在平均情况下哪一个更快。2加深对时间复杂度概念的理解。实验任务：1实现几种排序算法selectionsort,insertionsort,bottomupsort,quicksort,堆排序。对于快速分类,SPLIT中的划分元素采用三者A,A,A/2中其值居中者。2随机产生20组数据比如n=5000i,1i20o数据均属于围0,105的整数。对于同一组数据，运行以上几种排序算法，并记录各自的运行时间以毫秒为单位。3根据实验数据及其结果来比较这几种分类算法的平均时间和比较次数，并得出结论。实验设备及环境
2、：PC;C/C+等编程语言。实验主要步骤：(1)明确实验目标和具体任务；(2)理解实验所涉及的几个分类算法；(3)编写程序实现上述分类算法；(4)设计实验数据并运行程序、记录运行的结果；(5)根据实验数据及其结果得出结论；(6)实验后的心得体会。问题分析包括问题描述、建模、算法的基本思想及程序实现的技巧等：选择排序：令A1-n为待排序数组，利用归纳法，假设我们知道如何对后n-1个元素排序，即对口阿An排序。对某个j,1=j=n,设Aj是最小值。首先，如果就!=1,我们交换A1和Aj。然后由假设，已知如何对A2.n排序，因此可对在A2n中的元素递归地排序。可把递归改为迭代。算法程序实现如下：vo
3、idSelectionSortinti,j,k;intaa;c=0;fori=0;ik=i;forj=i+1;jc+;ifArrayjk=j;ifaa=Arrayi;Arrayi=Arrayk;Arrayk=aa;插入排序：将n个元素的数列分为已有序和无序两个部分,每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较,找出插入位置,将该元素插入到有序数列的合适位置中。算法程序实现如下：voidInsertionSortinti,j;intaa;c=0;fori=0;iaa=Arrayi;j=i-1;while=0&Arrayjaac+;Arrayj+1=Arrayj;j=j-
4、1;Arrayj+1=aa;自底向上合并排序：利用分治法思想,将两个或两个以上有序表合并成一个新的有序表即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。将已有序的子序列合并,得到完全有序的序列；即先使每个子序列有序,再使子序列段间有序。算法程序实现如下：voidMergeint*B=newintr-p+1;ints=p;intt=q+1;intk=0;whiles=q&tC+；ifAs(Bk=As;s=s+1;)else(Bk=At;t=t+1;)k=k+1;)if(whilet(Bk=At;k=k+1;t=t+1;)else(whiles(Bk=As
5、;k=k+1;s=s+1;)k=0;whilep(Ap=Bk;k+;p+;)deleteB;)voidBottomupSort(ints,i,t=1;c=0;whilet(s=t;t=2*s;i=0;whilei+t(Merge;i=i+t;ifi+sMerge;快速排序：设要排序的数组是A0AN-1,首先任意选取一个数据通常选用第一个数据作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。快速排序就是递归调用此过程。算法程序实现如下：voidSplit(intaa,x;intj,i=low;intmid=/2;ifAlow(ifAmidw=l
6、ow;elseifAmidw=mid;elsew=high;else(ifAmidw=high;elseifAmidw=mid;elsew=low;c+;x=Aw;aa=Alow;Alow=Aw;Aw=aa;forj=low+1;j(c+;ifAji=i+1;ifaa=Ai;Ai=Aj;Aj=aa;aa=Alow;Alow=Ai;Ai=aa;w=i;voidQuickintw;iflowSplit;Quick;Quick;voidQuickSortc=0;Quick;堆排序：堆排序利用了大根堆堆顶记录的关键字最大这一特征,使得在当前无序区中选取最大关键字的记录变得简单。先将初始文件R1.n建成
7、一个大根堆,此堆为初始的无序区,再将关键字最大的记录R1和无序区的最后一个记录Rn交换,由此得到新的无序区R1.n-1和有序区Rn,且满足R1.n-1.keyswRn.key,由于交换后新的根R1可能违反堆性质，故应将当前无序区R1.n-1调整为堆。然后再次将R1.n-1中关键字最大的记录R1和该区间的最后一个记录Rn-1交换,由此得到新的无序区R1.n-2和有序区Rn-1.n,且仍满足关系R1.n-2.keysRn-1.n.keys,同样要将R1.n-2调整为堆。直到无序区只有一个元素为止。voidSiftdownbooldone=false;intj,a;ifnreturn;while2*
8、i+1j=i；i=2*i+1;c=c+2;ifi+1Hii=i+1;ifHja=Hi;Hi=Hj;Hj=a;elsedone=true;voidMakeHeap4nt*A,intn,int&cinti;fori=/2;i=0;i-Siftdown;voidHeapSortc=0;MakeHeap;intj;intx;for=1;j-x=A0;A0=Aj；Aj=x；Siftdown;实验数据及其结果可用图表形式给出：输入规模nselectioninsertionbottomupquickHeap5000运行时间毫秒7878000数组元素比较次数12497500620019856813631831
9、0774410000运行时间毫秒3122811600数组元素比较次数499950002520847512365813811123542420000运行时间毫秒1263112316016数组兀素比较次数1999900009975063926747630292351081230000运行时间毫秒28702527161615数组兀素比较次数44998500022497904141026846028980036640000运行时间毫秒52104509471516数组兀素比较次数799980000402537541574791663812110117250000运行时间毫秒81747004471631数
10、组兀素比较次数12499750006260688747333908663511409734实验结果分析及结论:选择排序算法最稳定，算法的效率只跟输入规模有关，与元素序列无关，但也是效率最差。插入排序的效率跟元素的序列有关，最好情况已排序时间复杂度为0,最坏情况逆序时间复杂度为。.自底向上合并排序、快速排序、堆排序的效率差不多，最坏情况和最好情况时间复杂度都为o,对于绝大部分元素有序的数组，这三种排序算法的效率不如插入排序。实验自我评价及心得体会：通过这次实验，我对这五种排序的原理和执行过程有了更清楚地了解，由于本次实验是在VC+2008平台下利用MFC实现，在学习算法的过程中同时也让我更加熟悉了windows的界面编程方法。主要参考文献：算法设计技巧与分析沙特M.H.Alsuwaiyel著
几种排序算法的平均性能比较(实验报告)
