【算法】快速排序与归并排序对比_快速排序和归并排序区别-程序员宅基地

技术标签: 算法  快速排序  归并排序  

算法 系列博客

【算法】刷题范围建议 和 代码规范
【算法】复杂度理论 ( 时间复杂度 )

【字符串】最长回文子串 ( 蛮力算法 )
【字符串】最长回文子串 ( 中心线枚举算法 )
【字符串】最长回文子串 ( 动态规划算法 ) ★
【字符串】字符串查找 ( 蛮力算法 )
【字符串】字符串查找 ( Rabin-Karp 算法 )

【算法】双指针算法 ( 双指针算法分类 | 相向双指针 | 有效回文串 )
【算法】双指针算法 ( 有效回文串 II )
【算法】哈希表 ( 两数之和 )

【算法】快速排序
【算法】归并排序
【算法】快速排序与归并排序对比






一、时间复杂度



快速排序 ( Quick Sort )归并排序 ( Merge Sort ) 的时间复杂度都是 O ( n log ⁡ n ) O(n \log n) O(nlogn) ;


快速排序 的 平均时间复杂度 O ( n log ⁡ n ) O(n \log n) O(nlogn) , 该时间复杂度是一个期望值 , 快速排序在 最坏情况下会达到 O ( n 2 ) O(n^2) O(n2) ;

如 : 数组 [1,2,3] 排序 , 有 6 种排列方式 , 计算这 6 种排序时间复杂度的平均期望就是 O ( n log ⁡ n ) O(n \log n) O(nlogn) ;

最坏的情况时 [1,2,3] 排列情况 , 时间复杂度 O ( n 2 ) O(n^2) O(n2) ;


归并排序 的 最好情况下的时间复杂度最坏情况下的时间复杂度 都是 O ( n log ⁡ n ) O(n \log n) O(nlogn) ;


从时间复杂度来讲 , 归并排序 的稳定性 要比 快速排序 高 , 二者时间复杂度相当 ;





二、空间复杂度



从空间复杂度来讲 , 归并排序 的空间复杂度是 O ( n ) O(n) O(n) , 快速排序 的空间复杂度是 O ( 1 ) O(1) O(1) , 快速排序没有使用额外的空间 , 在数组原地进行排序 ,





三、排序稳定性



排序的稳定性 : 假如数组中有两个相同的元素 , 给这两个相同的元素分别打上标记 , 如果每次排列得到的元素顺序都是相同的 , 则说明该排序是稳定的 ;

