论排序算法的效率

李明达 何丽丽

[摘 要] 排序算法是计算机设计中常用的解决问题的方法，常见的有冒泡法、选择法、插入法、归并法和快速法等。对于这些排序算法，各自有何种优势和缺陷？又分别适用于什么情况？搞懂这些问题对于我们进行程序设计和优化都具有十分重要的意义。本文主要通过对上述五种排序算法的剖析，分别对其效率进行研究和讨论。

[关键词] 排序算法；程序设计；冒泡法；插入法；快速法

doi ： 10 . 3969 / j . issn . 1673 - 0194 . 2018. 05. 067

[中图分类号] TP301.6 [文献标识码] A [文章编号] 1673 - 0194（2018）05- 0162- 03

0 引 言

在计算机程序设计中，排序算法是一种被广泛用于解决实际问题的重要方法。排序的目的在于帮助程序设计者提高查找、插入和删除的效率，使编程过程变得相对简单化和便捷化。随着当前计算机及网络技术的高度发展，以及计算机程序在各个应用领域的大力推广，基于计算机硬件存储空间和运行速度的局限性，进一步突出了提高计算机运行速度和节省存储空间的重要性，因此它也成为今后软件设计人员共同努力和追求的方向。如何解决上述问题，其视角和思路并不唯一，但目前程序设计人员已将排序算法视为一个重要的因素，因为我们所选择的排序算法将直接影响程序的执行效率和它对计算机硬件存储空间的占用额，不仅决定了整个软件的综合性能，还会影响整个计算机系统的运行效率。

所谓排序算法，即通过特定的算法因式将一组或多组数据按照既定模式进行重新排序，这种新序列遵循着一定的规则，体现出一定的规律，因此，经处理后的数据便于筛选和计算，大大提高了计算效率。对于排序，我们首先要求其具有一定的稳定性，即当两个相同的元素同时出现在某个序列之中，则经过一定的排序算法之后，两者在排序前后的相对位置不发生变化。换言之，即便是两个完全相同的元素，它们在排序过程中也是各有区别的，不允许混淆不清。

1 计算机程序设计中常见的排序算法

目前计算机程序设计中出现的排序算法已不单一，而是呈现出多样化的前景，比如有冒泡排序法、选择排序法、插入排序法、归并排序法和快速排序法等多种形式。

1.1 计算机程序设计中的冒泡排序算法

冒泡排序算法是把较小的元素往前调或者把较大的元素往后调。这种方法主要是通过对相邻两个元素进行大小的比较，根据比较结果和算法规则对该二元素的位置进行交换，这样逐个依次进行比较和交换，就能达到排序目的。冒泡排序的基本思想是，首先将第1个和第2个记录的关键字比较大小，如果是逆序的，就将这两个记录进行交换，再对第2个和第3个记录的关键字进行比较，依次类推，重复进行上述计算，直至完成第（n-1）个和第n个记录的关键字之间的比较；此后，再按照上述过程进行第2次、第3次排序，直至整个序列有序为止。排序过程中要特别注意的是，当相邻两个元素大小一致时，这一步操作就不需要交换位置，因此也说明冒泡排序是一种严格的稳定排序算法，它不改变序列中相同元素之间的相对位置关系。

1.2 计算机程序设计中的选择排序算法

选择排序算法的基本思路是为每一个位置选择当前最小的元素。选择排序的基本思想是，基于直接选择排序和堆排序这两种基本的简单排序方法，首先从第1个位置开始对全部元素进行选择，选出全部元素中最小的给该位置；再对第2个位置进行选择，在剩余元素中选择最小的给该位置即可；以此类推，重复进行“最小元素”的选择，直至完成第（n-1）个位置的元素选择，则第n个位置就只剩唯一的最大元素，此时不需再进行选择。使用这种排序时，要注意其中一个不同于冒泡法的细节，举例说明：序列5 8 5 3 9，我们知道第一遍选择第1个元素“5”会和元素“3”交换，那么原序列中的两个相同元素“5”之间的前后相对顺序就发生了改变。因此，我们说选择排序不是稳定的排序算法，它在计算过程中会破坏稳定性。

