五种排序算法的分析与比较

五种排序算法的分析与比较广东医学院医学信息专业郭慧玲摘要：排序算法是计算机程序设计广泛使用的解决问题的方法,研究排序算法具有重要的理论意义和广泛的应用价值。文章通过描述冒泡、选择、插入、归并和快速5种排序算法,总结了它们的时间复杂度、空间复杂度和稳定性。通过实验验证了5种排序算法在随机、正序和逆序3种情况下的性能,指出排序算法的适用原则,以供在不同条件下选择适合的排序算法借鉴。关键词：冒泡排序;选择排序;插入排序;归并排序;快速排序。排序是计算机科学中基本的研究课题之一,其目的是方便记录的查找、插入和删除。随着计算机的发展与应用领域的越来越广,基于计算机硬件的速度和存储空间的有限性,如何提高计算机速度并节省存储空间一直成为软件设计人员的努力方向。其中,排序算法已成为程序设计人员考虑的因素之一[1]，排序算法选择得当与否直接影响程序的执行效率和内外存储空间的占用量,甚至影响整个软件的综合性能。排序操作[2，3],就是将一组数据记录的任意序列,重新排列成一个按关键字有序的序列。而所谓排序的稳定性[4]是指如果在排序的序列中，存在前后相同的两个元素，排序前和排序后他们的相对位置不发生变化。1算法与特性1.1冒泡排序1.1.1冒泡排序的基本思想冒泡排序的基本思想是[5,6]:首先将第1个记录的关键字和第2个记录的关键字进行比较,若为逆序,则将2个记录交换,然后比较第2个和第3个记录的关键字,依次类推,直至ｎ-1个记录和第ｎ个记录的关键字进行过比较为止。然后再按照上述过程进行下一次排序,直至整个序列有序为止。1.1.2冒泡排序的特性容易判断冒泡排序是稳定的。可以分析出它的效率,在最好情况下,只需通过ｎ-1次比较,不需要移动关键字,即时间复杂度为Ｏ(ｎ)(即正序);在最坏情况下是初始序列为逆序,则需要进行ｎ-1次排序,需进行ｎ(ｎ-1)/2次比较,因此在最坏情况下时间复杂度为Ｏ(ｎ2),附加存储空间为Ｏ(1)。1.2选择排序1.2.1选择排序的基本思想选择排序的基本思想是[5,6]:每一次从待排序的记录中选出关键字最小的记录,顺序放在已排好序的文件的最后,直到全部记录排序完毕.常用的选择排序方法有直接选择排序和堆排序,考虑到简单和易理解,这里讨论直接选择排序。直接选择排序的基本思想是ｎ个记录的文件的直接排序可经过ｎ-1次直接选择排序得到有序结果。1.2.2选择排序的特性容易得出选择排序是不稳定的。在直接选择排序过程中所需进行记录移动的操作次数最少为0,最大值为3(ｎ-1)。然而,无论记录的初始排序如何,所需进行的关键字间的比较次数相同,均为ｎ(ｎ-1)/2,时间复杂度为Ｏ(ｎ2),附加存储空间为Ｏ(1)。1.3插入排序1.3.1插入排序的基本思想插入排序的基本思想是[5,6]:每次将1个待排序的记录按其关键字大小插入到前面已经排好序的子文件中适当的位置,直到全部记录插入完成为止。插入排序分直接插入排序、折半插入排序和希尔排序3类。考虑到简单、易理解的因素,这里讨论直接插入排序,其基本思想是:初始时Ｒ[0]自成一个有序区,无序区为Ｒ[1,…,ｎ-1],从ｉ=1至ｉ=ｎ-1为止,依次将Ｒ[ｉ]插入到当前的有序区中,生成含ｎ个记录的有序区。容易得出插入排序是稳定的。1.3.2插入排序的特性当待排序文件为正序时,所需进行的关键字间比较的次数达最小值ｎ-1,记录不需要移动;反之,逆序时比较次数达最大值(ｎ+2)(ｎ-1)/2,移动次数为(ｎ+4)(ｎ-1)/2,因此,其时间复杂度为Ｏ(ｎ2),附加存储空间为Ｏ(1)。1.4归并排序1.4.1归并排序的基本思想归并排序的基本思想是[7,8]:采用分治策略,将待排序文件分成大小大致相同的2个子集合,分别对2个子集合进行排序,最终将排好序的子集合并成所要求的排好序的集合。假设初始序列含有ｎ个记录,则可以将每个记录看成是长度为1的子序列,然后两两归并,得到对ｎ/2个长度为2或1的有序子序列;再两两归并,如此重复,直至得到1个长度为ｎ的有序序列为止。1.4.2归并排序的特性容易得出归并排序稳定。归并排序算法对ｎ个待排序记录进行排序,在最坏的情况下所需的计算时间Ｔ(ｎ)满足:ｎ≤1,Ｔ(ｎ)=Ｏ(1);otherwise,Ｔ(ｎ)=Ｏ(ｎｌｏｇｎ)。附加存储空间为Ｏ(ｎ)。1.5快速排序1.5.1快速排序的基本思想快速排序的基本思想是[7,9]:具体过程如下,假设当前待排序序列为Ｒ[low,…,high],排序过程分为分解、求解和合并3个步骤:①分解，在Ｒ[low,…,high]中任选一个记录作为基准(base),以此基准将当前待排序序列分为左、右2个子区间,前者为Ｒ[low,…,base-1],均小于基准,后者为Ｒ[base+1,…,high],均大于基准,基准则处于正确的位置上;②求解，通过递归调用快速排序对左、右2个子区间进行快速排序;③合并，当求解中的2个递归调用结束时,左、右2个子区间已有序,即完成排序。需附加存储空间为Ｏ(log2ｎ).容易得出快速排序不稳定。1.5.2快速排序的特性根据对此排序的描述,可以分2种情况讨论:1)当待排序序列有序(序列按正序排列)时,每次划分只得到1个比上一次少1个记录的子序列。这样,必须经过ｎ-1次才能把所有记录定位,而且第ｉ次需要ｎ-ｉ次比较才能找到第ｉ个记录的正确位置,故总的比较次数达到1/2*ｎ(ｎ-1)=Ｏ(ｎ2)。2)当排序序列是随机序列时,且Ｔ(ｎ)是对ｎ个记录的序列进行排序所需的时间,每次对1个记录正确定位后,正好把序列划分为长度相等的2个子序列,此时Ｔ(ｎ)满足ｎ≤1,Ｔ(ｎ)=Ｏ(1);otherwise,Ｔ(ｎ)=Ｏ(ｎｌｏｇｎ)。2性能评价2.1实验与结果为了比较各种排序算法的性能,我们使用一台桌面电脑，在ＶＳ6.0环境下,用Ｃ语言编写程序,调用随机函数、时间函数来统计输入规模不同和排序不同的元素时五种排序算法的用时情况。以下实验结果引用于[10]：五种排序算法的性能分析由表1可知:当输入规模为10000时,5种排序算法的用时情况差不多,但随着输入规模的增大,快速排序算法的优势就体现出来,其次是归并排序,最差的是选择排序,插入排序略优于冒泡排序。由表2可知:当输入序列是正序时,插入排序算法最佳,其次是归并排序,快速排序略优于冒泡排序,最差的是选择排序。由表3可知:当输入序列是逆序时,归并排序算法是最理想的,最坏的是选择排序;输入规模在8000个记录范围内时,插入排序和快速排序差不多,随着输入规模的增大,快速排序比插入排序耗时更少;输入规模在4000个记录范围内时,冒泡排序和选择排序几乎一样,差别极其微小,随着规模增大,冒泡排序优于选择排序。2.2算法性能评价评价排序算法好坏的标准主要有3条[11]:执行时间、所需的辅助空间以及算法的稳定性。算法本身的复杂程度,即空间复杂度和时间复杂度。如果所需的辅助空间并不依赖于问题的规模,即辅助空间是Ｏ(1),称之为就地排序;非就地排序一般要求的辅助空间为Ｏ(ｎ)。然而,时间复杂度[12]取决于算法本身涉及的记录之间的比较次数和交换次数。总结排序算法比较（表4）排序方法平均时间复杂度最坏情况空间复杂度稳定性冒泡排序O(n2)O(n2)O(1)稳定选择排序O(n2)O(n2)O(1)不稳定插入排序O(n2)O(n2)O(1)稳定归并排序O(nlogn)O(nlogn)O(n)稳定快速排序O(nlogn)O(n2)Ｏ(log2ｎ)不稳定综合比较上述讨论的几种内部排序算法,可得到如表4所示的结论。根据表4,可以将5种排序算法按照平均时间分为2类:冒泡排序、选择排序、插入排序其时间复杂度为Ｏ(ｎ2),即平方阶排序;归并排序、快速排序其时间复杂度为Ｏ(ｎlogｎ),即线性对数阶排序。从平均时间性能而言,快速排序和归并排序优越于其他3种排序,所需时间最省,但在最坏情况下,快速排序则不如归并排序。在输入规模较大时,快速排序比较有优势,但当输入规模不是很大时,5种排序算法的耗时相差无几。就空间复杂度而言,快速和归并排序的辅助空间开销比较大,冒泡、选择、插入排序辅助空间开销比较少。根据以上实验结果,可得出结论:当记录较小,基本有序，要求稳定时，则采用直接插入排序；若记录较小，分布随机，稳定性不做要求时，则采用直接选择排序；若记录较大，内存允许，要求排序稳定时，则采用归并排序。所以在选择合适的排序算法时,应该考虑到算法本身的时间复杂度、空间复杂度和稳定性等.其具体的用法应根据应用环境而定,侧重点不同,则选择的排序方法也各异。参考文献[1]王德超.常用排序算法的分析与比较.现代计算机,2012,6(1):36-40.[2]张铭,赵海燕,王腾蛟等.北京大学《数据结构与算法》教学设计[J],计算机教育,2008,11(20):64-68.[3]葛建梅.《数据结构》课程教学方法改革的思考[J]，中国成人教育,2008,9(1)，51-55.[4]范策,周世平,胡哓琨等.数据结构（C语言版）.机械工业出版社，2004，8（4）:81-93.[5]严蔚敏,吴伟民.数据结构[Ｍ].北京清华大学出版社,1997:263-289.[6]曹衍龙,林瑞仲,徐慧.Ｃ语言实例解析[Ｍ].北京人民邮电出版社,2007:94-117.[7]王晓东.计算机算法设计与分析[Ｍ].北京电子工业出版社,2007:21-25.[8]王颖,李肯立,李浪等.纵横多路并行归并算法[Ｊ].计算机研究与发展,2006,43(12):2180-2186.[9]周建钦.超快速排序算法[Ｊ].计算机工程与应用,2006,29(86):41-42.[10]淦艳,杨有.五种排序算法的性能分析.重庆文理学院学报(自然科学版),2010,29(3):45-50.[11]张建伟,张保威,郭云飞.一类分批排序问题的复杂性分析及近似算法[Ｊ].计算机工程与应用,2007,43(3):175-178.[12]刘模群.排序算法时间复杂度研究,软件导刊,2012，11（6）：23-27.