`

稳定排序和不稳定排序(转载)

阅读更多
本文是针对老是记不住这个或者想真正明白到底为什么是稳定或者不稳定的人准备的。

      首先,排序算法的稳定性大家应该都知道,通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下,如果Ai = Aj,Ai原来在位置前,排序后Ai还是要在Aj位置前。

      其次,说一下稳定性的好处。排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。基数排序就是这样,先按低位排序,逐次按高位排序,低位相同的元素其顺序再高位也相同时是不会改变的。另外,如果排序算法稳定,对基于比较的排序算法而言,元素交换的次数可能会少一些(个人感觉,没有证实)。

回到主题,现在分析一下常见的排序算法的稳定性,每个都给出简单的理由。

(1)冒泡排序

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,我想你是不会再无聊地把他们俩交换一下的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。

(2)选择排序

选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里面给第二个元素选择第二小的,依次类推,直到第n - 1个元素,第n个元素不用选择了,因为只剩下它一个最大的元素了。那么,在一趟选择,如果当前元素比一个元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了。比较拗口,举个例子,序列5 8 5 2 9,我们知道第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法。

(3)插入排序
插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。当然,刚开始这个有序的小序列只有1个元素,就是第一个元素。比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。

(4)快速排序
快速排序有两个方向,左边的i下标一直往右走,当a[i] <= a[center_index],其中center_index是中枢元素的数组下标,一般取为数组第0个元素。而右边的j下标一直往左走,当a[j] > a[center_index]。如果i和j都走不动了,i <= j,交换a[i]和a[j],重复上面的过程,直到i > j。 交换a[j]和a[center_index],完成一趟快速排序。在中枢元素和a[j]交换的时候,很有可能把前面的元素的稳定性打乱,比如序列为5 3 3 4 3 8 9 10 11,现在中枢元素5和3(第5个元素,下标从1开始计)交换就会把元素3的稳定性打乱,所以快速排序是一个不稳定的排序算法,不稳定发生在中枢元素和a[j] 交换的时刻。

(5)归并排序
归并排序是把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列,不断合并直到原序列全部排好序。可以发现,在1个或2个元素时,1个元素不会交换,2个元素如果大小相等也没有人故意交换,这不会破坏稳定性。那么,在短的有序序列合并的过程中,稳定是是否受到破坏?没有,合并过程中我们可以保证如果两个当前元素相等时,我们把处在前面的序列的元素保存在结果序列的前面,这样就保证了稳定性。所以,归并排序也是稳定的排序算法。

(6)基数排序
基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序,最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以其是稳定的排序算法。

(7)希尔排序(shell)
希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小, 插入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比O(n^2)好一些。由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。

(8)堆排序
我们知道堆的结构是节点i的孩子为2 * i和2 * i + 1节点,大顶堆要求父节点大于等于其2个子节点,小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列,堆排序的过程是从第n / 2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n / 2 - 1, n / 2 - 2, ... 1这些个父节点选择元素时,就会破坏稳定性。有可能第n / 2个父节点交换把后面一个元素交换过去了,而第n / 2 - 1个父节点把后面一个相同的元素没 有交换,那么这2个相同的元素之间的稳定性就被破坏了。所以,堆排序不是稳定的排序算法。

综上,得出结论: 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法,而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法

该文章转自http://www.cnblogs.com/codingmylife/archive/2012/10/21/2732980.html
分享到:
评论

相关推荐

    排序算法总结(转载)

    在选择排序算法时,需要综合考虑数据量大小、排序稳定性、内存限制以及编程实现的复杂性等因素。对于大数据量,优先考虑时间复杂度较低的算法,如归并排序、快速排序和堆排序;对于小数据量,简单易实现的冒泡排序、...

    python数据结构与算法详解与源码

    5-01 排序算法的稳定性 5-02 冒泡排序及实现 5-03 选择排序算法及实现 5-04 插入算法 5-05 插入排序 5-06 插入排序2 5-07 希尔排序 5-08 希尔排序实现 5-09 快速排序 5-10 快速排序实现1 (1) 5-10 快速...

    折半查找main.cpp

    将数据分为有序数据和无序数据,第一次排序时默认Array[0]为有序数据,Array[1]~Array[n-1]为无序数据。有序数据分区的第一个元素位置为low,最后一个元素的位置为high。 遍历无序区间的所有元素,每次取无序...

    亿级数据的高并发通用搜索引擎架构设计[转载]

    这类系统需要在海量数据的基础上提供快速、准确的搜索服务,同时还需要具备良好的扩展性和稳定性,以应对高并发访问。本篇文章将围绕这个主题展开,探讨相关的设计理念和技术要点。 首先,搜索引擎的核心在于数据的...

    Radmin自动登录器v3.0

    为了在功能和稳定性方面进一步提高和改进,v2.0版使用VC++ Unicode(MFC)编程,程序在编译时已经集成了VC运行库,可独立运行。 由于MFC越益臃肿笨重,为了提高稳定性和效率,v3.0版使用WTL VC++ Unicode编程,程序...

    悠索科技高校教务管理系统(转载)

    9. **数据结构与算法**:优化的算法和合理的数据结构能够提升系统处理教务数据的效率,如排序、搜索算法的应用。 10. **报表与图表**:可能集成了Crystal Reports或DevExpress等组件,用于生成各类统计报表和可视化...

    【转载】oracle创建数据库后创建自己的用户

    在Oracle数据库系统中,创建一个新数据库是数据库管理员(DBA)进行的初始任务...在实际操作中,应根据组织的安全策略和需求,合理配置用户的权限,避免过度授权,同时定期审查和调整权限设置,确保系统的稳定和安全。

    BBS论坛开发全套资料

    考虑到大量用户和数据,论坛需要优化,如缓存策略、负载均衡、数据库索引优化等,确保系统的稳定性和响应速度。 11. **安全防护**: 防SQL注入、XSS攻击、CSRF攻击是必要的,还需要防止恶意注册和垃圾信息。 12....

    常用的数据分析方法(转载)

    - **排列图**(帕累托图):将质量问题按重要程度排序,以便识别主要问题。通常用于质量改进项目中。 - **因果分析图**(鱼骨图):用于识别导致问题的各种因素,有助于深入理解问题的根本原因。 3. **掌握分层法...

    seo基础试题.pdf

    2. 服务器稳定性对网站排名有很大影响,因为不稳定可能导致搜索引擎无法正常抓取和索引网页。Title标签是网页标题,对排名影响显著;Keywords标签虽然现在影响力减弱,但仍有意义;网站内容和更新频率是决定排名的...

    【RPA之家转载视频教程9】使用UiPath automation Hub可以节省1000000美元的自动化成本.rar

    2. **需求管理**:收集到的自动化需求会被整理和优先级排序,确保团队专注于最具价值的项目。 3. **协作与设计**:团队成员可以一起讨论并设计自动化流程,确保解决方案符合业务需求。 4. **自动化构建**:提供...

    集团网站群管理规定.doc

    链接规则按照级别和用户量进行排序,确保信息的连贯性。 内容录入与更新的规定指出,每两周至少更新一次内容,内容涵盖文字、图片和附件。同时,严禁发布违法或有悖集团利益的信息。下级网站内容不得与上级冲突,且...

    SEO面试题以及答案

    3. **影响网站排名的因素**:服务器稳定性、Title标签、Keywords标签(尽管现在影响较小)、网站内容和更新频率等都是重要因素。 4. **友情链接选择**:优先选择与网站主题相关且PR(PageRank)高的链接。 5. **...

    seo面试题及答案[参考].pdf

    14. 搜索引擎基本工作流程包括抓取、索引和排序。 15. 子页设置相关链接可促进爬虫爬行,提升网站活跃度。 16. 通过关键词研究、内容优化和链接建设等方法进行SEO优化。 17. 选择次关键词可避免与大网站的直接竞争。...

    大工17春《SEO搜索引擎优化》在线作业1.docx

    3. **排序**: 当用户提交搜索请求后,搜索引擎会从索引库中找出与之匹配的结果,并按照一定的算法计算每条结果的相关性和质量,最终决定展示顺序。 ### SEO关键词策略 1. **关键词密度**: 最优的关键词密度通常被...

    thinkPHP5快速入门手册

    - **排序和分页**:说明如何对查询结果进行排序和分页显示。 - **聚合函数**:介绍如何使用聚合函数进行统计计算,如求和、平均值等。 #### 六、模型和关联 - **模型定义**:指导如何定义模型类,以及模型的基本...

    HY462x_Application Notes_TC_Preliminary V3.0.pdf

    根据文档中的信息,HY462x系列IC被设计用于高性能的触控面板应用,强调了其稳定性和多功能性。这些芯片支持多点触控,具备高级的环境适应能力,并且为了方便用户的开发,提供了一整套的开发工具和完整的开发资料。在...

    最好的asp CMS系统科讯CMSV7.0全功能SQL商业版,KesionCMS V7.0最新商业全能版-免费下载

    8、自定义字段功能:可自由设置字段类型、字段类型(单行文本、多行文本、下拉列表、数字、日期、单选按钮、多选按钮、电子邮箱、文件)、表单选项限制(功能启用时间限制、是否只允许会员...,可按自定义字段搜索和排序...

    vue列表数据发生变化指令没有更新问题及解决方法

    在上述例子中,`:key='index'`可能导致问题,因为当过滤或排序列表时,尽管数据发生了变化,但索引可能保持不变,导致Vue认为元素没有变化,从而不触发指令的更新。 **问题分析:** 在Vue的`v-for`循环中,`:key`...

Global site tag (gtag.js) - Google Analytics