当前位置: 首页 > 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; 立即删除能够保证内存数据的及时性和空间的有效…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

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

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

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...