【数据结构与算法】如何对快速排序进行细节优化以及实现非递归版本的快速排序?
即使走的再远,也勿忘启程时的初心
C/C++ 游戏开发
Hello,米娜桑们,这里是君兮_,国庆长假结束了,无论是工作还是学习都该回到正轨上来了,从今天开始恢复正常的更新频率,今天为大家带来的内容是快速排序的两大优化和非递归实现
- 好了废话不多说,开始我们今天的学习吧!!
快排优化与非递归实现
- 快速排序优化
- 三数去中优化
- 对递归次数的优化
- 非递归的快速排序
- 总结
快速排序优化
- 有关快速排序的基本内容可以去看看这篇博客,讲的已经非常详细了
【算法速查】万字图解带你快速入门八大排序(下) - 我们在这里就以hoare版本的快速排序来讲讲还可以优化的地方以及为什么
- hoare版本的快速排序代码如下:
Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
int getMid(int* a, int left, int right)
{assert(a);int mid = (left + right) / 2;if (a[left] > a[mid]){if (a[mid] > a[right])return mid;else if(a[right]>a[left]){return left;}else{return right;}}else{if (a[mid] < a[right])return mid;else if (a[left] > a[right]){return left;}else{return right;}}
}
int PartSort1(int* a, int left, int right)
{int mid = getMid(a, left, right);//三数取中//把取好的key放到left中Swap(&a[left], &a[mid]);int key = left;while (left<right){//右边先走while (left < right && a[right] >= a[key]){right--;}//左边走while (left<right&&a[left]<=a[key]){left++;}//交换Swap(&a[left], &a[right]);}//交换停下的位置的值把key换到此时左右相遇的位置Swap(&a[key], &a[left]);//此时key的左右都有序,由于right,left都指处于key的位置返回任意即可return right;
}
void QuickSort(int* a, int left,int right)
{//只剩下一个值了,说明已经有序,不需要再排,递归结束if (left >= right)return;int key = PartSort1(a,left,right);//key已经满足左右都有序了不需要再排//排key的左边QuickSort(a, left, key-1);//排key的右边QuickSort(a, key+1, right);}
三数去中优化
-
我们知道,快速排序是先取一个key值然后让左右两边有序来进行排序的,因此key值的取值对我们快速排序的速度是有比较大的影响的,举个最坏的例子,假设每次我们取到的key值都是此次所需排序数据中最小的,如下图所示
-
此时的时间复杂度就是O(N^2)了,因此,我们需要对快速排序进行优化,尽量减少出现图示的这种情况,就有了以下的代码
int getMid(int* a, int left, int right)
{assert(a);int mid = (left + right) / 2;if (a[left] > a[mid]){if (a[mid] > a[right])return mid;else if(a[right]>a[left]){return left;}else{return right;}}else{if (a[mid] < a[right])return mid;else if (a[left] > a[right]){return left;}else{return right;}}
}
- 简单的来说,上述这段代码表示的是这样的意思
取最左,最右,中间三个数,分别对三个数进行比较,最终取得的值就是处于三个值中中间的这个值。 - 通过上述这个优化,此时所需排序的数据中总要比我们取得的key值小以及比我们取得的key值大的值存在,就能较大的提供我们的快排效率啦!
对递归次数的优化
- 我们在使用递归版本的快速排序时,当区间中的数比较少时,仍然使用递归的方式进行是会消耗非常多不必要消耗的内存的,还是举个例子:假设此时区间中还有10个数需要排
- 我们递归返回的条件是left>=right,递归是栈中开辟空间进行的,当递归的层数过深,栈的大小又不是很大,就容易造成“爆栈”,如上图所示,为了排序这十个数,我们又递归了这么多层,是非常不明智的选择,因此,我们在数据较少的情况出现时,可以使用插入排序等方法进行排序,减少不必要的空间浪费,也能提供我们快排的速度
void QuickSort1(int* a, int begin, int end)
{if (begin >= end)return;// 小区间优化,小区间不再递归分割排序,降低递归次数if ((end - begin + 1) > 10){int keyi = PartSort1(a, begin, end);// [begin, keyi-1] keyi [keyi+1, end]QuickSort1(a, begin, keyi - 1);QuickSort1(a, keyi + 1, end);}else{InsertSort(a + begin, end - begin + 1);}
}
- 好了,讲完了上述对递归版本的快排优化,接下来我们讲讲快速排序的非递归版本
非递归的快速排序
- 我们上面讲了,递归是在栈空间中进行的,栈空间又比较小,当递归层数比较深时就会造成“爆栈”,因此对于快速排序这种我们常用的排序算法来说,掌握其非递归版本也是非常重要的
- 想要了解非递归,我们就必须从递归开始下手,我们再来看看递归的这段代码
void QuickSort1(int* a, int begin, int end)
{if (begin >= end)return;// 小区间优化,小区间不再递归分割排序,降低递归次数if ((end - begin + 1) > 10){int keyi = PartSort1(a, begin, end);// [begin, keyi-1] keyi [keyi+1, end]QuickSort1(a, begin, keyi - 1);QuickSort1(a, keyi + 1, end);}else{InsertSort(a + begin, end - begin + 1);}
}
- 如果你学过数据结构的话,会发现我们递归与栈是非常类似的,栈是后进先出,最后再处理最先放入的,而递归也是先往深处走,再往回返,因此,我们在实现非递归的快速排序时,选用栈这种数据结构来帮助我们进行。
void QuickSortNonR(int* a, int left,int right)
{Stack st;StackInit(&st);//初始化栈StackPush(&st, left);//入栈StackPush(&st, right);while (!StackEmpty(&st))//判断栈是否为空{int right = StackTop(&st);//后进先出,取栈顶元素StackPop(&st);//此时的栈顶元素出栈int left = StackTop(&st);//此时的栈顶为leftStackPop(&st);int key = PartSort1(a, left, right);//选key值if (key + 1 < right)//此时key+1小于right 把key+1作为下一次排序的左 right作为右入栈{StackPush(&st, key + 1);StackPush(&st, right);}if (left < key - 1)//key-1大于left key-1就为下一次循环的右,left为左{StackPush(&st, left);StackPush(&st, key - 1);}}//当栈中没有元素了,说明此时的左大于等于右,此时已经没有数据未进行排序了StackDestroy(&st);//销毁栈
}
- 和递归大致是一样的,只不过我们是用栈的方式来模拟递归朝深度进行,如果你能理解递归实现的快速排序,相信非递归实现的快速排序对你来说也非常好理解
- 唯一需要注意的是入栈和出栈的顺序,当你开始先入右再入左的话,由于后进先出的原因,先出的是左其中是右,这点在取栈顶元素作为排序的左右区间时一定要注意避免取错。
总结
- 好啦,我们总算把八大排序算法都讲完了,算法这一块光靠看代码不是那么容易理解的,因此我花了大量的时间画图分析,希望能对你有所帮助
- 当然,这篇文章创作的初衷是希望帮助初学者对排序算法有一个大致的了解,对已经学过的人起到在需要使用的时候快速回忆的效果,因此可能还有一部分细节不全,之后我会挑出重点单独出博客讲解
- 有任何的问题和对文章内容的疑惑欢迎在评论区中提出,当然也可以私信我,我会在第一时间回复的!!
新人博主创作不易,如果感觉文章内容对你有所帮助的话不妨三连一下再走呗。你们的支持就是我更新的动力!!!
**(可莉请求你们三连支持一下博主!!!点击下方评论点赞收藏帮帮可莉吧)**
相关文章:

【数据结构与算法】如何对快速排序进行细节优化以及实现非递归版本的快速排序?
君兮_的个人主页 即使走的再远,也勿忘启程时的初心 C/C 游戏开发 Hello,米娜桑们,这里是君兮_,国庆长假结束了,无论是工作还是学习都该回到正轨上来了,从今天开始恢复正常的更新频率,今天为大家带来的内容…...

【电商API接口的应用:电商数据分析入门】初识Web API(一)
如何使用Web应用变成接口(API)自动请求网站到特定信息而不是整个网站,再对这些信息进行可视化。由于这样编写到程序始终使用最新到数据来生成可视化,因此即便数据瞬息万变,它呈现到信息也都是最新的。 使用Web API Web API是网站的一部分&am…...

大运新能源天津车展深度诠释品牌魅力 为都市人群打造理想车型
如今,新能源汽车行业发展潜力巨大,不断吸引无数车企入驻新能源汽车赛道,而赛道的持续紧缩也让一部分车企很难找到突破重围的机会。秉持几十年的造车经验,大运新能源凭借雄厚的品牌实力从一众车企中脱颖而出。从摩托车到重卡&#…...
深入浅出:react高阶成分(HOC)的应用
React中的HOC(Higher-Order Component)是一种高阶组件的模式,它是一个函数,接收一个组件作为参数,并返回一个新的包装组件。HOC可以用于增强组件的功能,例如添加属性、处理生命周期方法、共享状态等。 HOC…...

分库分表(3)——ShardingJDBC实践
一、ShardingSphere产品介绍 Apache ShardingSphere 是一套开源的分布式数据库中间件解决方案组成的生态圈,它由 JDBC、Proxy 和 Sidecar(规划中)这 3 款相互独立,却又能够混合部署配合使用的产品组成。 它们均提供标准化的数据分…...

Xcode 15下,包含个推的项目运行时崩溃的处理办法
升级到Xcode15后,部分包含个推的项目在iOS17以下的系统版本运行时,会出现崩溃,由于崩溃在个推Framework内部,无法定位到具体代码,经过和个推官方沟通,确认问题是项目支持的最低版本问题。 需要将项目的最低…...

《安富莱嵌入式周报》第324期:单对以太网技术实战,IROS2023迪士尼逼真机器人展示,数百万模具CAD文件下载,闭环步进电机驱动器,CANopen全解析
周报汇总地址:嵌入式周报 - uCOS & uCGUI & emWin & embOS & TouchGFX & ThreadX - 硬汉嵌入式论坛 - Powered by Discuz! 更新一期视频教程: 第8期ThreadX视频教程:应用实战,将裸机工程移植到RTOS的任务划分…...

Kafka集群架构设计原理详解
从 Zookeeper 数据理解 Kafka 集群工作机制 这一部分主要是理解 Kafka 的服务端重要原理。但是 Kafka 为了保证高吞吐,高性能,高可扩展的三高架构,很多具体设计都是相当复杂的。如果直接跳进去学习研究,很快就会晕头转向。所以&am…...

学习Kotlin编程语言
官网地址 https://developer.android.google.cn/kotlin/learn?hlzh-cn 脑图...
js文字逐个显示
定时器每隔一段时间,替换文本内容,,substring 截取更多的字符串显示 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>Title</title> </head> <body…...

电子沙盘数字沙盘大数据人工智能开发教程第16课
电子沙盘数字沙盘大数据可视化GIS系统开发教程第16课:新增加属性在MTGIS3d控件 public bool ShowFLGrid;//是否显 示方里网格。 public bool Atmosphere;//是否显示大气圈。(因为WPF不支持shader功能,所以效果嘛。。。) 在SDK中为…...

dockerfile lnmp 搭建wordpress、docker-compose搭建wordpress
-----------------安装 Docker--------------------------- 目前 Docker 只能支持 64 位系统。systemctl stop firewalld.service setenforce 0#安装依赖包 yum install -y yum-utils device-mapper-persistent-data lvm2 --------------------------------------------------…...

手写模拟SpringBoot核心流程
通过手写模拟实现一个Spring Boot,让大家能以非常简单的方式就能知道Spring Boot大概是如何工作的。 依赖 建一个工程,两个Module: 1.springboot模块,表示springboot框架的源码实现 2.user包,表示用户业务系统,用来写…...

怒刷LeetCode的第26天(Java版)
第一题 题目来源 64. 最小路径和 - 力扣(LeetCode) 题目内容 解决方法 方法一:动态规划 可以使用动态规划来解决这个问题。 首先创建一个与网格大小相同的二维数组dp,用于存储从起点到每个位置的最小路径和。然后初始化dp[0…...
Linux文件基本权限
一、Linux权限 简介 在Linux系统中,每个文件和目录都有读(r),写(w)和执行(x)权限,这些权限决定了用户对该文件或目录的访问方式。Linux服务器上有严格的权限等级,如果权限过高导致误操作会增加服务器的风险。文件权限 只有root用户和文件拥有者才可以修改文件访问权…...

Unity设计模式——装饰模式
装饰模式(Decorator),动态地给一个对象添加一些额外的职责,就增加功能来说,装饰模式比生成子类更为灵活。 Component类: abstract class Component : MonoBehaviour {public abstract void Operation(); …...

Http请求响应 Ajax 过滤器
10/10/2023 近期总结: 最近学的后端部署,web服务器运行,各种请求响应,内容很多,学的很乱,还是需要好好整理,前面JavaSE内容还没有完全掌握,再加上一边刷题,感觉压力很大哈…...
【Qt控件之QTableWidget】使用及技巧
简介 QTableWidget是Qt中的表格控件,用于显示和编辑二维表格数据,QTableView类的子类。 可以和定时器结合,实现定时刷新表格中的数据或执行其他与表格相关的操作。 主要函数说明 定时器相关函数(用于刷新表格数据): void startT…...

算法-动态规划/中心扩散法-最长回文子串
算法-动态规划/中心扩散法-最长回文子串 1 题目概述 1.1 题目出处 https://leetcode.cn/problems/longest-palindromic-substring 1.2 题目描述 2 动态规划 2.1 思路 dp[i][j] 表示[i,j]之间的字符串是否是回文。 那么,如果chars[i] chars[j]时,就…...
(6)SpringMVC中使用CharacterEncodingFilter编码过滤器处理请求和响应的乱码问题
处理SpringMVC中乱码问题 处理原生Servlet中请求和响应的乱码问题,参考文章 Servlet中的过滤器的实现及其原理,参考文章 配置CharacterEncodingFilter 在Servlet规范中要求request和response对象设置编码之前不能有获取请求参数和响应数据的操作,否则后续设置的编码都将不起…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...

用docker来安装部署freeswitch记录
今天刚才测试一个callcenter的项目,所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

算法岗面试经验分享-大模型篇
文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer (1)资源 论文&a…...

FFmpeg:Windows系统小白安装及其使用
一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】,注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录(即exe所在文件夹)加入系统变量…...
vue3 daterange正则踩坑
<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...

数据结构:递归的种类(Types of Recursion)
目录 尾递归(Tail Recursion) 什么是 Loop(循环)? 复杂度分析 头递归(Head Recursion) 树形递归(Tree Recursion) 线性递归(Linear Recursion)…...

网页端 js 读取发票里的二维码信息(图片和PDF格式)
起因 为了实现在报销流程中,发票不能重用的限制,发票上传后,希望能读出发票号,并记录发票号已用,下次不再可用于报销。 基于上面的需求,研究了OCR 的方式和读PDF的方式,实际是可行的ÿ…...
用 FFmpeg 实现 RTMP 推流直播
RTMP(Real-Time Messaging Protocol) 是直播行业中常用的传输协议。 一般来说,直播服务商会给你: ✅ 一个 RTMP 推流地址(你推视频上去) ✅ 一个 HLS 或 FLV 拉流地址(观众观看用)…...
MySQL基本操作(续)
第3章:MySQL基本操作(续) 3.3 表操作 表是关系型数据库中存储数据的基本结构,由行和列组成。在MySQL中,表操作包括创建表、查看表结构、修改表和删除表等。本节将详细介绍这些操作。 3.3.1 创建表 在MySQL中&#…...
触发DMA传输错误中断问题排查
在STM32项目中,集成BLE模块后触发DMA传输错误中断(DMA2_Stream1_IRQHandler进入错误流程),但单独运行BLE模块时正常,表明问题可能源于原有线程与BLE模块的交互冲突。以下是逐步排查与解决方案: 一、问题根源…...