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

C语言实现Hoare版快速排序(递归版)

Hoare版

快速排序是由Hoare发明的,所以我们先来讲创始人的想法。我们直接切入主题,Hoare版快速排序的思想是将一个值设定为key,这个值不一定是第一个,如果你选其它的值作为你的key,那么你的思路也就要转换一下,好,我们刚刚说到将一个值设为key(这里我们就将第一个值设为key就好了),left在最左边,right在最右边,我们设定好key值之后,先让right往左走(目标是找小),找到比key小的值就停下,再让left往右走(目标是找大),找到比key大的值就停下,然后交换right和left的值,这样就会让大的那一个值到右边,小的那一个值到左边,交换完后再让right先走,以此类推直到相遇,相遇后的那个值再跟key进行交换,一趟就结束了,快速排序的一个特点是每一趟走完都会定下这个key值的位置,也就是说每一趟走完都将固定一个值,然后进行递归,把所有值都固定就排序完成了。

接下来说说第二趟也就是如何来递归,我们前面说过了,每一趟都会确认一个值的位置,那么,我们的步骤就是类比二叉树的后序遍历一样,以固定的值为最左值或最右值,依次固定住所有的该在的位置。

我们已经知道,每一趟都会确定key值以及位置,那么我们就将每一趟排序的过程单独封装成一个函数PartSort1.既然是递归,那么我们肯定要有结束条件吧,结束条件就是begin>=end,为什么是这个呢?我们看下面的代码,我说过了,类似后序遍历的思想,所以我们就写出了先找左,再找右的递归代码,第一个QuickSort就是往左递归嘛,那么起始位置就是begin不变,右边的界限就是我们通过函数找出来的k(key交换后的下标),但是要减一,因为key的下标k已经是确定好的了嘛,就不需要访问它了;第二个QuickSort自然就是访问右边了,访问右边最右边就不用动,最左边是k+1,理由跟上面的是一样的。

这样我们就理解了,第一个QuickSort后如果只有一个数据可以访问,那么begin是==end的,就该停止,那么第二QuickSort个可能就是没有数据,这个时候begin就会大于end,也要停止,接下来我们具体看看排序部分是怎么写的。

从上往下的思路是left等于最左值,right等于最右值,key也等于最左值的下标,当还没相遇的情况下,循环就会继续,按照思路先让右边找小,找到就停止,但是不要漏了后面的条件,因为如果没有找到,就会一直往左走,到最后right就变成负的了。同理,下面left的思路也是一样的,left和right都找到后就交换,当两个相遇之后,把key的值跟他们交换就行了。然后返回新的key下标。

相关文章:

C语言实现Hoare版快速排序(递归版)

Hoare版 快速排序是由Hoare发明的,所以我们先来讲创始人的想法。我们直接切入主题,Hoare版快速排序的思想是将一个值设定为key,这个值不一定是第一个,如果你选其它的值作为你的key,那么你的思路也就要转换一下&#xf…...

git 避免输入用户名 密码 二进制/文本 文件冲突解决

核心概念介绍 工作区是你当前正在进行编辑和修改的文件夹,可见的。 暂存区位于.git/index(git add放入)。 代码库(工作树)位于.git(git commit将暂存区中的更改作为一个提交保存到代码库中,并清空暂存区) 避免输入用户 密码: 方式一: ht…...

[OpenWrt]RAX3000一根线实现上网和看IPTV