1.3 计算机程序设计中的插入排序算法

插入排序算法是基于某序列已经有序排列的情况下，通过一次插入一个元素的方式按照原有排序方式增加元素。这种比较是从该有序序列的最末端開始执行，即要插入序列中的元素最先和有序序列中最大的元素比较，若其大于该最大元素，则可直接插入最大元素的后面即可，否则再向前一位比较查找直至找到应该插入的位置为止。插入排序的基本思想是，每次将1个待排序的记录按其关键字大小插入到前面已经排好序的子序列中，寻找最适当的位置，直至全部记录插入完毕。执行过程中，若遇到和插入元素相等的位置，则将要插入的元素放在该相等元素的后面，因此插入该元素后并未改变原序列的前后顺序，我们认为插入排序也是一种稳定的排序方法。插入排序分直接插入排序、折半插入排序和希尔排序3类。

1.4 计算机程序设计中的归并排序算法

归并排序算法就是把序列递归划分成为一个个短序列，以其中只有1个元素的直接序列或者只有2个元素的序列作为短序列的递归出口，再将全部有序的短序列按照一定的规则进行排序为长序列。归并排序融合了分治策略，即将含有n个记录的初始序列中的每个记录均视为长度为1的子序列，再将这n个子序列两两合并得到n/2 个长度为2（当n为奇数时会出现长度为1的情况）的有序子序列；将上述步骤重复操作，直至得到1个长度为n的有序长序列。需要注意的是，在进行元素比较和交换时，若两个元素大小相等则不必刻意交换位置，因此该算法不会破坏序列的稳定性，即归并排序也是稳定的排序算法。

1.5 计算机程序设计中的快速排序算法

快速排序算法的基本思想是通过分解、求解和合并这3个主要步骤来计算和排序。具体而言，当我们要对一个序列R进行排序时：第一步要先分解，即在R中任选一个记录作为基准，以此基准为界将R一分为二，即左、右两个子区间，前者中的记录均小于基准，后者中的记录均大于基准；第二步要求解，即对这两个区间快速排序；第三步就是合并，对上述两个分别完成排序的子区间进行合并，即完成整体的排序。快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和右侧子区间元素交换的时刻。

2 排序算法的基本特性分析

对于这些常见排序算法的基本思想和步骤，我们已经明确，每种算法所具有的时间、空间复杂性以及稳定性特征，也应是我们研究其算法效率或性能的一个重要基础。

2.1 冒泡排序算法的特性分析

冒泡排序是一种稳定的排序算法。冒泡排序在最佳情况下只需通过1次排序、（n-1）次比较即可实现，此时的时间复杂度为O（n）；相反，当遇到初始序列为逆序的最差情况时，则需要进行（n-1）次排序、（n-1）n/2次比较才能完成，此时的时间复杂度为O（n2）；我们假定附加存储空间为O（1）。

2.2 选择排序算法的特性分析

选择排序是一种不稳定的排序算法。选择排序以直接选择排序法最为典型，选择排序过程中移动记录的操作次数最少可能为0，最大则为3（n-1）次，而关键字之间的比较次数均为（n-1）n/2次，时间复杂度也是O（n2）；附加存储空间也是O（1）。

2.3 插入排序算法的特性分析

插入排序也是一种稳定的排序算法。为了方便理解，我们以直接插入进行探讨：当所研究的序列为正序时，需要最少进行（n-1）次关键字之间的比较，此时不需要对记录进行移动操作，时间复杂度为O（n）；相反，遇到逆序时，则对关键字的比较呈现出最大值（n+2）（n-1）/2次，而对应的记录移动次数为（n+4）（n-1）/2次，其时间复杂度为O（n2），附加存储空间为O（1）。

2.4 归并排序算法的特性分析

归并排序也是一种稳定的排序算法。选用归并排序算法对n个记录进行排序计算，假设其计算时间为T（n），则最佳情况下，T（n）=O（1），且 n≤1；而最差的情况下，T（n）=O（nlogn）；附加存储空间为O（n）。