如 : { 2 , 1 , 1 , 2 } \{2,1,1,2\} { 2,1,1,2} , 中给 2 2 2 打上标记 , { 2 ′ , 1 , 1 , 2 ′ ′ } \{2',1,1,2''\} { 2,1,1,2} , 最终排序后是 { 1 , 1 , 2 ′ , 2 ′ ′ } \{1,1,2', 2''\} { 1,1,2,2} 还是 { 1 , 1 , 2 ′ ′ , 2 ′ } \{1,1,2'', 2'\} { 1,1,2,2} ;

快速排序中 , 这两个结果随机出现 , 同样使用快速排序 , 并不能保证得到的是相同的标记元素次序 ;

归并排序 , 可以保证 , 每次排序 , 得到的都是相同的结果 ;





三、局部有序与整体有序



快速排序 与 归并排序 , 都是将数组分为两个部分 , 然后两部分再次进行递归 ;


快速排序 随便选择了一个数组元素 p 作为中心点 , 将小于等于 p 的元素放在左边 , 将大于等于 p 的元素放在了右边 , 分割完毕后 , 左侧的元素肯定小于右侧的元素 ;
然后对左侧 和 右侧 再次分别选择一个元素 m , n , 进行分割 , 分为 4 份 ,
在 4 份的基础上 , 再次进行分割 , 分为 8 份 , 递归调用该快速排序算法 , 直到所有的元素有序为止 ;

快速排序 是 先整体有序 , 然后局部有序 ;


归并排序 先根据中心点分成两部分 , 左侧和右侧分别进行排序 , 两遍都排序完毕后 , 再组合到一起 ;

归并排序 是 先局部有序 , 然后整体有序 ;

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/han1202012/article/details/119154236

智能推荐

第二十六章 Caché 使用%Dictionary类_cache数据库%dictionary-程序员宅基地

文章浏览阅读782次。文章目录第二十六章 Caché 使用%Dictionary类类定义类简介浏览类定义更改类定义第二十六章 Caché 使用%Dictionary类本附录讨论了类定义类,这是一组持久类,它们提供对所有类定义的对象和SQL访问。类定义类简介类定义类提供对Caché统一字典的对象和SQL访问。使用这些类,可以以编程方式检查类定义,修改类定义,创建新类,甚至编写自动生成文档的程序。这些类包含在%Di..._cache数据库%dictionary

图片热点_图片“热点”-程序员宅基地

文章浏览阅读120次。图片热点: 规划出图片上的一个区域,可以做出超链接,直接点击图片区域就可以完成跳转的效果 网页划区: 在一个网页里,规划出一个区域用来展示另一个网页的内容。 网..._图片“热点”

Windows系统下:jenkins+selenium+TestNG一步搞定简单自动化持续集成_jenkins+selenium+java持续集成-程序员宅基地

文章浏览阅读9.6k次,点赞2次,收藏18次。Windows系统下:jenkins+selenium+TestNG一步搞定简单自动化持续集成注意!注意!本篇只介绍Windows系统下的操作!1.安装jenkins,最好从官网下载并安装:https://jenkins.io/download/,安装过程很简单,一路下一步就可以。安装过程中的小插曲,如图:然后按照导航默认选择的进行启动jenkins服务即可。【_jenkins+selenium+java持续集成

NUll的作用和意义_null指针的地址-程序员宅基地

文章浏览阅读2.9k次,点赞2次,收藏16次。空地址NULL意义所在深入核心技术与架构,分享典型创新之道,全景展现全栈式分析服务主题演讲和6大分会场,40+前沿技术主题,尽在亚马逊云科技数据驱动在线峰会NULL其地址值为0,而由于任何进程的0地址开始存储的都是系统关键地址,比如进程的退出,堆栈维护,键盘处理等系统控制程序的地址。因此0地址是不允许用户代码中直接读写访问的(hacking除外),如果某指针被赋予NULL,之后该指针被用来操作对象或内存,要么在编译时报错,要么运行时程序崩溃。指针被赋值为NULL的意义在于,将NULL作为唯一无效指针_null指针的地址

NLP/Transformer/BERT/Attention面试问题与答案_attention面试题-程序员宅基地

文章浏览阅读2.4k次。主要聚焦目前处于NLP舞台中央的Transformer/BERT/后BERT 和 Self Attention。筛选的问题会深入到上述算法/模型更细节的地方,而尽量避免大而泛的问题。本文希望能帮助你对Transformer/BERT的理解再深一层,而这也要求你对上面的算法/模型有基本的认识,主要包括这两部分(后BERT的模型可以自行查找):1、论文:论文是最一手的资源,没有各方解读的杂音Transformer:Attention Is All You NeedBERT:Pre-train.._attention面试题

服务器装系统驱动程序,服务器装系统驱动-程序员宅基地

文章浏览阅读2.2k次。服务器装系统驱动 内容精选换一换Windows Server 2012 R2操作系统弹性云服务器,本地使用远程桌面连接功能连接云服务器并启用redirected drive功能时,云服务器出现蓝屏。远程桌面连接启用了redirected drive功能,同时加载对应rdpdr.sys驱动,该驱动可能会导致云服务器操作系统崩溃,无法正常运作(例如错误码:0x18, 0x5该任务以“Windows S..._服务器驱动

随便推点

基于Java+SpringBoot+Vue前后端分离毕业论文管理系统设计和实现-程序员宅基地

文章浏览阅读1.2k次,点赞30次,收藏20次。随着Internet的发展,以网络为支撑的论文管理系统不但可以让学生随时随地提交论文,老师也可以通过电脑或者移动终端随时随地下载论文,对论文进行审核,有关单位部门的工作人员和导师也能随时获取相关信息进行毕业生论文的管理工作,相较于传统手工方式管理毕业生的论文,这种方式大大提高了学校教育管理的工作效率。如何把论文管理工作转移到基于网络的毕业论文管理系统上,保证论文管理合理、简化评审专家工作、系统高效稳定是目前各大高校研究的热门,为此本文设计并实现了一套毕业论文管理系统。_前后端分离毕业论文

iOS [NSURL URLWithString:] 返回nil解决办法_[nsurl urlwithstring:string] nil-程序员宅基地

文章浏览阅读1.7k次。iOS [NSURL URLWithString:] 返回nil解决办法先对url 做UTF-8编码NSString* urlString = @“http://www.baidu.com”;urlString = [urlString stringByAddingPercentEscapesUsingEncoding:NSUTF8StringEncoding];NSURL *url = ..._[nsurl urlwithstring:string] nil

计算机视觉入门路线_计算机视觉入门路线cv技术指南-程序员宅基地

文章浏览阅读4.1k次。给大家写了一个计算机视觉入门路线,这个路线一共分为十一步,每一步指明了学习内容,学习程度,学习方式和学习目的,并指明了各个内容的重难点。欢迎关注公众号CV技术指南,专注于计算机视觉的技术总结、最新技术跟踪、经典论文解读、CV招聘信息。本文主要介绍计算机视觉从入门到具备自主学习能力的一个学习路线。在介绍具体内容前,有必要先说明现在计算机视觉的情况。计算机视觉是一个需要会的内容特别多,基础要求牢固,知识面要求足够广的领域。计算机视觉领域有一个最大的问题在于它使用的方法具有黑盒的特点,一个_计算机视觉入门路线cv技术指南

第二十二章 Caché 设计模式 享元模式_姚鑫cache-程序员宅基地

文章浏览阅读685次。文章目录第二十二章 Caché 设计模式 享元模式定义优点使用场景结构图描述完整示例实体类抽象享元角色实现享元角色享元工厂调用思考第二十二章 Caché 设计模式 享元模式定义运用共享技术有效地支持大量细粒度的对象。优点享元模式可以避免大量非常相似类的开销,在程序设计中,有时需要生成大量细粒度的类实例来表示数据。如果能发现这些实例除了几个参数外基本上相同的,有时就能够大幅度地减少需要..._姚鑫cache

HTML列表元素-程序员宅基地

文章浏览阅读79次,点赞6次,收藏2次。在html中,我们的列表可以有很多种表现方式,有阿拉伯数字、罗马数字、字母等,也有着圆点表示的。方式多种多样。大体分类如下图:

angular生命周期函数_angularjs生命周期函数-程序员宅基地

文章浏览阅读1.2k次。对于单页面应用来说,组件的生命周期在开发中至关重要。了解生命周期,在适当的时机处理不同的逻辑,从而使应用更加合理与健壮。(原文阅读)定义:当 Angular实例化组件类并渲染组件视图及其子视图时,组件实例的生命周期就开始了。生命周期一直伴随着变更检测,Angular会检查数据绑定属性何时发生变化,并按需更新视图和组件实例。当 Angular销毁组件实例并从 DOM中移除它渲染的模板时,生命周期就结束了。tips:演示将在life-cycle组件中进行。生命周期顺序Angular有以下8个生命周期._angularjs生命周期函数