《五种排序算法的分析与比较》由会员分享，可在线阅读，更多相关《五种排序算法的分析与比较（9页珍藏版）》请在金锄头文库上搜索。
1、五种排序算法的分析与比较广东医学院 医学信息专业 郭慧玲摘要：排序算法是计算机程序设计广泛使用的解决问题的方法,研究排序算法具有重要的理论意义和广泛的应用价值。文章通过描述冒泡、选择、插入、归并和快速 5 种排序算法,总结了它们的时间复杂度、空间复杂度和稳定性。通过实验验证了 5 种排序算法在随机、正序和逆序 3 种情况下的性能,指出排序算法的适用原则,以供在不同条件下选择适合的排序算法借鉴。关键词：冒泡排序;选择排序;插入排序;归并排序 ;快速排序。排序是计算机科学中基本的研究课题之一,其目的是方便记录的查找、插入和删除。 随着 计算机的发展与应用领域的越来越广,基于计算机硬件的速度和存储空
2、间的有限性,如何提高计算机速度并节省存储空间一直成为软件设计人员的努力方向。其中,排序算法已成为程序设计人员考虑的因素之一 1 ，排序算法选择得当与否直接影响程序的执行效率和内外存储空间的占用量,甚至影响整个软件的综合性能。排序操作 2 ， 3 ,就是将一组数据记录的任意序列, 重新排列成一个按关键字有序的序列。而所谓排序的稳定性 4 是指如果在排序的序列中，存在前后相同的两个元素，排序前和排序后他们的相对位置不发生变化。1算法与特性1.1 冒泡排序1.1.1 冒泡排序的基本思想冒泡排序的基本思想是 5,6 :首先将第 1 个记录的关键字和第 2 个记录的关键字进行比较,若为逆序,则将 2 个
3、记录交换,然后比较第 2 个和第 3 个记录的关键字,依次类推,直至-1 个记录和第个记录的关键字进行过比较为止。然后再按照上述过程进行下一次排序,直至整个序列有序为止。1.1.2 冒泡排序的特性容易判断冒泡排序是稳定的。可以分析出它的效率,在最好情况下,只需通过-1 次比较,不需要移动关键字,即时间复杂度为( )(即正序);在最坏情况下是初始序列为逆序,则需要进行-1 次排序,需进行(-1)/2次比较,因此在最坏情况下时间复杂度为( 2 ),附加存储空间为(1)。1.2 选择排序1.2.1 选择排序的基本思想选择排序的基本思想是 5,6 :每一次从待排序的记录中选出关键字最小的记录,顺序放在
4、已排好序的文件的最后,直到全部记录排序完毕.常用的选择排序方法有直接选择排序和堆排序,考虑到简单和易理解,这里讨论直接选择排序。直接选择排序的基本思想是个记录的文件的直接排序可经过-1 次直接 选择排序得到有序结果。1.2.2 选择排序的特性容易得出选择排序是不稳定的。在直接选择排序过程中所需进行记录移动的操作次数最少为 0,最大值为 3(-1)。然而,无论记录的初始排序如何,所需进行的关键字间的比较次数相同,均为(-1)/2,时间复杂度为 (2 ),附加存储空间为 (1)。1.3 插入排序1.3.1 插入排序的基本思想插入排序的基本思想是 5,6 :每次将 1 个待排序的记录按其关键字大小插
5、入到前面已经排好序的子文件中适当的位置,直到全部记录插入完成为止。插入排序分直接插入排序、折半插入排序和希尔排序 3 类。考虑到简单、易理解的因素,这里讨论直接插入排序,其基本思想是:初始时 0自成一个有序区,无序区为 1,-1,从=1 至= -1 为止,依次将插入到当前的有序区中,生成含个 记录 的有序区。容易得出插入排序是稳定的。1.3.2 插入排序的特性当待排序文件为正序时,所需进行的关键字间比较的次数达最小值-1,记录 不需要移 动;反之 ,逆序时比较次数达最大值(+2)(-1)/2,移动次数为( +4)(-1)/2,因此 ,其时间复杂度为( 2 ),附加存储空间为(1)。1.4 归并
6、排序1.4.1 归并排序的基本思想归并排序的基本思想是 7,8 :采用分治策略,将待排序文件分成大小大致相同的 2 个子集合,分别对 2 个子集合进行排序,最终将排好序的子集合并成所要求的排好序的集合。假设初始序列含有个记录,则可以将每个记录看成是长度为 1 的子序列,然后两两归并,得到对/2 个长度为 2 或 1 的有序子序列;再两两归并,如此重复 ,直至得到 1 个长度为的有序序列为止。1.4.2 归并排序的特性容易得出归并排序稳定。归并排序算法对个待排序记录进行排序,在最坏的情况下所需的计算时间( )满足: 1,()=(1); otherwise,()=()。附加存储空间为 ()。1.5
7、 快速排序1.5.1 快速排序的基本思想快速排序的基本思想是 7,9 :具体过程如下,假设当前待排序序列为 low, ,high,排序过程分为分解、求解和合并 3 个步骤:分解，在low, ,high中任选 一个记录作为基准(base),以此基准将当前待排序序列分为左、右 2 个子区间,前者为 low, ,base-1,均小于基准,后者为base+1, ,high,均大于基准,基准则处于正确的位置上;求解，通过递归调用快速排序对左、右 2 个子区间进行快速排序;合并，当求解中的 2 个递归调用结束时,左、右 2 个子区间已有序,即完成排序。 需附加存储空间为(log 2).容易得出快速排序不
8、稳定。1.5.2 快速排序的特性根据对此排序的描述,可以分 2 种情况讨论:1)当待排序序列有序(序列按正序排列) 时,每次划分只得到 1 个比上一次少 1 个记录的子序列。这样,必须经过-1 次才能把所有记录定位,而且第次需要-次比 较才能找到第个记录的正确位置,故总的比较次数达到 1/2*(-1)=(2)。2)当排序序列是随机序列时,且 ()是对个记录的序列进行排序所需的时间,每次对 1 个记录正确定位后,正好把序列划分为长度相等的 2个子序列,此时()满足 1,()=(1); otherwise, ()=()。2性能评价2.1实验与结果为了比较各种排序算法的性能,我们使用一台桌面电脑，在
9、6.0环境下,用语言编写程序 ,调用随机函数、时间 函数来统计输入规模不同和排序不同的元素时五种排序算法的用时情况。以下实验结果引用于10 ：五种排序算法的性能分析由表 1 可知:当输入规模为 10 000 时,5 种排序算法的用时情况差不多,但随着输入规模的增大,快速排序算法的优势就体现出来,其次是归并排序,最差的是选择排序,插入排序略优于冒泡排序。由表 2 可知:当输入序列是正序时,插入排序算法最佳,其次是归并排序,快速排序略优于冒泡排序,最差的是选择排序。由表 3 可知:当输入序列是逆序时,归并排序算法是最理想的,最坏的是选择排序;输入规模在 8 000 个记录范围内时,插入排序和快速排
10、序差不多,随着输入规模的增大, 快速排序比插入排序耗 时更少;输入规模在 4 000 个记录范围内 时,冒泡排序和选择排序几乎一样,差别极其微小,随着规模增大,冒泡排序优于选择排序。2.2算法性能评价评价排序算法好坏的标准主要有 3 条 11 :执行时间、所需的辅助空间以及算法的稳定性。算法本身的复杂程度,即空间复杂度和时间复杂度。如果所需的辅助空间并不依赖于问题的规模,即辅助空间是(1),称之为就地排序;非就地排序一般要求的辅助空 间为()。然而,时间复杂度 12 取决于算法本身涉及的记录之间的比较次数和交换次数。总结排序算法比较（表 4）排序方法 平均时间复杂度 最坏情况 空间复杂度 稳定
11、性冒泡排序 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 种排序,
12、所需时间最省,但在最坏情况下,快速排序则不如归并排序。在输入规模较大时,快速排序比较有优势,但当输入规模不是很大时,5 种排序算法的耗时相差无几。就空间复杂度而言,快速和归并排序的辅助空间开销比较大,冒泡、选择、插入排序辅助空间开销比较少。根据以上实验结果,可得出结论:当记录较小, 基本有序，要求稳定时， 则采用直接插入排序；若记录较小，分布随机，稳定性不做要求时，则采用直接选择排序；若记录较大，内存允许，要求排序稳定时，则采用归并排序。所以在选择合适的排序算法时,应该考虑到算法本身的时间复杂度、空 间复杂度和稳定性等.其具体的用法应根据应用环境而定,侧重点不同,则选择的排序方法也各异。参考文
13、献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.
