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

五种排序算法的分析与比较 广东医学院 医学信息专业 郭慧玲 摘要：排序算法是计算机程序设计广泛使用的解决问题的方法,研究排序算法具有重要的理论意义和广泛的应用价值。文章通过描述冒泡、选择、插入、归并和快速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+