当前位置: 首页 > news >正文

【数据结构与算法】如何对快速排序进行细节优化以及实现非递归版本的快速排序?

在这里插入图片描述

君兮_的个人主页

即使走的再远,也勿忘启程时的初心

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);//销毁栈
}
  • 和递归大致是一样的,只不过我们是用栈的方式来模拟递归朝深度进行,如果你能理解递归实现的快速排序,相信非递归实现的快速排序对你来说也非常好理解
  • 唯一需要注意的是入栈和出栈的顺序,当你开始先入右再入左的话,由于后进先出的原因,先出的是左其中是右,这点在取栈顶元素作为排序的左右区间时一定要注意避免取错。

总结

  • 好啦,我们总算把八大排序算法都讲完了,算法这一块光靠看代码不是那么容易理解的,因此我花了大量的时间画图分析,希望能对你有所帮助
  • 当然,这篇文章创作的初衷是希望帮助初学者对排序算法有一个大致的了解,对已经学过的人起到在需要使用的时候快速回忆的效果,因此可能还有一部分细节不全,之后我会挑出重点单独出博客讲解
  • 有任何的问题和对文章内容的疑惑欢迎在评论区中提出,当然也可以私信我,我会在第一时间回复的!!

新人博主创作不易,如果感觉文章内容对你有所帮助的话不妨三连一下再走呗。你们的支持就是我更新的动力!!!

**(可莉请求你们三连支持一下博主!!!点击下方评论点赞收藏帮帮可莉吧)**

在这里插入图片描述

相关文章:

【数据结构与算法】如何对快速排序进行细节优化以及实现非递归版本的快速排序?

君兮_的个人主页 即使走的再远&#xff0c;也勿忘启程时的初心 C/C 游戏开发 Hello,米娜桑们&#xff0c;这里是君兮_&#xff0c;国庆长假结束了&#xff0c;无论是工作还是学习都该回到正轨上来了&#xff0c;从今天开始恢复正常的更新频率&#xff0c;今天为大家带来的内容…...

【电商API接口的应用:电商数据分析入门】初识Web API(一)

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

大运新能源天津车展深度诠释品牌魅力 为都市人群打造理想车型

如今&#xff0c;新能源汽车行业发展潜力巨大&#xff0c;不断吸引无数车企入驻新能源汽车赛道&#xff0c;而赛道的持续紧缩也让一部分车企很难找到突破重围的机会。秉持几十年的造车经验&#xff0c;大运新能源凭借雄厚的品牌实力从一众车企中脱颖而出。从摩托车到重卡&#…...

深入浅出:react高阶成分(HOC)的应用

React中的HOC&#xff08;Higher-Order Component&#xff09;是一种高阶组件的模式&#xff0c;它是一个函数&#xff0c;接收一个组件作为参数&#xff0c;并返回一个新的包装组件。HOC可以用于增强组件的功能&#xff0c;例如添加属性、处理生命周期方法、共享状态等。 HOC…...

分库分表(3)——ShardingJDBC实践

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

Xcode 15下,包含个推的项目运行时崩溃的处理办法

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

《安富莱嵌入式周报》第324期:单对以太网技术实战,IROS2023迪士尼逼真机器人展示,数百万模具CAD文件下载,闭环步进电机驱动器,CANopen全解析

周报汇总地址&#xff1a;嵌入式周报 - uCOS & uCGUI & emWin & embOS & TouchGFX & ThreadX - 硬汉嵌入式论坛 - Powered by Discuz! 更新一期视频教程&#xff1a; 第8期ThreadX视频教程&#xff1a;应用实战&#xff0c;将裸机工程移植到RTOS的任务划分…...

Kafka集群架构设计原理详解

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

学习Kotlin编程语言

官网地址 https://developer.android.google.cn/kotlin/learn?hlzh-cn 脑图...

js文字逐个显示

定时器每隔一段时间&#xff0c;替换文本内容&#xff0c;&#xff0c;substring 截取更多的字符串显示 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>Title</title> </head> <body…...

电子沙盘数字沙盘大数据人工智能开发教程第16课

电子沙盘数字沙盘大数据可视化GIS系统开发教程第16课&#xff1a;新增加属性在MTGIS3d控件 public bool ShowFLGrid;//是否显 示方里网格。 public bool Atmosphere;//是否显示大气圈。&#xff08;因为WPF不支持shader功能&#xff0c;所以效果嘛。。。&#xff09; 在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&#xff0c;让大家能以非常简单的方式就能知道Spring Boot大概是如何工作的。 依赖 建一个工程&#xff0c;两个Module: 1.springboot模块&#xff0c;表示springboot框架的源码实现 2.user包&#xff0c;表示用户业务系统&#xff0c;用来写…...

怒刷LeetCode的第26天(Java版)

第一题 题目来源 64. 最小路径和 - 力扣&#xff08;LeetCode&#xff09; 题目内容 解决方法 方法一&#xff1a;动态规划 可以使用动态规划来解决这个问题。 首先创建一个与网格大小相同的二维数组dp&#xff0c;用于存储从起点到每个位置的最小路径和。然后初始化dp[0…...

Linux文件基本权限

一、Linux权限 简介 在Linux系统中,每个文件和目录都有读(r),写(w)和执行(x)权限,这些权限决定了用户对该文件或目录的访问方式。Linux服务器上有严格的权限等级,如果权限过高导致误操作会增加服务器的风险。文件权限 只有root用户和文件拥有者才可以修改文件访问权…...

Unity设计模式——装饰模式

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

Http请求响应 Ajax 过滤器

10/10/2023 近期总结&#xff1a; 最近学的后端部署&#xff0c;web服务器运行&#xff0c;各种请求响应&#xff0c;内容很多&#xff0c;学的很乱&#xff0c;还是需要好好整理&#xff0c;前面JavaSE内容还没有完全掌握&#xff0c;再加上一边刷题&#xff0c;感觉压力很大哈…...

【Qt控件之QTableWidget】使用及技巧

简介 QTableWidget是Qt中的表格控件&#xff0c;用于显示和编辑二维表格数据&#xff0c;QTableView类的子类。 可以和定时器结合&#xff0c;实现定时刷新表格中的数据或执行其他与表格相关的操作。 主要函数说明 定时器相关函数(用于刷新表格数据)&#xff1a; void startT…...

算法-动态规划/中心扩散法-最长回文子串

算法-动态规划/中心扩散法-最长回文子串 1 题目概述 1.1 题目出处 https://leetcode.cn/problems/longest-palindromic-substring 1.2 题目描述 2 动态规划 2.1 思路 dp[i][j] 表示[i,j]之间的字符串是否是回文。 那么&#xff0c;如果chars[i] chars[j]时&#xff0c;就…...

(6)SpringMVC中使用CharacterEncodingFilter编码过滤器处理请求和响应的乱码问题

处理SpringMVC中乱码问题 处理原生Servlet中请求和响应的乱码问题,参考文章 Servlet中的过滤器的实现及其原理,参考文章 配置CharacterEncodingFilter 在Servlet规范中要求request和response对象设置编码之前不能有获取请求参数和响应数据的操作,否则后续设置的编码都将不起…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...