2.5 快速排序算法的特性分析

快速排序主要分2種情况，一种是待排序序列为有序序列，一种是待排序序列为随机无序序列。当待排序序列有序时，每一次划分将只能得到1个比上一次少1个记录的子序列，因此需要经过（n-1）次才能完成全部计算，其中第m次需要（n-m）次比较才能准确找到第m个记录的位置，此时总的比较次数为1/2n（n-1）=O（n2）。当待排序序列是随机序列时，我们假设对n个记录的序列排序的时间为T（n），则每一次正确定位1个记录后，该序列恰被划分为长度相等的两个子序列，此时T（n）=O（1），且n≤1；相反，则最差的情况下，T（n）=O（n2）；附加存储空间为O（log2n）。

3 排序算法的效率分析

对于各种排序算法的性能或效率的评价，一直以来都是备受关注的一个话题。为了比较上述各种常见排序算法的效率，我们要设定一个相同的运算环境，比如在VS6.0环境下进行C语言编程测试，调用时间函数和随机函数来对输入不同规模和排序元素时，各种排序算法的运行状况。

首先，我们通过改变输入元素的规模，对各种排序算法的时间消耗上进行分析。当输入规模相对较小时，上述算法消耗的时间基本上一致，差距甚小；随着输入规模的逐步增大，其时间差距越来越明显，其中以快速算法最具优势，其次是归并排序，而选择排序耗时最多，因此其时间效率也是最低的。其次，我们通过调整输入顺序来研究各种排序算法的时间消耗。正序时，插入排序算法优势最明显——不消耗时间，而下面则是归并排序法、快速排序法和冒泡排序法，而选择排序耗时最多，因此时间效率最高；逆序时，归并排序法成为最理想的计算方法，下面是快速排序法和插入排序法，而冒泡排序法和选择排序法则相对不具有优势。经过比较我们发现，当规模不断增加时，各种算法之间的差别是很大的。我们对排序算法进行评价的标准主要参照执行时间、辅助空间和算法稳定性这三个方面。对上述几种排序算法的相关参数记录如下。

据此，我们可按照平均时间复杂度把上述五种排序算法分为2类，一类是时间复杂度为O（n2）的冒泡排序、选择排序和插入排序，其时间复杂度均为平方阶排序；一类是时间复杂度为O（nlogn）的归并排序和快速排序，其时间复杂度均为线性对数阶排序。单从平均时间的性能分析，快速排序和归并排序明显优于其他三种排序算法，但是，在最差的情况下，快速排序则不如归并排序；在输入规模较大时，归并排序又不如快速排序；在输入规模较小时，所有算法的效率相差无几。我们再来看空间方面，快速排序和归并排序对空间的占用较大，而前三种则耗用较小的空间。

综上所述，这五种算法中，快速排序比较和移动次数最少，效率最高。选择排序（直接选择排序）虽然交换次数很少，但比较次数较多，因此其效率不如快速排序算法。当序列中的记录较小且基本有序时，如果要求稳定性，则可以采用直接插入的排序算法；当序列中的记录较小且分布随机时，一般不对稳定性做特殊要求，宜采用直接选择排序的算法；当序列中的记录较大且要求排序稳定时，若内存空间允许，一般宜采用归并排序算法。因此，在选择具体排序算法时，必须充分考虑算法本身的时间复杂度、空间复杂度和稳定性等特征。

4 结 语

排序算法目前已经涉及计算机程序设计、操作系统、编译原理、数据库以及人工智能等诸多重要领域，且已经被广泛应用于信息学和系统工程。我们学习和研究排序算法的目的在于为今后更好地用计算机语言来解决和处理实际问题。

主要参考文献

[1]汤亚玲，秦锋.高效快速排序算法研究[J]. 计算机工程，2011，37（6）：77-78.

[2]杨波，肖自碧.信息与计算科学专业“算法分析与设计”研究性教学探索[J].中国电力教育，2013（1）：62-63.

[3]邵顺增.稳定快速排序算法研究[J].计算机应用与软件，2014，31（7）：263-266.