常用排序算法的比较与分析

常用排序算法的比较与分析

摘要：排序是计算机领域的一种重要操作，实现方法有很多种。该文从算法的基本思想、时间复杂度、空间复杂度、稳定性和问题的规模n值大小等方面对常用的排序算法进行了比较分析，为各种实际应用领域选择、设计一个高效且合理实用的算法提供了依据。 关键词：排序算法；时间复杂度；空间复杂度；算法实现 中图分类号：tp312 文献标识码：a 文章编号：1009-3044（2013）09-2146-03

排序是计算机图形学、计算机辅助设计、模式识别、商业事物处理和日常生活等领域的一种重要操作，应用广泛[1]，比如招生切线的分数排序、录取新生的成绩排序等，是计算机科学中的需要解决的重要问题之一。计算机程序中的排序是将一串任意序列的数据按照所要求的既定排序方式确定每个数据的具体位置的算法。在以上领域的数据处理时，程序的排序算法占了很大的比重。因此，排序算法既有广泛的应用价值，又有深刻的理论意义，曾经被列为对科学与工程计算的研究影响最大的十大问题之一[2]，长期以来，人们为了各种领域的应用需要，研究、开发出了多种排序算法，这些算法有着各自的特点，实现方法不尽相同、速度也有差异，而且都在各自的应用领域扮演了重要的角色。

尽管已经开发出了各种不尽相同的排序算法，但是对排序算法的复杂度分析、算法的稳定度和数据结构的研究是解决许多实际应用的基础。该文从排序算法的基本概念、原理出发，分别从算法复杂

度（时间、空间）、算法的稳定性和速度等方面进行分析比较，为具体领域应用的排序选择提供依据，使得执行效率更高。 1 排序的基本概念和算法分析的理论依据 1.1 排序的基本概念

排序：将数据表中没有规律、任意序列的数据元素按照既定的排序依据（关键码）排列成有一定规律的序列。

关键码：规定数据对象的其中一个属性域用作排序依据，从而区分对象，该属性域就是关键码。当数据表中各对象的关键码互不相同时，该关键码为主关键码；否则为次关键码；根据主关键码进行排序时，结果是唯一的，否者可能不唯一。

内部、外部排序：所谓内部排序是指排序时数据元素全部存放在j计算机的随机存储器（内存）；外部排序是指排序时数据元素在内、外存之间不断移动（待排序的数据量很大，内存无法一次容纳全部数据）。

静态排序：所谓静态排序是指对数据元素经过比较和判断之后将对象移动到相应的位置。

动态排序：所谓动态排序是指给每个对象增加一个链接指针，对数据元素经过比较和判断之后不移动对象，而是修改对象的链接指针来达到元素之间顺序的改变。 1.2 算法分析的理论依据

一个问题可以采用不同算法来实现，算法的质量优劣直接影响算法的效率。算法分析的目的在于选择合适的算法和改进算法。评价

一个算法的优劣主要是根据算法的复杂度（分为时间复杂度和空间复杂度），不同的排序算法，其复杂度也不一样，简单的算法程序，其执行效率也低；反之，复杂的算法程序，其执行效率相对来说也会比较高。

如果一个问题的规模是n，解这一问题的某一算法所需要的时间为t（n），它是n的某一函数，t（n）称为这一算法的时间复杂度。当问题规模n趋于无穷大时，如果存在某个辅助函数f（n），t（n）/f（n）的极限值为不等于零的常数，该时间复杂性的极限情形称为算法的渐近时间复杂度[3-4]，记作o（f（n））。一般情况，在算法分析时对两者不予区分，经常是将渐近时间复杂度t（n）=o（f（n））简称为时间复杂度，f（n）是算法中频度最大的语句频度。常见的时间复杂度有：常数阶o（1），对数阶o（log2n），线性阶o（n），线性对数阶o（nlog2n），平方阶o（n2），立方阶o（n3），k次方阶o（nk），指数阶o（2n）。n越大，时间复杂度也越大，算法的执行效率就越低。例如： sum=0； （1次）

for（i=1；i直接插入排序中，关键词相同的数据元素将保持原有位置不变，所以该算法是稳定的，时间复杂度的最坏值为平方阶o（n2），空间复杂度为常数阶o（1）。

该排序方法是对冒泡排序的改进，比冒泡排序大约快3倍，但是只适用于数据量较小（1000）的排序。 2.1.2 希尔排序

基本思想：根据不同步长对数据元素执行插入排序，刚开始数据非常无序时，步长最大，此时插入排序的元素个数很少，速度很快；数据基本有序时，步长很小，插入排序对于有序的序列效率很高。因此，如果元素为你的待排序序列，先取一个小于n的整数i作为步长，将所有元素分为i个子序列，在每个子序列中分别执行直接插入排序。然后缩小步长i重新划分子序列和排序，直到i=1，此时，相当于将所有元素放在一个序列当中。

刚开始，由于步长i很大，所以排序效率很高，当步长i逐渐减小时，序列也趋于有序化，所以排序效率也很高。因此，希尔排序时间复杂度会比o（n2）好一些，然而，多次插入排序中，第一次插入排序是稳定的，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，所以希尔排序是不稳定的。

相对来说，希尔排序比较简单，适用于小数据量（5000以下）的排序，比直接插入排序快2倍、比冒泡排序快5倍，因此，希尔排序适用于小数据量的、排序速度要求不高的排序。 2.2 选择排序

基本思想：每一趟扫描时，从待排序的数据元素中选出关键码最小或最大的一个元素，顺序放在已经排好顺序序列的最后，直到全部待排序的数据元素排完为止。 2.2.1 直接选择排序

基本思想：给每个位置选择关键码最小的数据元素，即：选择最小的元素与第一个位置的元素交换，然后在剩下的元素中再选择最