背景: 1.我家电信宽带IPTV 2.入户光猫,桥接模式 3.光猫划分vlan,将上网信号IPTV信号,通过lan口(问客服要光猫超级管理员密码,具体教程需要自行查阅,关键是要设置iptv在客户侧的vlan id&#…...

最新50万字312道Java经典面试题52道场景题总结(附答案PDF)

最近有很多粉丝问我,有什么方法能够快速提升自己,通过阿里、腾讯、字节跳动、京东等互联网大厂的面试,我觉得短时间提升自己最快的手段就是背面试题;花了3个月的时间将市面上所有的面试题整理总结成了一份50万字的300道Java高频面…...

​html.parser --- 简单的 HTML 和 XHTML 解析器​

源代码: Lib/html/parser.py 这个模块定义了一个 HTMLParser 类,为 HTML(超文本标记语言)和 XHTML 文本文件解析提供基础。 class html.parser.HTMLParser(*, convert_charrefsTrue) 创建一个能解析无效标记的解析器实例。 如果…...

赵传和源代码就是设计-UMLChina建模知识竞赛第4赛季第23轮

参考潘加宇在《软件方法》和UMLChina公众号文章中发表的内容作答。在本文下留言回答。 只要最先答对前3题,即可获得本轮优胜。第4题为附加题,对错不影响优胜者的判定,影响的是优胜者的得分。 所有题目的回答必须放在同一条消息中&#xff0…...

Leaflet.Graticule源码分析以及经纬度汉化展示

目录 前言 一、源码分析 1、类图设计 2、时序调用 3、调用说明 二、经纬度汉化 1、改造前 2、汉化 3、改造效果 总结 前言 在之前的博客基于Leaflet的Webgis经纬网格生成实践中,已经深入介绍了Leaflet.Graticule的实际使用方法和进行了简单的源码分析。认…...

html 中vue3 的setup里调用element plus的弹窗 提示

引入Elementplus之后&#xff0c;在setup&#xff08;&#xff09;方法外面导入ElMessageBox const {ElMessageBox} ElementPlus 源码 &#xff1a; <!DOCTYPE html> <html> <head><meta charset"UTF-8"><!-- import Vue before Elemen…...

对话系统之解码策略(Top-k Top-p Temperature)

一、案例分析 在自然语言任务中&#xff0c;我们通常使用一个预训练的大模型&#xff08;比如GPT&#xff09;来根据给定的输入文本&#xff08;比如一个开头或一个问题&#xff09;生成输出文本&#xff08;比如一个答案或一个结尾&#xff09;。为了生成输出文本&#xff0c…...

《面向机器学习的数据标注规程》摘录

说明&#xff1a;本文使用的标准是2019年的团体标准&#xff0c;最新的国家标准已在2023年发布。 3 术语和定义 3.2 标签 label 标识数据的特征、类别和属性等。 3.4 数据标注员 data labeler 对待标注数据进行整理、纠错、标记和批注等操作的工作人员。 【批注】按照定义…...

VGG(pytorch)

VGG:达到了传统串型结构深度的极限 学习VGG原理要了解CNN感受野的基础知识 model.py import torch.nn as nn import torch# official pretrain weights model_urls {vgg11: https://download.pytorch.org/models/vgg11-bbd30ac9.pth,vgg13: https://download.pytorch.org/mo…...

celery/schedules.py源码精读

BaseSchedule类 基础调度类&#xff0c;它定义了一些调度任务的基本属性和方法。以下是该类的主要部分的解释&#xff1a; __init__(self, nowfun: Callable | None None, app: Celery | None None)&#xff1a;初始化方法&#xff0c;接受两个可选参数&#xff0c;nowfun表…...

单片机上位机(串口通讯C#)

一、简介 用C#编写了几个单片机上位机模板。可定制&#xff01;&#xff01;&#xff01; 二、效果图...

初识Flask

摆上中文版官方文档网站&#xff1a;https://flask.github.net.cn/quickstart.html 开启实验之路~~~~~~~~~~~~~ from flask import Flaskapp Flask(__name__) # 使用修饰器告诉flask触发函数的URL&#xff0c;绑定URL&#xff0c;后面的函数用于返回用户在浏览器上看到的内容…...

JeecgBoot jmreport/queryFieldBySql RCE漏洞复现

0x01 产品简介 Jeecg Boot(或者称为 Jeecg-Boot)是一款基于代码生成器的开源企业级快速开发平台,专注于开发后台管理系统、企业信息管理系统(MIS)等应用。它提供了一系列工具和模板,帮助开发者快速构建和部署现代化的 Web 应用程序。 0x02 漏洞概述 Jeecg Boot jmrepo…...

机器学习---模型评估

1、混淆矩阵 对以上混淆矩阵的解释&#xff1a; P&#xff1a;样本数据中的正例数。 N&#xff1a;样本数据中的负例数。 Y&#xff1a;通过模型预测出来的正例数。 N&#xff1a;通过模型预测出来的负例数。 True Positives:真阳性&#xff0c;表示实际是正样本预测成正样…...

【机器学习】应用KNN实现鸢尾花种类预测

目录 前言 一、K最近邻&#xff08;KNN&#xff09;介绍 二、鸢尾花数据集介绍 三、鸢尾花数据集可视化 四、鸢尾花数据分析 总结 &#x1f308;嗨&#xff01;我是Filotimo__&#x1f308;。很高兴与大家相识&#xff0c;希望我的博客能对你有所帮助。 &#x1f4a1;本文由Fil…...

ACL和NAT

目录 一.ACL 1.概念 2.原理 3.应用 4.种类 5.通配符 1.命令 2.区别 3.例题 4.应用原则 6.实验 1.实验目的 2.实验拓扑 3.实验步骤 7.实验拓展 1.实验目的 2.实验步骤 3.测试 二.NAT 1.基本理论 2.作用 3.分类 静态nat 动态nat NATPT NAT Sever Easy-IP…...

MX6ULL学习笔记(十二)Linux 自带的 LED 灯

前言 前面我们都是自己编写 LED 灯驱动&#xff0c;其实像 LED 灯这样非常基础的设备驱动&#xff0c;Linux 内 核已经集成了。Linux 内核的 LED 灯驱动采用 platform 框架&#xff0c;因此我们只需要按照要求在设备 树文件中添加相应的 LED 节点即可&#xff0c;本章我们就来学…...

Qt容器QToolBox工具箱

# QToolBox QToolBox是Qt框架中的一个窗口容器类,常用的几个函数有: ​setCurrentIndex(int index):设置当前显示的页面索引。可以通过调用该函数,将指定索引的页面设置为当前显示的页面。 addItem(QWidget * widget, const QString & text):向QToolBox中添加一个页面…...

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

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

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...