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

快速排序(下)

快速排序(下)

在这里插入图片描述

前言

在上一篇文章中我们了解了快速排序算法,但那是Hoare的版本,其实还有别的版本:一种是挖坑法,它们的区别主要在于如何找基准值。霍尔的版本思路难理解但代码好理解,挖坑法则是思路好理解但代码不好理解;还有一种是lomuto的前后指针法
此外,还有不使用递归的快排方法(找基准值还是用的三种方法之一)。

本文就来讲解这几种不同的快排方法。

正文

挖坑法

实现思路

创建左右指针。首先从右向左找出比基准值小的数据,找到后立即放入左边坑中,当前位置变为新的“坑”,然后从左向右找出比基准值大的数据,找到后立即放入右边坑中,当前位置变为新的“坑”,结束循环后将最开始存储的分界值放入当前的“坑”中,返回当前“坑”的下标(即分界值下标)。

画图理解一下什么是“坑”。

这就是整个“挖坑”然后“填坑”直到left和right重叠时将基准值放到该位置(它该待的位置)的过程。

现在我们可以来写一下挖坑法的代码:

//挖坑法
int _QuickSort(int* arr, int left, int right)
{int hole = left;int key = arr[hole];while (left < right)//注意和霍尔版区别{//这里同样需要限制且不能是arr[right] >= key,否则可能无法“二分”,最终效率低下while (left < right && arr[right] > key){--right;}arr[hole] = arr[right];hole = right;while (left < right && arr[left] < key){++left;}arr[hole] = arr[left];hole = left;}arr[hole] = key;return hole;
}
排序效果

我们在main函数中写这样的代码:

	int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };int n = sizeof(a) / sizeof(int);printf("排序前: ");PrintArr(a, n);//代码不具体展示QuickSort(a, 0, n-1);printf("排序后: ");PrintArr(a, n);

执行结果:

可以看到我们就成功排序了。


lomuto前后指针法

实现思路

创建前后指针,从左往右找比基准值小的进行交换,使得小的都排在基准值的左边。

其实前后指针对于很多学过数据结构的人来说应该已经不陌生了,但是快排也能用到前后指针法,我们看看具体怎么做

  • 定义两个变量prev和cur,让cur指向位置的数据和key值比较
    1. 若arr[cur]<arr[key],prev向后走一步并和cur交换
    2. 若arr[cur]>=arr[key],cur继续往后
  • 退出循环后将prev与key值交换,找到基准值

同样不变的思路也是要找基准值,也就是要让基准值左侧的数据都小于基准值,让基准值右侧的数据都大于基准值。

那么两个变量的作用是什么?可以说prev是用来占坑的,而cur用来找小,找到小后就让prev加一后和cur交换。退出循环后将prev与key值交换,就找到了基准值。

代码:

//lomuto前后指针法
int _QuickSort(int* arr, int left, int right)
{int prev = left, cur = left + 1;int key = left;while (cur<=right){if (arr[cur] < arr[key] && ++prev !=cur)//prev和cur相同就不交换//写为arr[cur] <= arr[key],加上等号也是殊途同归{Swap(&arr[cur], &arr[prev]);}cur++;//进不进循环cur都要往后走}Swap(&arr[key], &arr[prev]);return prev;
}

执行效果:

也一样成功排序完了。

可以发现这一种方法比起前面的Hoare版本和挖坑法,在取不取等号的探讨上少了很多麻烦。

  • 注意:

    在循环内的if语句中arr[cur] < arr[key]如果写为arr[cur] <= arr[key],并不能解决无法”二分“子序列的问题,所以加不加都无所谓。

    这也就是前后指针法的一个**缺陷:如果数组中数据都相等**,效率就会很低。


快排的非递归版本

所以现在已经知道了三种版本的快排,其实也就是三种找基准值的方法。

既然我们的快排使用的是递归,就难免有空间上的缺陷。其实快排还有非递归版本。但是要借助数据结构:栈

那么现在问题是左右区间再分左右区间时我们怎么找区间呢?因为找基准值时没有使用递归而是在找区间时使用的递归(所以找基准值使用前面说的三种方法的任意一种都行)。

(先将5和0入栈,然后出栈,left=0,right=5,找到基准值为3)

我们知道keyi(基准值)也就能区分左区间和右区间,这两个区间任意哪一个入栈都行。

现在,我们还是一样要现将right入栈再将left入栈(先入右区间),然后再入另一个区间。

此时栈不为空,我们出栈,先出的两个就是左区间,然后去找它的基准值。

然后这样找下去直到right小于left或等于left时,也就是没有数据或者只有一个数据时,构不成有效区间,就不入栈

左区间所有基准值找完后,就像二叉树一样,开始走右区间。

开始走右区间时也就是刚好栈里剩的两个数据为右区间时。

所以可以看出,我们取栈顶元素就是在模拟递归。

代码参考

现在我们通过代码来看看怎么使用栈进行快排。

//非递归版快排
//借助数据结构——栈
void QuickSortNonR(int* arr, int left, int right)
{ST st;STInit(&st);StackPush(&st, right);StackPush(&st, left);while (!StackEmpty(&st)){//取两次栈顶int begin = StackTop(&st);StackPop(&st);int end = StackTop(&st);StackPop(&st);//找基准值——用双指针法int prev = begin;int cur = begin + 1;int keyi = begin;while (cur <= end){if (arr[cur] <= arr[keyi] && ++prev!=cur){Swap(&arr[cur], &arr[prev]); }cur++;}Swap(&arr[keyi], &arr[prev]);keyi = prev;//根据基准值划分左右区间//左区间:[begin,keyi-1]//右区间:[keyi+1,end]if (keyi + 1 < end)//控制区间有效{StackPush(&st, end);StackPush(&st, keyi + 1);}	if (keyi-1>begin)//控制区间有效{StackPush(&st, keyi - 1);StackPush(&st, begin);}}STDestroy(&st);
}

那么到此本文就结束了,祝学习愉快=_=

相关文章:

快速排序(下)

快速排序&#xff08;下&#xff09; 前言 在上一篇文章中我们了解了快速排序算法&#xff0c;但那是Hoare的版本&#xff0c;其实还有别的版本&#xff1a;一种是挖坑法&#xff0c;它们的区别主要在于如何找基准值。霍尔的版本思路难理解但代码好理解&#xff0c;挖坑法则是…...

LazyLLM:长上下文场景下提高LLM推理效率

LazyLLM旨在优化大型语言模型&#xff08;LLM&#xff09;在处理长文本语境下的推理效率。传统上&#xff0c;LLM的推理过程分为预填充和解码两个阶段&#xff0c;其中预填充阶段负责计算并存储输入提示的所有token的键值&#xff08;KV&#xff09;缓存&#xff0c;这一步骤在…...

PDF文件点击打印无反应?是何原因造成能解决吗?

PDF无法打印怎么处理&#xff1f;在我们工作中&#xff0c;经常会遇见各种各样的文件问题&#xff0c;当我们想要将PDF文件打印出来纸质版使用&#xff0c;却不知什么原因&#xff0c;显示PDF无法打印&#xff0c;这时应该怎么处理呢&#xff1f; 一般情况下&#xff0c;PDF文件…...

初学者友好!从零到一快速上手PyCharm安装的超详细图解+避坑指南教程

一&#xff0c;pycharm的官网下载 下载地址&#xff1a;www.jetbrains.com/pycharm/ 本文将从 Python解释器安装到Pycharm专业版安装和配置汉化等使用都进行了详细介绍&#xff0c;希望能够帮助到大家。 Python解释器&Pycharm安装包&Pycharm破姐插件我都打包好了。 …...

AI大模型需要什么样的数据?

数据将是未来AI大模型竞争的关键要素 人工智能发展的突破得益于高质量数据的发展。例如&#xff0c;大型语言模型的最新进展依赖于更高质量、更丰富的训练数据集&#xff1a;与GPT-2相比&#xff0c;GPT-3对模型架构只进行了微小的修改&#xff0c;但花费精力收集更大的高质量…...

Java每日一练_模拟面试题1(死锁)

一、死锁的条件 死锁通常发生在两个或者更多的线程相互等待对方释放资源&#xff0c;从而导致它们都无法继续执行。死锁的条件通常被描述为四个必要条件&#xff0c;也就是互斥条件、不可剥夺条件、占有并等待条件和循环等待条件。 互斥条件&#xff1a;资源不能被共享&#x…...

第三方库认识- Mysql 数据库 API 认识

文章目录 一、msyql数据库API接口1.初始化mysql_init()——mysql_init2.链接数据库mysql_real_connect——mysql_real_connect3.设置当前客户端的字符集——mysql_set_character_set4.选择操作的数据库——mysql_select_db5.执行sql语句——mysql_query6.保存查询结果到本地——…...

Python兼职接单全攻略:掌握技能,拓宽收入渠道

引言 随着Python在数据处理、Web开发、自动化办公、爬虫技术等多个领域的广泛应用&#xff0c;越来越多的人开始利用Python技能进行兼职接单&#xff0c;以此拓宽收入渠道。本文将详细介绍Python兼职接单的注意事项、所需技能水平、常见单子类型、接单途径及平台&#xff0c;帮…...

一键编译并启动一个 ARM Linux qemu 虚拟机

需要事先自己编译 qemu-system-arm 可执行文件&#xff1b; 1&#xff0c;编译创建ARM 虚拟机 #!/usr/bin/bash sudo lssudo apt-get install gcc-arm-linux-gnueabi#wget https://mirrors.edge.kernel.org/pub/linux/kernel/v5.x/linux-5.10.tar.gztar zxf linux-kernel-v5.10…...

KubeVirt虚拟机存储及网络卸载加速解决方案

1. 方案背景 1.1. KubeVirt介绍 随着云计算和容器技术的飞速发展&#xff0c;Kubernetes已成为业界公认的容器编排标准&#xff0c;为用户提供了强大、灵活且可扩展的平台来部署和管理各类应用。然而&#xff0c;在企业的实际应用中&#xff0c;仍有许多传统应用或遗留系统难…...

JVM—对象已死?

参考资料&#xff1a;深入理解Java虚拟机&#xff1a;JVM高级特性与最佳实践&#xff08;第3版&#xff09;周志明 在堆里面存放着 Java 世界中几乎所有的对象实例,垃圾收集器在对堆进行回收前,第一件事情就是要确定这些对象之中哪些还“存活”着,哪些已经“死去”。 1、如何判…...

【前端面试3+1】20 css三栏布局6种实现方式、多行文本溢出怎么实现、token过期了怎么处理、【二叉树的中序遍历】

一、css三栏布局6种实现方式 1.浮动布局&#xff08;Floats&#xff09; .container {overflow: auto; /* 清除浮动 */ }.left, .right {width: 20%; /* 左右栏宽度 */float: left; }.middle {width: 60%; /* 中间栏宽度 */margin: 0 20%; /* 左右栏宽度 */ } 2.Flexbox .conta…...

【C++】vector介绍以及模拟实现(超级详细<=>源码并存)

欢迎来到我的Blog&#xff0c;点击关注哦&#x1f495; 【C】vector介绍以及模拟实现 前言vector介绍 vector常见操作构造函数iteratorcapacitymodify vector模拟实现存储结构默认构造函数构造函数拷贝构造函数赋值运算符重载析构函数 容量&#xff08;capacity&#xff09;si…...

【Redis 进阶】主从复制(重点理解流程和原理)

在分布式系统中为了解决单点问题&#xff08;某个服务器程序只有一个节点&#xff08;只搞一个物理服务器来部署这个服务器程序&#xff09;。可用性不高&#xff1a;如果这个机器挂了意味着服务就中断了&#xff1b;性能 / 支持的并发量比较有限&#xff09;。通常会把数据复制…...

Git常用命

转自&#xff1a;https://blog.csdn.net/ahjxhy2010/article/details/80047553 1.查看某个文件或目录的修改历史 git log filename #查看fileName相关的commit记录 git log -p filenam # 显示每次提交的diff#只看某次提交中的某个文件变化&#xff0c;commit-id  文件名…...

强化学习时序差分算法之Q-learning算法——以悬崖漫步环境为例

0.简介 基于时序差分算法的强化学习算法除了Sarsa算法以外还有一种著名算法为Q-learning算法&#xff0c;为离线策略算法&#xff0c;与在线策略算法Sarsa算法相比&#xff0c;其时序差分更新方式变为 Q(St,At)←Q(St,At)α[Rt1γmaxaQ(St1,a)−Q(St,At)] 对于 Sarsa 来说&am…...

111推流111

推流推流...

刷题——数组中只出现一次的两个数字

数组中只出现一次的两个数字_牛客题霸_牛客网 描述 一个整型数组里除了两个数字只出现一次&#xff0c;其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 数据范围&#xff1a;数组长度 2≤n≤10002≤n≤1000&#xff0c;数组中每个数的大小 0<val≤100000…...

《剖析程序员面试“八股文”:助力、阻力还是噱头?》

#“八股文”在实际工作中是助力、阻力还是空谈&#xff1f; 作为现在各类大中小企业面试程序员时的必问内容&#xff0c;“八股文”似乎是很重要的存在。但“八股文”是否能在实际工作中发挥它“敲门砖”应有的作用呢&#xff1f;有IT人士不禁发出疑问&#xff1a;程序员面试考…...

Redis过期key的删除策略

在 Redis 中&#xff0c;设置了过期时间的键在过期时间到达后&#xff0c;并不会立即从内存中删除。如果不是&#xff0c;那过期后到底什么时候被删除呢&#xff1f; 下面对这三种删除策略进行具体分析。 立即删除&#xff1a; 立即删除能够保证内存数据的及时性和空间的有效…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...