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

摘要：排序是计算机领域的一种重要操作，实现方法有很多种。该文从算法的基本思想、时间复杂度、空间复杂度、稳定性和问题的规模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

for（j=1；j

sum++； （n2次）

在上述交换i和j的算法中，时间复杂度为T（n）=2n2+n+1 =O（n2）。

空间复杂度是指算法在执行过程中，根据n的规模大小需要临时占用的存储空间[3-4]，和时间复杂度类似，也是问题规模n的函数，记作S（n）=O（f（n））。

一般情况，时间复杂度和空间复杂度是相互影响的，即：时间复杂度较好时（效率较高），空间复杂度的可能就变差（占用较多的存储空间），反之也一样。所以设计或选择一个好的算法时要考虑算法的时间复杂度和空间复杂度。

对于排序算法的稳定性，如果待排序的序列中存在两个或两个以上具有相同关键词的数据，排序后这些数据的相对次序保持不变，即它们的位置保持不变，则该算法是稳定的；如果排序后，数据的相对次序发生了变化，则该算法是不稳定的。

不仅仅是时间复杂度和空间复杂度之间相互影响，算法的所有性能之间或多或少都会相互影响。因此，当设计或选择一个算法时，尤其是大型算法，要综合考虑算法的各项性能：复杂度、稳定性、以及算法描述语言的特性，算法运行的机器系统环境等各方面因素。

2 排序算法的分析比较

2.1 插入排序

基本思想：每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数据元素依然有序；直到待排序数据元素全部插入完为止。关键在于将新的数据元素插入到已排序好的序列当中，包括找到应插入的位置、如何移动序列当中的数据元素。因此，插入排序又分为以下两种。

2.1.1 直接插入排序

基本思想：将欲插入的第i个数据元素的关键码与前面已经排序好的i-1、i-2、i-3、…数据元素的关键码进行顺序比较，通过这种线性搜索的方法找到第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 直接选择排序

基本思想：给每个位置选择关键码最小的数据元素，即：选择最小的元素与第一个位置的元素交换，然后在剩下的元素中再选择最小的与第二个位置的元素交换，直到倒数第二个元素和最后一个元素比较为止。

根据其基本思想，每当扫描一趟时，如果当前元素比一个元素小，而且这个小元素又出现在一个和当前元素相等的元素后面，则它们的位置发生了交换，所以直接选择排序时不稳定的，其时间复杂度为平方阶O（n2），空间复杂度为O（1）。

该算法和冒泡排序算法一样，适用于n值较小的场合，而且是排序算法发展的初级阶段，在实际应用中采用的几率较小。

2.2.2 堆排序

堆排序时对直接选择排序的一种有效改进，其基本思想是：将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶的数据元素和序列的最后一个元素交换；接着重建堆、交换数据，依次下去，从而实现对所有的数据元素的排序。完成堆排序需要执行两个动作：建堆和堆的调整，如此反复进行。

由基本思想可知，堆排序有可能会使得两个相同关键码的元素位置发生互换，所以是不稳定的，其平均时间复杂度为O（nlog2n），空间复杂度为O（1）。由于堆的不断建立和调整，所以堆排序不适用于数据元素较少的排序，但是对于n较大的情形，该算法能够表现出较大的优越性。因此，堆排序比较适用于数据量达到百万及其以上的排序，在这种情况下，使用递归设计的快速排序和归并排序可能会发生堆栈溢出的现象。

2.3 交换排序

基本思想：顾名思义，就是一组待排序的数据元素中，按照位置的先后顺序相互比较各自的关键码，如果是逆序，则交换这两个数据元素，直到该序列数据元素有序为止。

2.3.1 冒泡排序

基本思想：对于待排序的一组数据元素，把每个数据元素看作有重量的气泡，按照轻气泡不能在重气泡之下的原则，将未排好顺序的全部元素自上而下的对相邻两个元素依次进行比较和调整，让较重的元素往下沉，较轻的往上冒。

根据基本思想，只有在两个元素的顺序与排序要求相反时才将调换它们的位置，否则保持不变，所以冒泡排序时稳定的。时间复杂度为平方阶O（n2），空间复杂度为O（1）。

冒泡排序时最慢的排序算法，是排序算法发展的初级阶段，实际应用中采用该算法的几率比较小。

2.3.2 快速排序

