几种典型内部排序算法性能分析

《几种典型内部排序算法性能分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、几种典型内部排序算法性能分析　　摘要：目前排序算法的应用越来越广泛，其目的是方便记录的查找、插入及删除。本文从算法时间复杂度、空间复杂度及稳定性方面对冒泡排序、选择排序、插入排序以及归并排序进行了分析，并通过对比实验，对比了四种算法在不同数据规模时的对比次数、移动次数、交换次数以及时间，通过分析得出在数据量较大时选择归并排序，数据量较小时可以选择选择排序，数据大部分有序时可以选择插入排序的结论。　　关键词：排序算法；性能；复杂度　　中图分类号：TP311文献标识码：A文章编号：1009-3044（

2、2016）26-0026-04　　1绪论10　　近几年互联网的发展速度越来越快，涉及的领域越来越广，同时对计算机的性能要求也越来越高，基于目前硬件存储性能的限制，科研人员一直致力于计算机性能的优化，在目前的众多方法中，排序算法的优化及选择是研究的重点，排序算法的性能优劣直接影响到程序执行的性能。排序算法目前广泛应用于各个行业领域，例如网站搜索的排序，推荐的先后等等，重要性不言而喻。排序算法是依照一种规则对数据位置进行确定的算法，正是由于排序算法的重要性，人们对排序算法的研究从未停止，先后发明了适合

3、于各种情况的排序算法。本文主要通过对几种典型的排序算法进行算法性能分析，通过算法执行的时间效率、空间效率以及算法稳定性对几种算法进行比较[1]。　　2排序算法　　排序算法数据处理规模的不同导致算法使用处理器的不同，一般将排序算法分为内部排序和外部排序。内部排序是指算法的整个处理过程完全在计算机内存中进行的排序算法，这是基于算法的数据估摸相对比较小，计算机内存能够满足计算机读取存储的需求，本文重点讨论的是内部排序中的冒泡排序、选择排序、插入排序、归并排序四种排序算法。外部排序一般需要处理的数据比较大

4、，计算机内存无法满足待排序对象的一次存储，待排序记录需要在计算机内部存储器以及外部存储器之间进行切换来满足数据量的要求，进而实现对整个文件的排序[2]。　　2.1冒泡排序　　冒泡排序的基本思想是：通过不断比较相邻两个数的大小，并进行相应的调整使得最后所有数据达到有序，之所以称为冒泡排序是由于每一趟排序只比较出一个最大或最小的数出来，类似于冒泡。　　具体排序过程如下：　　1）在进行首次排序过程时将第一个数与第二个数比较，小数在前大数在后，之后是第二个数据和第三个数据按照相同的方式进行比较，同时按照小

5、数在前大数在后的规则进行调整次序，不断进行比较交换调整直至最后两个数比较完毕最大的数据在最后一个，此时第一趟比较结束。　　2）之后进行第二次排序，从第一个数据按照第一趟排序的规则依次比较排序直至倒数第二个数比较完毕，此时第二大的数据在倒数第二的位置。10　　3）之后按照相同的规则进行比较直到最后只剩下一个数据，此时排序完成。　　冒泡排序算法的程序如下所示：　　voidpaixu：：bubblesort（intr[]，longm，longn）　　{for（i=m；i<=n-1；i++）　　{for（

6、j=n；j>=i+1；j--）　　{if（r[j]

7、初始的正好相反所有的记录按照关键字有序的序列的话此时是最坏的情况需进行n-1趟冒泡，比较的次数n（n-1）/2，移动的次数是3n（n-1）/2，时间复杂度O（n2）。冒泡排序的空间复杂度并不随着处理数据量n的大小而改变，为O（1）。　　2.2选择排序10　　选择排序的基本思想是：选择排序的主要排序方式是通过选择进行完成的。在初始待排序的数据中找到最小的数据，并把它和初始数据中第一个位置的数据进行交换，同时在剩余的所有数据中按照相同的方法找到最小的数据与初始数据中第二个位置的数据进行比较，按照这种方

8、式对余下的数据进行排序直到所有的数据排序完成，算法结束。　　具体的排序过程如下所示：　　1）在第一次排序过程中，从所有的m个数sort[0]-sort[m-1]中找到最小的数sort[i]，并将sort[i]于sort[1]进行交换。　　2）在第二次排序过程中，从剩余的sort[1]-sort[m-1]中再次找到最小的数sort[i]，并将sort[i]于sort[2]进行交换。　　3）在第j次排序过程中，从剩余的sort[j-1]-sort[m-1]中再次找到最小的数sort[i