几种典型内部排序算法性能探析.doc

几种典型内部排序算法性能分析 　　摘要：目前排序算法的应用越来越广泛，其目的是方便记录的查找、插入及删除。本文从算法时间复杂度、空间复杂度及稳定性方面对冒泡排序、选择排序、插入排序以及归并排序进行了分析，并通过对比实验，对比了四种算法在不同数据规模时的对比次数、移动次数、交换次数以及时间，通过分析得出在数据量较大时选择归并排序，数据量较小时可以选择选择排序，数据大部分有序时可以选择插入排序的结论 关键词：排序算法；性能；复杂度 中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）26-0026-04 1绪论 近几年互联网的发展速度越来越快，涉及的领域越来越广，同时对计算机的性能要求也越来越高，基于目前硬件存储性能的限制，科研人员一直致力于计算机性能的优化，在目前的众多方法中，排序算法的优化及选择是研究的重点，排序算法的性能优劣直接影响到程序执行的性能。排序算法目前广泛应用于各个行业领域，例如网站有哪些信誉好的足球投注网站的排序，推荐的先后等等，重要性不言而喻。排序算法是依照一种规则对数据位置进行确定的算法，正是由于排序算法的重要性，人们对排序算法的研究从未停止，先后发明了适合于各种情况的排序算法。本文主要通过对几种典型的排序算法进行算法性能分析，通过算法执行的时间效率、空间效率以及算法稳定性对几种算法进行比较[1] 2排序算法 排序算法数据处理规模的不同导致算法使用处理器的不同，一般将排序算法分为内部排序和外部排序。内部排序是指算法的整个处理过程完全在计算机内存中进行的排序算法，这是基于算法的数据估摸相对比较小，计算机内存能够满足计算机读取存储的需求，本文重点讨论的是内部排序中的冒泡排序、选择排序、插入排序、归并排序四种排序算法。外部排序一般需要处理的数据比较大，计算机内存无法满足待排序对象的一次存储，待排序记录需要在计算机内部存储器以及外部存储器之间进行切换来满足数据量的要求，进而实现对整个文件的排序[2] 2.1冒泡排序 冒泡排序的基本思想是：通过不断比较相邻两个数的大小，并进行相应的调整使得最后所有数据达到有序，之所以称为冒泡排序是由于每一趟排序只比较出一个最大或最小的数出来，类似于冒泡 具体排序过程如下： 1）在进行首次排序过程时将第一个数与第二个数比较，小数在前大数在后，之后是第二个数据和第三个数据按照相同的方式进行比较，同时按照小数在前大数在后的规则进行调整次序，不断进行比较交换调整直至最后两个数比较完毕最大的数据在最后一个，此时第一趟比较结束 2）之后进行第二次排序，从第一个数据按照第一趟排序的规则依次比较排序直至倒数第二个数比较完毕，此时第二大的数据在倒数第二的位置 3）之后按照相同的规则进行比较直到最后只剩下一个数据，此时排序完成 冒泡排序算法的程序如下所示： void paixu：：bubblesort（int r[]，long m，long n） {for（i=m；i=i+1；j--） {if（r[j] 　　r[k]=temp；}} 通过选择排序的代码可以看出，选择排序的执行过程是两个for循环的查找过程，第一个过程是查找最小元素，第二个过程是m次循环过程，所以时间复杂度是O（n2），所需进行的关键字间的比较次数是n（n-1）/2，移动记录的次数，最小值为0，最大值为3（n-1） 。选择排序的空间复杂度并不随着处理数据量n的大小而改变，为O（1） 2.3插入排序 这里以希尔插入排序为例，希尔插入排序是对线性插入排序的一种改进，又称为缩小增量排序。希尔排序的基本思想是：对于一个记录数是m的待排序数据，首先选择一个增量dis10） {for（i=gap+1；im-1） { if（r[j]r[j+gap]） //交换r[j]和r[j+gap] {temp=r[j]； r[j]=r[j+gap]； r[j+gap]=temp； j=j-gap；} else j=m-1； //通过给j赋值而退出while循环}} gap=gap/2； //减小增量 }} 希尔排序是直接插入排序的改进，在性能上要优于直接插入排序。在希尔排序算法中如果初始的数据所有的记录按照关键字有序的序列的话此时是最好的情况，移动的次数为0，比较的次数在n～ n2之间；如果初始的数据所有的记录按照关键字逆序的序列的话此时是最坏的情况，移动次数和比较次数接近n2，但是在平均情况下希尔排序的比较次数和移动次数好于直接插入排序，为O（n1.3）左右。选择排序的空间复杂度并不随着处理数据量n的大小而改变，为O（1） 2.4归并排序 归并排序采用的是分治思想，是将两个或多个有序序列合并