快速排序是对冒泡排序本质上的改进。其基本思想为：是一个就地排序，分而治之，大规模递归的算法。即：通过一趟扫描后确保基准点的这个数据元素的左边元素都比它小、右边元素都比它大，接着又以递归方法处理左右两边的元素，直到基准点的左右只有一个元素为止。

快速排序时一个不稳定的算法，其最坏值的时间复杂度为平方阶O（n2），空间复杂度为O（log n）。

快速排序是递归的、速度最快的排序算法，但是在内存有限的情况下不是一个好的选择；而且，对于基本有序的数据序列排序，快速排序反而变得比较慢。

2.4 归并排序

归并排序的基本思想是：把数据序列递归地分成短序列，即把1分成2、2分成4、依次分解，当分解到只有1个一组的时候排序这些分组，然后依次合并回原来的序列，不断合并直到原序列全部排好顺序。

合并过程中可以确保两个相等的当前元素中，把处在前面的元素保存在结果序列的前面，因此归并排序是稳定的，其时间复杂度为O（nlog2n），空间复杂度为O（n）。

归并排序比堆排序要快，但是需要的存储空间增加一倍。

2.5 基数排序

基数排序属于分配式排序，其基本思想是：首先是低位排序，然后收集；其次是高位排序，然后再收集；依次类推，直到最高位。

基数排序基于分别排序、分别收集，是稳定的排序算法，其时间复杂度为O（nlog（r）d），r是采取的基数、d是堆数，空间复杂度为O（rd）。

基数排序适用于规模n值很大的场合，但是只适用于整数的排序，如果对浮点数进行基数排序，则必须明确浮点数的存储格式，然后通过某种方式将其映射到整数上，最后再映射回去，过程复杂。

3 排序算法的选择

经过排序算法的分析比较，各种算法有自己比较适合的应用场合，选择算法时应综合考虑稳定性、时间复杂度和空间复杂度等因素。综合前面的分析比较，各种算法的各种因素影响见表1。

表1 排序算法的分析与比较

[排序方法＼&时间复杂度＼&空间

复杂度＼&稳定性＼&规模n＼&平均情况＼&最坏情况＼&插入排序＼&直接插入排序＼&O（n2）＼&O（n2）＼&O（1）＼&是＼&n小＼&希尔排序＼&O（nlog2n）＼&O（nlog2n）＼&O（1）＼&否＼&n小＼&选择排序＼&直接选择排序＼&O（n2）＼&O（n2）＼&O（1）＼&否＼&n小＼&堆排序＼&O（nlog2n）＼&O（nlog2n）＼&O（1）＼&否＼&n大＼&交换排序＼&冒泡排序＼&O（nlog2n）＼&O（n2）＼&O（log n）＼&是＼&n小＼&快速排序＼&O（knlog2n）＼&O（n2）＼&O（log n）＼&否＼&n大＼&归并排序＼&O（nlog2n）＼&O（nlog2n）＼&O（n）＼&是＼&n大＼&基数排序＼&O（nlog（r）d）＼&O（nlog（r）d）＼&O（rd）＼&是＼&n大＼&]

4 结束语

排序算法的应用非常广泛，是计算机图形学、计算机辅助设计、模式识别、商业事物处理和日常生活等领域的一种重要的程序操作。该文从时间复杂度、空间复杂度、稳定性以及规模n值的大小等方面对常用的排序算法进行了分析比较和总结，为排序算法的选择提供了依据。规模n值较小时、且对稳定性不作要求时选用选择排序比较有利，对稳定性有要求时选用插入或冒泡排序比较有利。规模n值较大、且关键码元素随机、对稳定性没要求时选用快速排序比较有利；关键码元素有序、对稳定性有要求时，存储空间又允许的情况下选用归并排序比较有利；关键码元素有序、对稳定性没有要求时选用堆排序比较有利。总而言之，充分了解各种排序算法自身的特点及其基本思想在选择、设计高效且合理的算法具有重要意义。

参考文献：

[1] Cormen T H，Leiserson C E，Rivest R L，et al.Introduction to Algorithms[M].2nd ed.The MIT Press，2001.

[2] Dongarra J.The top 10 algorithms[J].IEEE Computing in Science & Engineering，2000，2（1）： 22-23.

[3] 严蔚敏，吴伟民.数据结构[M].北京：清华大学出版社，2007.

[4] 王晓东，傅清祥，叶东毅.算法与数据结构[M].北京：电子工业出版社，1998.